在我找到標題之前






         論文寫多了常常會忘記:書寫的價值,其實在背後的感動

19/04/2010

投票問題

Filed under: 研究─非關研究 — shoude @ 11:53 下午

今天碰到了一個很實際也很有趣的投票問題。絕對值得花時間想一下。
問題是這樣的:假設有N個候選人,我們要從中間用投票選出K個,而可以投票的人數有Y人。
現在問題來了,到底票要怎麼投才好?以下有幾個投票方案:

a. 投排序票,讓這Y人對這N個人排序,第一名得N-1分,最後一名得0分,最後把總分加起來選最高分的K個。

b. 投排序票,但是只排出前K個人,得分從N到N-K, 從第K+1名到第N名都得N-K-1分 (比如說四個選兩個的話,得分就是第一名三分,第二名兩分,剩下都一分)

c. 投贊成票。每個人可以投X張贊成票給X個人(不能多投也不能少投)最後選出得到最多贊成票的前K名。(在這個情況下,X應該要多少最好?)

一個適合的投票方案,至少要滿足幾個條件:

1. 對所有candidate是公平的

  • 這個部分上述作法都沒有疑義,因為都不會偏袒特定候選人。

2. 最多人贊成的可以出線, 沒有多數被少數操弄的風險

  • 這個部分其實非常tricky,因為涉及到大家知不知道其他人心中的順序的問題。我們先來看一個簡單的例子:假設N=4,K=2,Y=10,而且假設這十個投票人心中對這四個候選人的排序為

C1

C2

C3

C4

P1

1

2

3

4

P2

1

2

3

4

P3

1

2

3

4

P4

1

2

3

4

P5

1

2

3

4

P6

1

2

3

4

P7

1

3

2

4

P8

1

3

2

4

P9

1

3

2

4

P10

1

3

2

4

Avg

1

2.4

2.6

4

很明顯的C1這個candidate是大家心中的第一名。而C2應該是另外一個雀屏中選者,因為跟C3比起來C2被六個人排第二,C3只有四個。

我們假設大家是用(b)的方式投票,且假設所有人都按照心中的排序投票,那麼投票結果會是:

C1

C2

C3

C4

P1

1

2

3

3

P2

1

2

3

3

P3

1

2

3

3

P4

1

2

3

3

P5

1

2

3

3

P6

1

2

3

3

P7

1

3

2

3

P8

1

3

2

3

P9

1

3

2

3

P10

1

3

2

3

Avg

1

2.4

2.6

3

C1跟C2果然當選。

但是,我們都知道世界不總是這麼美好。不是所有人都想得這麼簡單。

假如有一個狀況,是P7-P10這四個人希望C3跟C1能夠當選,而他們已經知道C1是大多數人的favorite,於是,他們可以改變自己心中對C1以及C3的排序,做出配票行為如下:

C1

C2

C3

C4

P1

1

2

3

3

P2

1

2

3

3

P3

1

2

3

3

P4

1

2

3

3

P5

1

2

3

3

P6

1

2

3

3

P7

2

3

1

3

P8

2

3

1

3

P9

2

3

1

3

P10

2

3

1

3

1.4

2.4

2.2

3

結果C2很不幸的,成為投票操作下的犧牲者。

假設P1-P6都是很誠實的按照自己心中的想法排序時,少數人就可以藉由配票操作達成讓C3跟C1當選的目標。

我們假設大家是用(a)的方式投票呢?結果更慘,因為P7-P10可以故意給C2最低分,結果就會是更大的差距

C1

C2

C3

C4

P1

1

2

3

3

P2

1

2

3

3

P3

1

2

3

3

P4

1

2

3

3

P5

1

2

3

3

P6

1

2

3

3

P7

2

4

1

3

P8

2

4

1

3

P9

2

4

1

3

P10

2

4

1

3

1.4

2.8

2.2

3

以上例子可以發現排序為本的方法有很大的漏洞,就是因為排序,所以可以讓少數有心人故意penalize本來排名前面的人,以遂行自己的目的。

那麼,似乎看起來 (c) 是一個比較可行的方法。很不幸的是,大部分的case也不是。我們來看另一個例子:

C1

C2

C3

C4

C5

C6

C7

P1

1

2

3

4

5

6

7

P2

1

2

3

4

5

6

7

P3

1

2

3

4

5

6

7

P4

1

2

3

4

5

6

7

P5

1

2

3

