上行復選制,跟方案4類似,只不過第一輪淘汰的不是支持最少,而是反對最多的候選人(獲得最多末選票的候選人)

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

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

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

    方案6:多賽制,民眾對候選人排序,然后候選人之間兩兩pk,統(tǒng)計每一張選票上看候選人A在候選人B前面還是B在A前面,如此找到獲勝場次最多的候選人來贏得選舉.

    這樣的問題是可能導致循環(huán)勝負,如ABC三個候選人,有3個民眾,投票分別是ABC,BCA,CAB,可以看出AB之間A獲勝兩次,A>B;BC之間B獲勝兩次,B>C,AC之間C獲勝兩次,C>A,這樣就構成了一個A>B>C的循環(huán).這個是不是有點像足球聯(lián)賽的記分制啊,如果積分相同,足球比賽中可以再看凈勝球、進球、勝負關系等,但是作者并沒有在這個方面進行展開,而是介紹了另一種方式:博達制.

    方案7:博達制,民眾對候選人排序,假如有n個候選人,第一位的候選人得n分,第二位得n-1分,以此類推,然后統(tǒng)計每個候選人的總分,獲得最多分的獲勝.

    有人對博達制的批評是:可能有選民會利用這種方式進行作弊(投"策略票"),最支持B的候選人本來心目中的排序是B>A>C,但是由于相對A,他們還是更喜歡B,因此,為了把B拉上來,就得把A拉下去,他們的投票就變成了B>C>A.博達對此批評的回應是:我的制度只適用于誠實的投票者.

    而這本書的作者卻認為博達制的"策略票"問題沒那么嚴重,如果無法準確預測民意和精確控制策略票的投法,有可能因為用力過猛,不但把A拉下來了,反而讓C獲得的支持票增加,這樣就使得最支持B的那些人的"策略票"反而使得他們最討厭的C當選了,當年在IMDB上就發(fā)生過類似一幕:

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

    博達制是否有其他問題呢?

    以上只是對這本書第14章的一個筆記,也僅僅針對"多候選人單職位"問題進行了討論,書的后面還會對"多候選人多職位"的情況繼續(xù)探討,也就是根據(jù)每個人對候選人的排序,來決定最終的候選人排序.

    回到搜索引擎領域來,如上策略的變遷會給我們一些啟示,先看看之前抽象出來的問題:

    有n個候選人,每個選民對這n個候選人投票,最終在n個候選人中選出最合適、最符合民意、也符合邏輯的那個人.

    這很像搜索引擎在解決的問題:

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

    從選舉的例子中,我們可以得到的幾個啟示:

    1. 設計算法時,要避免出現(xiàn)"贏者通吃"帶來的信息丟失問題.

    2. 不要因為某幾個特征特別好,就把某個網(wǎng)頁排到最前,或者因為某幾個特征特別差,就把某個網(wǎng)頁拋棄.

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

    4. 搜索引擎使用者對搜索結(jié)果的點擊行為,可以看成是對搜索結(jié)果進行的"投票",這樣的"投票"信息的使用方式,也要注意考慮是否會帶來選舉過程中出現(xiàn)的種種不合理.

    以上提到的種種選舉方案,僅僅是對"多候選人單職位的"的情況進行討論,而搜索引擎面對的問題,則更類似于"多候選人排序"的情況,也即:

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

    而這個"多候選人排序"問題,是有一個"不可能的民主"的理論的,該理論的大意是,"合理"的民主應該滿足3個條件:

    1. 如果選民都認為A比B好,那么最終結(jié)果應該也是A比B好

    2. 沒有"獨裁者",也即,不存在這樣一個人,無論別人怎么排序,最終結(jié)果的排序都和這個人的排序一致

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

    而通過數(shù)學的證明,可以得出結(jié)論:如果某種選舉方式滿足條件1和3,則必然不滿足2,也即必然存在"獨裁者",這個問題的證明,可以參考這篇博客:

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

    1. 認為條件3過于強,需要弱化.

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