社會選擇理論與投票演算法

社會選擇理論（Social Choice Theory）

社會選擇理論是探討一個問題：如何找到一個方式把團體中所有個體的喜好，拼成一個能代表全體意志的集體決策

用數學語言講，就是要找到一個制度或演算法（函數 $F(X, P)$）

輸入是選項 $X = \{A, B, C, D, \dots\}$ 跟個體的喜好 $P = (P_1, P_2, \dots, P_n)$

$$\begin{aligned} P_1 &= \{(A \succ B), (C \succ D), \dots\} \\ P_2 &= \{(C \succ A), (D \succ B), \dots\} \\ &\;\;\vdots \end{aligned}$$

使輸出能「代表全體意志」

$$F^* = \arg\max_{F \in \mathcal{F}} G(F)$$

其中 $\mathcal{F}$ 是所有可能的制度，$G$ 用來衡量一個制度有「多能代表全體意志」

你可能發現了，什麼叫代表全體意志??

定義是什麼？有這種東西嗎？這個看似我們再熟悉不過的東西，實際上並不好處理

我無法給出通用且明確的定義，但我能先列出結論，再一項項細說

全體意志存不存在	理論	現實
2 個選項	存在	不存在
3 個以上選項	不保證存在	不存在

在往下討論之前，補充說明一下社會選擇理論雖然用的多是數學與經濟學的語言，但能延伸到幾乎所有涉及多人決策的議題，例如：

• 一群人出去吃飯：決定要選哪間餐廳、要點什麼
• 民主：考慮人權保障、權力分立、憲法法治的集體決策制度
• 社會發展（福利經濟學）：法條制訂、基礎建設、社會福利政策、產業發展走向
• 股東會：多人考慮公司決策、根據持有股份有不同權重
• 推薦系統：根據使用者偏好與評分算出熱門影片排行榜

兩個選項時：May's Theorem

當選項只有兩個，跟你想的一樣，理論上的全體意志就是多數決（Majority rule）

多數決滿足以下條件（May's Theorem）：

1. Anonymity：每票等值
2. Neutrality：制度對選項無偏見
3. Positive responsiveness：如果大家投完後平手，此時只要有一個人改變心意支持 $A$，結果就必須變成 $A$ 勝出

這三個條件是多數決的核心精神，他不全然代表「公平」，卻是人們能想到對於公平最通用的詮釋

然而即便用多數決做出了決策，這個決策在現實生活中能代表「全體意志」嗎？顯然是不行的，因為少數人的意見會被忽視。因此我們才會說只有兩個選項時理論上能用多數決產生集體決策，現實中卻有更多情況是要為了避免多數人暴政，而對規則加以限制

三個選項時：全體意志是個假議題

只要是在台灣或民主國家長大，你大概都會覺得「只要人人投票，就能找出集體的意志、人民的智慧」，然而有兩個定理否決了這種幻想

1. 阿羅不可能定理證明只要選項有 3 個以上，滿足基本公平條件的排名投票制度就不存在
2. Gibbard-Satterthwaite 定理證明只要選項有 3 個以上，任何制度都防不住大家說謊

這兩個定理戳破了大家對民主政治美好的想像，並告訴我們唯一正確的「全體意志」並不存在，任何集體決策都只是投票規則不同帶來的結果

怎樣的 function 可以代表全體意志？

前面說要找到一個 $G$ 來代表全體意志，那這個 $G$ 會長怎樣呢？每一種 $G$ 其實就是一種對「全體意志」的定義（標準），而針對每種標準，又有不同的制度 $F$ 去實現它，例如：

1. 效用最大化（Utility Maximization）→ Borda Count
2. 多數標準（Majority）→ 相對多數決、多輪投票制
3. 孔多塞標準（Condorcet Criterion）→ Copeland、Schulze、Dodgson

其中多數標準跟孔多塞標準寫成 $G$ 的話就是滿足得 1 分、不滿足得 0 分

我們假設有四個選項、三個人在選擇

	第 1 名	第 2 名	第 3 名	第 4 名
小明	A	B	C	D
小華	B	C	D	A
小美	A	B	C	D

1. 效用最大化

