前陣子讀了《選舉的困境》,其中一章從美國選舉制度說起,先剖析制度缺陷,再逐一提出改進方案,而每種改進又都帶來新的問題。這條推演線索非常有意思,而且和排序算法的思路高度相通。
美國總統選舉採用的是「贏者通吃」:每個州按人口分配若干「州票」,州內投票後,得票最多者拿走該州全部州票,最後比總州票數。
缺陷很直觀。假設只有兩個州,A 州 5 人、5 張州票,B 州 4 人、4 張州票。候選人 X 在 A 州以 3:2 勝出,候選人 Y 在 B 州以 4:0 勝出。全國範圍看,Y 拿到 4 票,X 只有 3 票,但因為贏者通吃,X 帶走 A 州全部 5 張州票,Y 只帶走 4 張——僅獲三分之一選民支持的 X 反而當選。
2000 年的美國大選就出現過類似情形:小布什的州票領先,但普选票數落後於戈爾。(戈爾落敗還有另一個原因,此處暫且不表。)
換到算法語境,問題的本質是:我們想求解的目標是 R(最適人選),真正對應的特徵是 A(每個選民的投票),但決定 R 的卻是由 A 推導出的特徵 B(州票)。在 A→B 的推導過程中,各州支持率的差異被壓平了,信息發生丟失。
最直接的改法自然是取消贏者通吃,變成一人一票的直選。但麻煩才剛剛開始。先把問題抽象一下:有 n 個候選人,選民對他們投票,目標是從中選出最符合民意、也符合邏輯的那一個。
每人一票投給最喜歡的候選人,得票最多者當選。
問題是會出現「鹬蚌困局」。假設有 A、B、C 三人,B 與 C 政見接近、支持者互相認可,而喜歡 B 或 C 的人在全民中佔多數;A 政見相反,支持者是少數。結果 B、C 票源分散,A 票源集中反而勝出。只要 B、C 中有一人退選,票集中到另一人身上,多數派就能當選。戈爾落敗的另一個解釋正在於此:有人認為政見相近的第三方候選人分走了他的選票。
每人一票,若無人超過 50%,取前兩名再投一輪。法國總統選舉採用此制。
它能緩解鹬蚌困局,但無法根治。2002 年法國大選中,左派選民基數其實更大,最終進入第二輪的卻是一個右派和一個極右派候選人——因為當年有 16 位候選人,多數持左派政見,票被極端分散。
若無人超過 50%,淘汰得票最少者後重投,反覆進行直到有人過半。2001 年國際奧委會確定北京主辦 2008 年奧運會就用了這套機制:第一輪大阪被淘汰,第二輪北京即過半當選。
缺點是不實用。幾百人的投票還能承受,若是十幾位候選人的全國性選舉,最多可能要进行十五輪,成本無法接受。
選民對候選人排序。若有人獲得超過 50% 的首選直接勝出;否則淘汰票數最低者,並把這些選票轉給各自標記的下一位候選人,重複直到有人過半。愛爾蘭總統選舉與倫敦市長選舉採用類似機制。
問題依然存在。假設 10 位選民,中間派候選人是 3 人的首選,左右兩派各有 4 人的首選;左派選民最反感右派,右派選民最反感左派,但兩邊都能接受中間派。無論即時決選還是逐輪淘汰,中間派都會在第一輪出局。而他恰恰是全體最能接受、也最能調和分歧的人。
根本原因在於:即使選民完成了完整排序,第一輪統計時仍只看首選,忽略了第二、第三選擇攜帶的信息。
與方案四類似,只是第一輪淘汰的不是支持最少者,而是反對最多者(獲得最多末選票的候選人)。
回到上面的例子,中間派不是任何人的末選,於是第一輪出局的是左派或右派,第二輪中間派即可勝出。
但它也有自己的漏洞。假設只有 A、B 兩人參選,9 位選民中 6 人支持 A 厭惡 B,3 人反之,那麼無論哪種制度都是 A 勝。現在加入 C、D 兩位候選人:支持 B 的 3 人都把 A 排在末位,而支持 A 的 6 人末選則分散在 B、C、D 各 2 票。結果 A 因末選票最多而在第一輪被淘汰,精心構造之下甚至可能讓 B 當選。僅僅因為 C、D 是否參選,A 與 B 的勝負就完全逆轉。歷史上公元前 507 年的雅典有過類似做法,只是投的是反對票,把反對最多的人逐出。
選民對候選人排序,候選人之間兩兩 PK,統計每张選票上 A 與 B 的相對位置,勝場最多者當選。
問題是可能出現循環勝負。三名候選人 A、B、C,三位選民的排序分別是 ABC、BCA、CAB:A 對 B 兩勝,B 對 C 兩勝,而 C 對 A 也是兩勝,形成石頭剪刀布式的閉環,無法得出唯一結果。
排序系統的本質就是在做集體選擇:把大量用戶的行為聚合成一個最終順序。上面這些困境——信息在聚合過程中丟失、多數意見被分散、加入新選項改變原有結果、循環勝負無法求解——在排序模型中同樣存在,只是投票者換成了用戶點擊,候選人換成了網頁。理解這些經典困境,有助於在設計或評估一套排序機制時,先問清楚它究竟丟掉了哪些信息。