上行復(fù)選制,跟方案4類(lèi)似,只不過(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年的雅典有類(lèi)似的方案,不是讓民眾投支持票,而是投反對(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分,以此類(lèi)推,然后統(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ò)類(lèi)似一幕:

    電影《蝙蝠俠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)題,則更類(lèi)似于"多候選人排序"的情況,也即:

    系統(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)該滿(mǎn)足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é)論:如果某種選舉方式滿(mǎn)足條件1和3,則必然不滿(mǎn)足2,也即必然存在"獨(dú)裁者",這個(gè)問(wèn)題的證明,可以參考這篇博客:

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

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

    2. 也許在網(wǎng)頁(yè)排序問(wèn)題上,真的存在這樣一個(gè)"獨(dú)裁特征",這個(gè)"獨(dú)裁特征"從目前看來(lái),最適合的應(yīng)該就是"用戶(hù)滿(mǎn)意度"了,按照用戶(hù)的滿(mǎn)意程度來(lái)排序網(wǎng)頁(yè),就是最合理的網(wǎng)頁(yè)排序.如何衡量"用戶(hù)滿(mǎn)意度"呢?這就是我們一直在努力的.