每個人對每個選項都有一個「效用」（喜歡的程度），一個制度選出來的結果帶給大家的效用總和越大，就越能代表全體意志

$$G(F) = \sum_{i=1}^{n} u_i\big(F(X, P)\big)$$ $$F(X, P) = \arg\max_{x \in X} \sum_{i=1}^{n} u_i(x)$$

Borda Count：第 1 名給 3 分、第 2 名給 2 分、第 3 名給 1 分、第 4 名給 0 分

	A	B	C	D
小明	3	2	1	0
小華	0	3	2	1
小美	3	2	1	0
總分	6	7	4	1

勝出的是 B，雖然有兩個人最喜歡 A，但 B 沒有被任何人排在後段，A 卻是小華的最後一名，可以說 B 是比較「大家都能接受」的選項

2. 多數標準

相對多數決（Plurality） 這次每個人只能投一票，得票最多的勝出，也就是大部分選舉用的方式

$$F(X, P) = \arg\max_{x \in X} \left|\{\, i : x \text{ 是 } P_i \text{ 的第一名} \,\}\right|$$

上面的例子 A 拿 2 票、B 拿 1 票，A 勝出

相對多數決最常見的問題是分票

多輪投票制（Two-round system） 則是當第一輪沒有人過半時，前兩名進入第二輪

相對多數決跟多輪投票制都符合多數標準，但兩個制度可能會選出不同的結果，可見光靠多數標準還不足以決定全體意志

3. 否決制

只要有一個人否決，選項就會被拿掉，以例子來說 A 被小華否決就不會當選。這是個破壞 Neutrality 與效率的做法，傾向維持現狀

最有名的應該是聯合國安理會的五常否決權

4. 孔多塞標準

孔多塞 提出讓每個選項兩兩對決，如果有一個選項跟其他任何選項一對一都能贏（孔多塞贏家），它就是全體意志，制度就必須選它

對決	結果
A vs B	A 以 2:1 勝
A vs C	A 以 2:1 勝
A vs D	A 以 2:1 勝

A 是孔多塞贏家，跟相對多數決的結果一樣，但跟 Borda 不同，所以 Borda 不符合孔多塞標準

但應該也有人想到了，萬一大家的偏好，像剪刀石頭布一樣剪刀贏布、布贏石頭、石頭又贏剪刀，孔多塞標準就不適用了。這稱為孔多塞悖論：集體傾向可以是循環性的，即使個人的傾向不是

5. Dodgson's method

Dodgson 有另外一個較為人所知的名字叫 Lewis Carroll，就是寫愛麗絲夢遊仙境那個人

他提出如果遇到孔多塞悖論，就計算每個選項「需要把相鄰的偏好排序對調幾次，才能讓自己成為孔多塞贏家」，次數最少的那個人勝出。算出最少的步數與贏家是個 NP-hard 問題

規則	運作方式	優點	缺點
Borda Count	依名次給分，總分最高者勝	選出大家都能接受的折衷選項	受無關選項影響；易被策略投票操弄
相對多數決	每人投一票，最高票者勝	簡單好懂	分票，可能選出多數人最討厭的
多輪投票制	沒人過半時，前兩名再投一輪	減少分票	成本高；折衷選項可能先被淘汰
否決制	有人否決就拿掉，全被否決則維持現狀	保障少數	偏向現狀，容易僵局
孔多塞法	兩兩對決，全勝者勝出	贏家一對一都有過半支持	可能出現循環，沒有贏家
Dodgson	對調排名次數最少就能成為孔多塞贏家者勝	處理孔多塞悖論	NP-hard，難計算

阿羅不可能定理

阿羅（Kenneth Arrow）證明了當候選人 3 個以上時，不存在任何一個投票制度能同時滿足以下 4 個條件：

• Non-Dictatorship：不能有任何一個人的喜好直接決定最終結果
• Pareto Efficiency：如果所有人一致認為 $A > B$，那集體結果必須是 $A > B$
• Independence of Irrelevant Alternatives：$A$ 和 $B$ 的相對排名，只取決於選民對 $A$ 和 $B$ 的偏好，不應該受到第三者 $C$ 出現或退選的干擾
• Unrestricted Domain：選民可以任意排列自己的喜好，制度都必須能處理

