前些天讀了一本《選舉的困境》，其中有一章，從美國(guó)的選舉制度說(shuō)起，介紹美國(guó)選舉制度的不足，然后針對(duì)其不足，提出種種改善，然而每種改善都有其各自的問(wèn)題，其中的變化很有趣。

 

    先說(shuō)美國(guó)選舉制度，美國(guó)的總統(tǒng)選舉是一種“贏者通吃”的方式，每個(gè)州根據(jù)其人口多少，有幾十或幾百的“州票”，州里的人對(duì)總統(tǒng)候選人進(jìn)行選舉，在某個(gè)州獲得票最多的那個(gè)候選人，獲得這個(gè)州所有的“州票”，然后統(tǒng)計(jì)所有候選人的“州票”多少，獲得最多“州票”的候選人獲勝。

 

    這樣制度的問(wèn)題是顯然的，比如如果只有兩個(gè)州，A州5個(gè)人，而B(niǎo)州4個(gè)人，州票也分別是5和4，如果某候選人X在A州以3:2獲勝，另一個(gè)候選人Y在B州以4:0獲勝，這樣顯然候選人Y在全國(guó)范圍內(nèi)獲得了6張票，而候選人X只有在A州的3張票，但是由于“贏者通吃”，X獲得了A周的全部5張“州票”，Y只獲得了B周的4張“州票”，在全國(guó)只有1/3民眾支持的X居然獲得了選舉的勝利。

 

    這樣的情況在2000年美國(guó)總統(tǒng)選舉中就出現(xiàn)過(guò)，小布什的州票領(lǐng)先于戈?duì)�，然而在全�?guó)民眾中統(tǒng)計(jì)支持戈?duì)柕娜藬?shù)卻是大于小布什的，當(dāng)然戈?duì)栞斀o小布什還有另一個(gè)原因，這里按下不表。

 

    如果放在算法領(lǐng)域，可以看出這里的問(wèn)題在于，為了統(tǒng)計(jì)結(jié)果R(最適合的總統(tǒng)人選)，找到了一個(gè)特征A(每個(gè)民眾的投票)，而決定結(jié)果R的，卻不是特征A，而是由特征A推導(dǎo)出來(lái)的特征B(州票)，在特征A向特征B的推導(dǎo)過(guò)程中，信息丟失了(每個(gè)洲的支持百分比不一樣)。

 

    “贏者通吃”這種制度的具體歷史原因先不說(shuō)，有興趣的朋友可以去看原著。解決這種問(wèn)題的最直接方案就是從“贏者通吃”變成直選，也就是一人一票，直接統(tǒng)計(jì)票數(shù)，然而這樣也會(huì)遇到一系列問(wèn)題。

 

    在談那一系列問(wèn)題之前，先把要解決的問(wèn)題抽象一下：

 

    有n個(gè)候選人，每個(gè)選民對(duì)這n個(gè)候選人投票，最終在n個(gè)候選人中選出最合適、最符合民意、也符合邏輯的那個(gè)人。

 

    方案1：一票制，每人一票，選出自己最喜歡的候選人，對(duì)結(jié)果進(jìn)行統(tǒng)計(jì)，得票最多的那個(gè)人當(dāng)選。

 

    這樣做的問(wèn)題是會(huì)導(dǎo)致作者定義的一種“鷸蚌困局”，舉例說(shuō)，如果有ABC三個(gè)候選人，其中BC政見(jiàn)比較類似，支持B的人也比較支持C，反之亦然，在全民中，喜歡BC的人占多數(shù)，A的政見(jiàn)和BC相反，支持A的人在全民中占少數(shù)。這樣導(dǎo)致的后果就是，BC獲得的票會(huì)比較分散，而A獲得的票比較集中從而獲得勝利，如果BC中有1人不參加選舉，票就會(huì)集中到B或者C一個(gè)人的手中，從而使多數(shù)選民的支持者當(dāng)選。前面按下不表的戈?duì)柺�敗的另一個(gè)原因，就是有人認(rèn)為有跟戈?duì)栒��?jiàn)類似的耐德的參與，他分散了部分戈?duì)柕倪x票。

 

    可以對(duì)此問(wèn)題有所改善的方案叫做“二選制”。

 

    方案2：二選制，每人一票，如果無(wú)人獲得大于50%的支持，則將得票最高的兩個(gè)候選人拿出來(lái)，再進(jìn)行一輪選舉，得票多的人獲勝。

 

    法國(guó)總統(tǒng)選舉就是這樣的二選制，但是這樣的方法只能改善“鷸蚌困局”，而不能徹底解決，2002年的法國(guó)總統(tǒng)大選就出現(xiàn)了類似的情況，當(dāng)時(shí)支持左派政見(jiàn)的民眾較多，然而在二選制下，最終的前兩名卻是一個(gè)右派和一個(gè)極右派。出現(xiàn)這種情況的原因是當(dāng)年有16個(gè)總統(tǒng)候選人，且多數(shù)是持左派政見(jiàn)者，這樣就導(dǎo)致左派的票極端分散。

 

    方案3：n選制，每人一票，如果無(wú)人獲得大于50%的支持，則去掉支持最少的候選人，再進(jìn)行一輪投票，若依舊無(wú)人獲得大于50%的支持，再去掉得票最少的候選人，直到有人大于50%支持為止。

 

    2001年奧委會(huì)決定北京為2008年奧運(yùn)會(huì)主辦城市的時(shí)候，就是用的這樣的制度，在第一輪投票里大阪被淘汰，北京在第二輪就獲得了半數(shù)以上的支持，從而當(dāng)選。

 

    n選制的問(wèn)題在于不實(shí)用，如果是奧委會(huì)這種只有幾百個(gè)人投票的情況還可以使用，如果類似前面法國(guó)總統(tǒng)選舉，有16個(gè)候選人，舉國(guó)上下最多可能進(jìn)行15次投票，成本太高。

 

    方案4：即刻復(fù)選制，每個(gè)民眾對(duì)候選人進(jìn)行排序，如果某個(gè)候選人獲得了50%以上的首選，則直接獲得勝利，否則淘汰票數(shù)最低的候選人，并且把票數(shù)最低候選人的得票中的第二候選人拿出來(lái)，分給對(duì)應(yīng)的候選人，如果有人獲得50%以上，則當(dāng)選，否則再淘汰一位最低的，并且把他票分給里面排序最高的且未被淘汰的候選人，如此往復(fù)。

 

    愛(ài)爾蘭總統(tǒng)選舉和倫敦市長(zhǎng)選舉采用的是類似的方案，此方案也有問(wèn)題，試想如此場(chǎng)景：選民共10人，中間派候選人是3人的首選，左派和右派的候選人分別是4人的首選，當(dāng)然左派選民最討厭右派候選人，而右派選民也最討厭左派候選人，而左派右派的民眾對(duì)中間派候選人倒是都可以接受，不管是即可復(fù)選制還是n選制，中間派候選人都會(huì)在第一輪被淘汰。而中間派候選人則是全體民眾都可以接受的人，也最能調(diào)和各派之間矛盾，最和諧。

 

    這個(gè)方案的本質(zhì)問(wèn)題是，雖然每個(gè)選民可以對(duì)候選人排序，但是在第一輪的時(shí)候卻只考慮了第一選，沒(méi)有考慮選民的二、三選。

 

    方案5：上行復(fù)選制，跟方案4類似，只不過(guò)第一輪淘汰的不是支持最少，而是反對(duì)最多的候選人(獲得最多末選票的候選人)

 

    再看上面提到的情況，中間派候選人由于不是任何人的末選，所以第一輪淘汰的是左派或者右派，再第二輪選舉中，中間派的候選人就可以獲勝了。

 

    方案5也有方案5的問(wèn)題，考慮這樣一種情況，只有兩個(gè)候選人AB參選，選民9人，其中6人喜歡A而討厭B，3人喜歡B而討厭A，無(wú)論按照之前的哪種方式，都會(huì)是A獲勝。但是現(xiàn)在又多了兩個(gè)候選人C和D，喜歡B的3人中，都是把A列在最后一個(gè)候選的，而喜歡A的6人的末選，卻是BCD各2票，這樣，在第一輪選舉中，A就由于獲得了最多的末選票被淘汰了，而通過(guò)精心的構(gòu)造例子，完全可以使B最終當(dāng)選。僅僅由于CD參選或者不參選，A和B之間的勝負(fù)關(guān)系就發(fā)生了大逆轉(zhuǎn)。

 

    實(shí)際使用此方案的例子不多，只有在公元前507年的雅典有類似的方案，不是讓民眾投支持票，而是投反對(duì)票，把反對(duì)最多的人投出局。

 

    方案6：多賽制，民眾對(duì)候選人排序，然后候選人之間兩兩pk，統(tǒng)計(jì)每一張選票上看候選人A在候選人B前面還是B在A前面，如此找到獲勝場(chǎng)次最多的候選人來(lái)贏得選舉。

 

    這樣的問(wèn)題是可能導(dǎo)致循環(huán)勝負(fù)，如ABC三個(gè)候選人，有3個(gè)民眾，投票分別是ABC，BCA，CAB，可以看出AB之間A獲勝兩次，A>B；BC之間B獲勝兩次，B>C，AC之間C獲勝兩次，C>A，這樣就構(gòu)成了一個(gè)A>B>C的循環(huán)。這個(gè)是不是有點(diǎn)像足球聯(lián)賽的記分制啊，如果積分相同，足球比賽中可以再看凈勝球、進(jìn)球、勝負(fù)關(guān)系等，但是作者并沒(méi)有在這個(gè)方面進(jìn)行展開(kāi)，而是介紹了另一種方式：博達(dá)制。

 

    方案7：博達(dá)制，民眾對(duì)候選人排序，假如有n個(gè)候選人，第一位的候選人得n分，第二位得n-1分，以此類推，然后統(tǒng)計(jì)每個(gè)候選人的總分，獲得最多分的獲勝。

 

    有人對(duì)博達(dá)制的批評(píng)是：可能有選民會(huì)利用這種方式進(jìn)行作弊(投“策略票”)，最支持B的候選人本來(lái)心目中的排序是B>A>C，但是由于相對(duì)A，他們還是更喜歡B，因此，為了把B拉上來(lái)，就得把A拉下去，他們的投票就變成了B>C>A。博達(dá)對(duì)此批評(píng)的回應(yīng)是：我的制度只適用于誠(chéng)實(shí)的投票者。

 

    而這本書(shū)的作者卻認(rèn)為博達(dá)制的“策略票”問(wèn)題沒(méi)那么嚴(yán)重，如果無(wú)法準(zhǔn)確預(yù)測(cè)民意和精確控制策略票的投法，有可能因?yàn)橛昧�過(guò)猛，不但把A拉下來(lái)了，反而讓C獲得的支持票增加，這樣就使得最支持B的那些人的“策略票”反而使得他們最討厭的C當(dāng)選了，當(dāng)年在IMDB上就發(fā)生過(guò)類似一幕：

 

    電影《蝙蝠俠6》上映后，蝙蝠俠的粉絲們覺(jué)得這部片太酷了，于是就想把蝙蝠俠6投成IMDB第一位，于是他們瘋狂的給蝙蝠俠6打高分，而同時(shí)，也紛紛的給當(dāng)時(shí)的IMDB第一《教父》投低分，導(dǎo)致的結(jié)果就是用力過(guò)猛，教父變成了第三名，原來(lái)的第二肖申克的救贖(TSR)變成了第二(原來(lái)的第二是排在教父后面，新的第二是排在蝙蝠俠6后面)，而后來(lái)，隨著瘋狂粉絲的熱情消退，理性的意見(jiàn)占據(jù)了上風(fēng)，蝙蝠俠6的得分逐漸下降，跌到了第10。而教父還是在肖申克的救贖后面，很久沒(méi)有回去了。

 

    博達(dá)制是否有其他問(wèn)題呢？

 

    以上只是對(duì)這本書(shū)第14章的一個(gè)筆記，也僅僅針對(duì)“多候選人單職位”問(wèn)題進(jìn)行了討論，書(shū)的后面還會(huì)對(duì)“多候選人多職位”的情況繼續(xù)探討，也就是根據(jù)每個(gè)人對(duì)候選人的排序，來(lái)決定最終的候選人排序。

 

    回到搜索引擎領(lǐng)域來(lái)，如上策略的變遷會(huì)給我們一些啟示，先看看之前抽象出來(lái)的問(wèn)題：

 

    有n個(gè)候選人，每個(gè)選民對(duì)這n個(gè)候選人投票，最終在n個(gè)候選人中選出最合適、最符合民意、也符合邏輯的那個(gè)人。

 

    這很像搜索引擎在解決的問(wèn)題：

 

    系統(tǒng)里有n個(gè)網(wǎng)頁(yè)，有m個(gè)特征(頁(yè)面質(zhì)量、頁(yè)面內(nèi)容豐富度、頁(yè)面超鏈、文本相關(guān)性等)對(duì)n個(gè)網(wǎng)頁(yè)有不同的打分，如何根據(jù)這些特征的“投票”，選出最適合放在第一位的網(wǎng)頁(yè)呢？

 

    從選舉的例子中，我們可以得到的幾個(gè)啟示：

 

    1.設(shè)計(jì)算法時(shí)，要避免出現(xiàn)“贏者通吃”帶來(lái)的信息丟失問(wèn)題。

 

    2.不要因?yàn)槟硯讉�(gè)特征特別好，就把某個(gè)網(wǎng)頁(yè)排到最前，或者因?yàn)槟硯讉�(gè)特征特別差，就把某個(gè)網(wǎng)頁(yè)拋棄。

 

    3.最合適放在首位的網(wǎng)頁(yè)不一定是在每個(gè)特征上都最好，而應(yīng)該是能夠兼顧所有特征，綜合表現(xiàn)最好的那個(gè)。

 

    4.搜索引擎使用者對(duì)搜索結(jié)果的點(diǎn)擊行為，可以看成是對(duì)搜索結(jié)果進(jìn)行的“投票”，這樣的“投票”信息的使用方式，也要注意考慮是否會(huì)帶來(lái)選舉過(guò)程中出現(xiàn)的種種不合理。

 

    以上提到的種種選舉方案，僅僅是對(duì)“多候選人單職位的”的情況進(jìn)行討論，而搜索引擎面對(duì)的問(wèn)題，則更類似于“多候選人排序”的情況，也即：

 

    系統(tǒng)里有n個(gè)網(wǎng)頁(yè)，有m個(gè)特征(頁(yè)面質(zhì)量、頁(yè)面內(nèi)容豐富度、頁(yè)面超鏈、文本相關(guān)性等)對(duì)n個(gè)網(wǎng)頁(yè)有不同的打分，如何根據(jù)這些特征的“投票”，決定n個(gè)網(wǎng)頁(yè)的順序？

 

    而這個(gè)“多候選人排序”問(wèn)題，是有一個(gè)“不可能的民主”的理論的，該理論的大意是，“合理”的民主應(yīng)該滿足3個(gè)條件：

 

    1.如果選民都認(rèn)為A比B好，那么最終結(jié)果應(yīng)該也是A比B好

 

    2.沒(méi)有“獨(dú)裁者”，也即，不存在這樣一個(gè)人，無(wú)論別人怎么排序，最終結(jié)果的排序都和這個(gè)人的排序一致

 

    3.無(wú)關(guān)因素獨(dú)立性，也即，在第一次投票完成后，A排在B前面，現(xiàn)在進(jìn)行第二次投票，如果所有人都沒(méi)有改變自己投票中A和B的相對(duì)順序，那最終結(jié)果應(yīng)該也是A在B前面

 

    而通過(guò)數(shù)學(xué)的證明，可以得出結(jié)論：如果某種選舉方式滿足條件1和3，則必然不滿足2，也即必然存在“獨(dú)裁者”，這個(gè)問(wèn)題的證明，可以參考這篇博客：http://roba.rushcj.com/?p=509

 

    根據(jù)“不可能的民主”理論，和搜索引擎結(jié)合起來(lái)看，似乎搜索引擎很難給出一個(gè)合理的網(wǎng)頁(yè)排序，但是搜索引擎和投票又似乎有所不同，有兩個(gè)角度可以破解

 

    1.認(rèn)為條件3過(guò)于強(qiáng)，需要弱化。