什麼是「讓大家開心」的投票算法？

我正在尋找一種基於大多數選票和票數組合的優勝者的投票算法。什麼是「讓大家開心」的投票算法？

活生生的例子：

公司擁有穀物棒。我們有3個不同的穀物的空間。我們想讓我們的員工投票選擇他們想要的穀物。

我們不想挑嚴格根據受歡迎程度的前3名，因爲有可能是員工的少數誰只能吃（無論何種原因）1種特別是穀物，我們想給他們儘可能的特殊津貼。

鑑於以下投票結果，下面是我們希望算法給我們的結果。

Vote scenario and desired outcome

我正在尋找一種算法，做這種排名。如果你至少可以提供我正在尋找的名字，這將是一個很大的幫助，因爲我可以更好地搜索它。 :)

謝謝！

來源

2011-12-14 joshuapoehls

要記住的一件事是，所描述的問題爲選擇較少選擇的人提供了更多的權力。如果我對他們中的任何人都感到滿意，但是特別喜歡他們，我可以聲稱這是我喜歡的唯一一個，並且實際上'迫使'你選擇它，因爲我沒有提供任何替代品。 – 2011-12-14 22:58:10

@NickJohnson也許就是這樣，因爲在那種情況下，你說如果你不能擁有X，那麼你對其他人沒有偏好。如果問題不能解決，我們不保證您會選擇一個約束。 – PengOne 2011-12-14 23:18:02

@PengOne沒有保證，不，但是你的偏好比另一個更誠實的選民更有可能受到尊重。如果要求您按照偏好順序對項目進行排名，則這一點更爲明顯。如果我誠實並且從1到3排列我最喜歡的3，我不太可能得到我想要的結果，而不是我僅排名我最喜歡的結果，並且沒有給別人帶來任何價值。 – 2011-12-14 23:32:03

你可能想要考慮Hall's marriage theorem和/或assignment problem的概括。

的理念，爲這個範式是建立一個二分圖，其中節點是人民和穀物，以人p和穀類c之間的邊緣，如果p投票c。我們的目標是選擇3種穀物，使得從刪除所有其它穀類得到的曲線圖是

連接（大家會吃所選穀物中的至少一種），和
最大化的最小/平均每個人的程度（最大化最小/平均快樂）

你可以改爲考慮這個爲Maximum Coverage Problem。在這種情況下，您已經設置了C1,C2,...,Cm其中Ci是一組喜歡穀類i的人。對於你舉例來說，以穀類和人民在表中列出的順序，你有

C1 = {1,5} 
C2 = {2} 
C3 = {1,4,5} 
C4 = {3,5}

讓n是人的數量，從而使Ci是{1,2,...,n}一個子集。目標是找到k集合，使聯合的基數最大化。如果存在多種解決方案，請選擇最小化交叉點基數的方法（最小化一個人主導的數量）或最大化最不頻繁元素重複的次數（使最不快樂的人的幸福最大化）。

對於此示例，其中涵蓋所有元素的最小的k是k=3並且它給出了唯一的解決方案C2,C3,C4。

然而，你看它，你有一個NP問題，但有已知的算法來解決它們（檢查維基百科文章的參考）。

來源

2011-12-14 23:12:16 PengOne

沒有一個完美的投票系統 - 見http://en.wikipedia.org/wiki/Arrow%27s_impossibility_theorem。已經有各種嘗試通過彎曲規則來解決這個問題，包括http://en.wikipedia.org/wiki/Range_voting。

接近範圍投票的一個想法是給每個人12張選票，並允許他們分發他們，如他們所願。看看你的例子，如果你假設有多種選擇的人平均分配他們的12張選票--12x1或6x2或4x3或3x4 - 那麼我認爲你可以得到你想要的結果，幸運符咒總共得到10張選票和其他一切比這更多。

來源

2011-12-14 20:39:45 mcdowella

我喜歡那個定理。我想，這個問題的標題立即引發你的想法。 – 2011-12-15 00:53:30

如果穀物的數量較少，您可以查看您的問題作爲一個子集覆蓋問題和蠻力用自己的方式尋找什麼樣的配置給最「當幸福來敲門」

var max_happyness = -INF 
for every subset {c1, c2, c3} of C: 
    max_hapyness = max(max_happyness, happyness(i1,i2,i3))

您仍然有問題定義一個合適的幸福功能。例如，你可以選擇一個快樂功能，作爲第一優先級來計算可以吃任何食物的人數。然後作爲第二優先級的人喜歡兩個穀類，那些喜歡三穀類的人等等。

優點：如果您可以定義一個幸福感函數，這可以給出最好的結果。

缺點：你必須能夠定義一個幸福函數。

來源

2011-12-14 20:52:44 hugomg

什麼是「讓大家開心」的投票算法？

回答

相關問題