跟 May's Theorem 的三個條件一樣，這四個條件是多個選擇的情況下，人們能想到對於公平最通用的詮釋

阿羅定理說明完美的公平在邏輯上是不存在的。所有集體做出的選擇，即使個人的偏好不變，在不同規則下就會出現不同結果，並且伴隨著一定的 trade-off

Manipulation、Strategyproof 與 2000 年台灣總統大選

Strategyproof（SP）的意思是投票者沒辦法透過不誠實（違反自己偏好）的選擇獲得較好的結果。研究制度怎麼設計的學者，夢寐以求的就是設計出一個 SP 的制度。然而 Gibbard-Satterthwaite Theorem 證明了「當候選人有 3 個以上時，世界上不存在任何一個非獨裁，又滿足 SP 的投票系統」

Plurality 可以操作棄保效應，Borda 就更不用說了，手上能給的選擇一多，能說謊的空間就更大

事實上 Dodgson 本人就不喜歡 Borda 法與 Plurality，而 Borda 自己也說「My scheme is intended only for honest men」

來看一個 case。2000 年台灣總統大選，是中國國民黨連戰、民主進步黨陳水扁、無黨籍宋楚瑜的三腳督局面，最終得票率為陳水扁 39.3%、宋楚瑜 36.84%、連戰 23.1%，由陳水扁當選

宋楚瑜身為台灣省長，原本上位呼聲極高，但李登輝與他切割之後他脫黨參選，國民黨則推出連戰參選。宋連二人屬於泛藍陣營，加起來有近 60% 的票，但這次分裂還是造成連宋相爭、阿扁得利的局面

宋楚瑜在此次選舉很可能是孔多塞贏家（宋 vs 扁是宋贏、宋 vs 連也是宋贏），卻吃了 Plurality 的虧。既然 Plurality 沒有辦法推出一個孔多塞贏家，為什麼還要用？原因大概有以下幾個：

1. 這次選舉其實有五個參選人（還有李敖跟許信良），用 Condorcet 法的話要排出五人排序，比較麻煩
2. 除了比較麻煩以外，由於規則較複雜且不一目了然，一旦有心人士操作陰謀論，對社會秩序和信任會是一種傷害
3. 即使候選人只有三組，也難保不會出現孔多塞悖論

對於第 3 點，可能會有人說「那如果先跑一次 Condorcet 法，出現悖論的話再退回 Plurality 或 Borda 不行嗎？」

這個想法有個名字叫做 Black's Method。然而這樣做依然行不通，因為泛綠陣營可以透過不誠實的投票使第一輪出現孔多塞悖論，硬是將投票拖到第二輪，這樣也選不出孔多塞贏家

• 如果 2000 年採用 Black's Method：陳水扁陣營最有動機發動策略性投票（因為誠實投票必輸）
• 如果綠營發動策略成功且退回 Plurality $\implies$ 陳水扁贏
• 如果綠營發動策略但退回 Borda Count $\implies$ 連戰勝率較高，但 Borda 仍面臨被操弄的風險
• 如果選民全部誠實投票 $\implies$ 宋楚瑜當選

這種將幾種方式拼在一起誕生的新投票方式，依然逃不出阿羅不可能定理與 Gibbard-Satterthwaite 定理

三個以上選項卻有全體意志的情況：Single-Peaked Preference

如果選項之間有一個特定的空間結構，例如位置、大小、高低、光譜，且選民的偏好呈現「單峰偏好（Single-Peaked Preference）」，也就是每人有一個最偏好的選項，距離此選項越遠偏好就遞減，此時理論上的全體意志就會存在

例如有三個人想決定一次旅行的價位，A 偏好 10 萬元、B 偏好 20 萬元、C 偏好 30 萬元，各自偏好的金額差越多滿意度就越低，這就是 Single-Peaked Preference

Single-Peaked Preference 可以保證孔多塞悖論不會出現，並且此時中位數選民（Median Voter）的偏好，會自動成為孔多塞贏家，這件事稱為中位數選民定理（Median Voter Theorem）