4

5

6

7

P6

1

2

3

4

5

6

7

P7

1

2

3

7

4

5

6

P8

1

2

3

7

4

5

6

P9

1

2

3

4

5

6

7

P10

4

2

3

1

5

6

7

1.3

2

3

4.3

4.8

5.8

6.8

在這個case有七個candidate,很明顯的如果以少數服從多數的話,選出來的兩人應該是C1以及C2 .

在此先假設X=3,也就是規定每人要投出三張贊成票給三個不同的人。假設大家都是很正常的按照心中的順序投出三張票給前三名的人,結果會是

X=3

C1

C2

C3

C4

C5

C6

C7

P1

1

1

1

P2

1

1

1

P3

1

1

1

P4

1

1

1

P5

1

1

1

P6

1

1

1

P7

1

1

1

P8

1

1

1

P9

1

1

1

P10

1

1

1

9

10

10

1

0

0

0

結果C1很不幸的落榜了,因為雖然10個人裡面有9個把他排第一,他不小心得罪了P10少了一票.

這個問題其實很嚴重,因為大家只是照自己的想法投票沒有故意操弄,就可以讓比較適合的人落選。如果刻意操弄就更危險了,請看下例:

X=4

C1

C2

C3

C4

C5

C6

C7

P1

1

2

3

4

5

6

7

P2

1

2

3

4

5

6

7

P3

1

2

3

4

5

6

7

P4

1

2

3

4

5

6

7

P5

1

2

3

4

5

6

7

P6

1

2

3

4

5

6

7

P7

1

3

2

7

4

5

6

P8

1

3

2

7

4

5

6

P9

4

3

2

1

5

6

7

P10

4

3

2

1

5

6

7

1.6

2.4

2.6

4

4.8

5.8

6.8

假設X=4.

這個例子看起來,通常人會覺得C1跟C2比較好。尤其是C2明顯比C3好。但是如果P7跟P8特別想要讓C3當選,他們的作法會是將本來應該投給C2的票改成投給他們覺得最不可能當選的(也就是C4);而假設P9跟P10很希望C3跟C4當選,但是他們又知道多數人的favorite是C1及C2,於是他們兩個人比較保險的作法就會是把本來該投給C1及C2的票拿去投C6跟C7這兩個他們覺得不可能當選的。開票後結果如下表:

X=4

C1

C2

C3

C4

C5

C6

C7

P1

1

1

1

1

P2

1

1

1

1

P3

1

1

1

1

P4

1

1

1

1

P5

1

1

1

1

P6

1

1

1

1

P7

1

1

1

1

P8

1

1

1

1

P9

1

1

1

1

P10

1

1

1

1

8

6

10

10

2

2

2

C1及C2這兩個多數人排前兩名的人,不幸中箭落馬。

以(C)的投票方法,關鍵在於X的大小。只要X>K就會有問題。X=K的時候,被多數人支持的人K個人,就會拿到那多數人的票,而其他Top K之外的人選不會拿到多數人的票。於是少數人再怎麼操弄,都無法改變這個事實。但是X>K的時候,對於一般按照自己心中想法投票的人,就會有一些票分到非前K名的人員上面。於是這就給了那些少數人操控投票的機會。

Irresponsible Conclusion from SD:

從比較general的角度而言,投票行為有兩種模式,一種是鼓勵式,一種是懲罰式。鼓勵式基本上把票投給自己喜歡的人,懲罰模式基本上不把票投給自己不希望當選的人。當每個人手中選票多時(如X>K),選舉就會變成傾向懲罰式,因為相對上被鼓勵的人不一定會當選,但是被懲罰的人大概就不會選上。此外,要杜絕少數操弄選票的情況,最重要的策略之一就是降低投票行為的「自由度」(degree of freedom),在上述方式中自由度是(a)>(b)>(c),因為(a)給rank可以讓每個投票人更明確的拉開候選人差距。對於(c)而言應該是X越接近N/2大自由度愈高。有些人建議(c)中X是上限就可以,也就是每個人至多投X張贊成票,但是不限制一定要投滿X張,這個情況也是增加自由度,相對而言增加操弄這個game的可能性,所以也是不建議。

The bottom line is: It seems to me (c) is a better solution, given X≤K。一人一票的投票制度雖然有點呆板,但是卻是比較safe的模式。



No Comments

No comments yet.

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

Powered by WordPress MU.

total of 79650 visits