現實應用：假設選民偏好的候選人或政見可以被畫在一個一維的光譜上，在單峰偏好的前提下，只要候選人或政黨想贏得選舉，他們就會不斷向光譜正中間的「中位數選民」靠攏（這也是為什麼兩黨制或多黨民主國家的政黨政見常趨於同質化、打中間牌）

總結

社會選擇理論告訴我們完美的投票制度不存在，且集體決策是件困難的事。即使理論上完美的公平難以達成，現實生活中也有許多額外的因素是必須考慮的，因此我們不會濫用 Plurality 犧牲少數人的權利，也不會執著於用孔多塞贏家當最佳解。投票制度不是關於找到完美的解，而是一套充滿調整與妥協的系統。理解演算法的局限、權衡賽局的利弊、在效率與正義之間找到當下的平衡點，是在社會中生活的我們該思考的事

Reference

• Dr. Hsu-Chun Hsiao
• 菜市場政治學
• A Set of Independent Necessary and Sufficient Conditions for Simple Majority Decision
• A Difficulty in the Concept of Social Welfare
• Strategy-proofness and Arrow's Conditions
• Voting Schemes for Which It Can Be Difficult to Tell Who Won the Election
• 2000 年中華民國總統選舉

Appendix：獵人協會會長選舉

在冨樫義博的漫畫作品《HUNTER×HUNTER》中，尼特羅會長死後留下遺言，下任會長由全體獵人投票選出，投票率沒有達到 95% 就作廢重投。十二支用抽籤決定細節，抽中的是金寫的四條規則：

1. 661 名獵人全都是選民，也全都是候選人
2. 第一輪沒有人過半，就由前 16 名進入下一輪，之後每輪砍半（16 → 8 → 4 → 2），直到有人過半
3. 投票率未達 95%，該輪作廢重投
4. 記名投票

不能棄權不能匿名的多輪投票制，最後投了 9 輪才結束

金：洞悉規則，決定 $F$ 的人

• 95% 門檻：只要超過 5% 的人不投票就整輪作廢，選舉隨時可能卡死，比的是誰能把不想投票的人逼出來
• 記名投票：等於取消了秘密投票，每個人的立場都攤在陽光下，棄保、施壓、派系綁票都能被看見
• 轉移注意力：用最後一條誇張的規則轉移十二支的注意力，掩蓋自己操作規則的事實

選舉的結果再次揭示全體意志並不存在，因為規則是金訂的，結果也跟他想得差不多

帕里斯通：實力強大的亂源候選人

帕里斯通有大批忠於他的協專獵人，第一輪就拿下近 4 成的票，之後一路領先

他常常做對自己不利的事，例如提議沒投票的人要暫時沒收執照，結果棄權的人反而變多，投票率遲遲過不了 95%，選舉一拖再拖，耗盡反對派（綺多、米才伊史多姆等人）的體力，而他的目的只是為了找樂子

雷歐力：以情緒號召選票，沒包袱的黑馬

雷歐力當著所有獵人的面揍了金一拳，氣他不去探望重傷的兒子小傑。影片傳開後，他的票數一口氣衝到前幾名，成為第八輪的贏家，一度威脅到帕里斯通

他沒政見沒組織，只是想救小傑，代表的是一種純粹的情緒投票：選民投給他來表達對某件事的憤怒或認同。這種票來得快去得也快，小傑康復回到會場後他退出選舉，使帕里斯通再度掌控局面

綺多：沒生存空間的中間派

穩健治理、沒什麼心機的十二支。她一路排在前幾名，但票數一直只有帕里斯通的零頭：既沒有帕里斯通的組織票，也沒有雷歐力的情緒號召，這是傳統中間派被極端陣營擠壓的悲劇

為了擋下最討厭的人，她決定啟用棄保支持雷歐力當選

結局：不在乎輸贏的人

帕里斯通當選後，當場任命綺多為副會長，然後立刻辭職，綺多成為第 14 任會長

綺多跟十二支在乎的是選舉勝負與協會權力，帕里斯通在乎的是遊戲本身。當大家在算票數、算棄保時，他要證明自己能掌控這套系統，再把治理協會的麻煩丟回給綺多

所有投票演算法都有一個隱含的假設：候選人想贏。一旦遇到不在乎結果的玩家，演算法能決定誰拿最多票，卻決定不了接下來會發生什麼