老應書齋
讀書筆記，好文摘抄，精彩轉貼，研究材料，參考文獻。
由於某些原因，最近在整理以前的日誌。偶然翻到這篇日誌時，順便在 Wikipedia 複習了一下 Arrow 不可能性定理的證明，驚奇地發現這個定理的證明過程非常困難但又非常初等，是一個門檻很低、老少鹹宜的思維遊戲。雖然不少人都翻譯過 Wikipedia 上的這段證明，但我也想自己寫一個自己的理解，一來做個筆記，二來也鍛煉一下自己的表達能力。
Arrow 不可能性定理是一個與選舉製度有關的定理。選舉製度，說穿了就是把所有選民的意見綜合成一個全體意見的算法。選民的意見，無非是候選對象在心目中誰優誰劣，完整地反應在選票上，就是候選對象們從優到劣的一個順序；形式最完整的全體意見，也就是候選對象的這麽一個排列。因此，我們可以把整個選舉製度想像成一個函數，輸入 n 個排列（相當於 n 張選票），將會輸出一個排列（相當於選舉結果）。對輸入數據的任何一處小改變，都有可能導致輸出結果隨之變化。作為一個合理的選舉製度，它必須滿足一些起碼的要求。我們提出兩個最基本的選舉製度要求：
1. 如果每張選票都認為 X 比 Y 好，那麽投票結果中 X 的排名也必須比 Y 更靠前；
2. 如果每張選票中 X 、 Y 的相對排名都不改變，那麽投票結果中 X 和 Y 誰先誰後也不能變。
我們將證明，同時滿足上述兩個條件的選舉製度隻有一種，就是選舉結果唯一地由其中某個選民的選票決定。也就是說，獨裁是唯一一種完美的選舉製度。為了簡便起見，讓我們假設候選人隻有 A 、 B 、 C 三個人。你會發現，下麵的證明過程很容易擴展到多個人的情況。
假設每張選票都把 B 放在最後一名。也就是說，每張選票都認為， A 比 B 好， C 也比 B 好。根據條件 1 ，最終投票結果中也應該滿足， A 和 C 都排在 B 前麵。也就是說，投票結果裏 B 也是最後一名。現在，讓我們按照一定的順序依次把每張選票裏的 B 從最後一名挪到第一名的位置上去，同時不斷關注在改票過程中選舉結果的變化。當所有的票都改完了後，根據同樣的道理，投票結果中 B 自然就排到了第一名。因此，在改票的過程中，一定存在這麽一個人，改完他的選票後，投票結果中 B 的名次靠前了（從最後一名升了上來）。我們把這張選票叫做“樞紐選票”。
接下來的證明分成四個大步驟。我們第一步要證明的就是，在改票過程中，改完這張樞紐選票，投票結果中 B 的名次將會直接從最後一名一下子升到第一名。反證，假如此時 B 沒有跑到投票結果的第一名去，那麽投票結果要麽是 A 、 B 、 C ，要麽是 C 、 B 、 A 。不妨假設是 A 、 B 、 C 吧。現在，把每張選票中 C 的名次都改到 A 前麵（ C 本來就在 A 前麵的那些選票就不用改了）。按照條件 1 ，最後的結果裏 C 也應該跑到 A 的前麵去。但同時，由於此時每張選票都把 B 列於第一名或者最後一名，調整 A 和 C 的順序不可能影響到 B 、 A 之間的相對順序，以及 B 、 C 之間的相對順序，因此由條件 2 ，結果裏 B 、 A 的相對排名和 B 、 C 的相對排名是不能變的。這就矛盾了：我們絕不可能在不改變 B 、 A 的相對位置以及 B 、 C 的相對位置的情況下，把投票結果 A 、 B 、 C 裏 A 和 C 的位置互換。因此，把那張樞紐選票中的 B 提到第一名，一定讓投票結果中的 B 也直接跑到了第一名去。
注意，樞紐選票的產生是有前提的：它要從某個滿足“每張選票裏 B 都排最後”的情形開始，再按照一定的順序把選票裏的 B 都改成第一名，在此過程中才能產生對應的樞紐選票。如果具體的初始情形不一樣，樞紐選票還一樣嗎？答案是肯定的。在第二步，我們要證明的就是，隻要滿足每張選票都把 B 放在最後一名（不管選票的具體內容是什麽），並且按照同樣的順序進行改票，樞紐選票總會是同一張。
這個原因很簡單，關鍵就在於，我們總是把每張選票裏的 B 從最後一名提到第一名。即使換一個不一樣的初始情形，在改票過程的每一個時刻，每張選票裏 B 和 A 、 B 和 C 之間的相對排名也都和原來一樣，因而投票結果中 B 和 A 、 B 和 C 之間的相對排名也和原來一樣。因此，投票結果裏 B 的位置仍然會在同一個時候發生變化，樞紐選票還是同一張。
在第三步裏，我們要證明的是，這張樞紐選票有一個非常牛的性質：在任何情形下，它都能獨裁 A 、 C 之間的相對排名。也就是說，這張樞紐選票認為 A 比 C 好，投票結果裏 A 就一定比 C 好；反過來，它說 C 比 A 好，投票結果裏 C 就比 A 好；並且此性質不依賴於任何前提條件，即使 B 不在各選票中的特殊位置，結論同樣也成立。現在，我們就考慮任意一組選票，無妨假設其中樞紐選票裏 A 比 C 靠前，我們將證明投票結果中 A 也是排在 C 前麵的。證明的思路是，對各選票進行一係列不涉及 A 、 C 間相對排名的修改，從而看出投票結果裏 A 在 C 前麵。我們先把所有選票中的 B 都排到最後一位去，注意，這一步不會改變投票結果中 A 、 C 的先後順序，但卻讓前麵的結論得以適用。然後，我們把樞紐選票之前的所有票裏 B 的位置都挪到最前麵，由前麵的結論，結果中的 B 仍然處於最後一位（因而 A 位於 B 前麵）。接下來，我們把樞紐選票（它應該是 A 、 C 、 B 的順序）改成 A 、 B 、 C ，由於這張票中 A 、 B 的相對位置沒變，因此結果中 A 、 B 的相對位置也沒變， A 仍然在 B 前麵。接下來，我們把樞紐選票改成 B 、 A 、 C ，由前麵的結論，此時結果裏的 B 跑到了最前麵（因而排到了 C 前麵），但把樞紐選票從 A 、 B 、 C 改成 B 、 A 、 C 時並沒有改變 B 和 C 的相對位置，因此剛才的投票結果中 B 也應該在 C 的前麵。也就是說，樞紐選票是 A 、 B 、 C 時，投票結果裏 A 在 B 前， B 在 C 前，也就是說 A 排在 C 前麵。但上述所有修改都不會改變任何一張選票裏 A 、 C 的相對排名，因此投票結果中 A 其實自始至終都在 C 前麵。這就證明了，投票結果裏 A 、 C 的相對排名完全取決於這張樞紐選票，不管其它選票是什麽樣的。
最後一步證明就是，這張選票不但獨裁了 A 、 C 的相對排名，它直接獨裁了所有人的排名。原因很簡單：按照之前的推理，還會有一張獨裁 A 、 B 相對排名的選票，另外還有一張獨裁 B 、 C 相對排名的選票；但一山不容二虎，這三個獨裁者隻能是同一個人，否則一個人說左一個人說右，就會立即產生矛盾。具體地說，首先，這三個獨裁者肯定不可能是三個不同的人，否則 A 、 B 的獨裁者說 A 比 B 好， B 、 C 的獨裁者說 B 比 C 好， A 、 C 的獨裁者說 C 比 A 好，投票結果就得同時滿足 A 在 B 前、 B 在 C 前、 C 在 A 前，這是不可能的。這三個獨裁者也不可能是兩個人。比方說其中一人同時獨裁了 A 、 B 和 A 、 C ，另一人則隻獨裁 B 、 C ，那麽如果前者說 B 在 A 前麵， A 在 C 前麵，後者又說 C 在 B 前麵，同樣不會有兼顧兩者的投票結果。因此，獨裁者隻能有一個，它就是填寫樞紐選票的那個人。
至此，我們就證明了，滿足那兩個基本條件的選舉製度隻有一種——獨裁製度。
上述結論有另外一種等價的表述方法：同時滿足全體一致性、無關候選人獨立性（就是那兩個基本條件）以及非獨裁性這三個條件的選舉製度理論上是不存在的。這就是美國經濟學家 Kenneth Arrow 提出的 Arrow 不可能性定理：不存在完美的選舉製度。
Three Brief Proofs of Arrow's Impossibility Theorem
http://wenku.baidu.com/view/0577c1222f60ddccda38a02d.html
下麵的內容謫自MBA智庫百科《阿羅的不可能定理》
http://wiki.mbalib.com/wiki/%E9%98%BF%E7%BD%97%E7%9A%84%E4%B8%8D%E5%8F%AF%E8%83%BD%E5%AE%9A%E7%90%86
阿羅的不可能定理一經問世便對當時的政治哲學和福利經濟學產生了巨大的衝擊，甚至招來了上百篇文章對他的定理的駁斥。李特爾、薩繆爾森試圖以與福利經濟學不相幹的論點來駁倒阿羅的不可能定理，但又遭到肯普、黃有光和帕克斯的反駁，他們甚至建立了在給定個人次序情況下的不可能性結果。
一個更完整、更簡單也更具一般意義的不可能性定理，是艾利亞斯在2004年發表的。這一定理聲稱：如果有多於兩個可供選擇的社會狀態，那麽，任何社會集結算子，隻要滿足“偏好逆轉”假設和“弱帕累托”假設，就必定是獨裁的。特別地，阿羅的社會福利函數和森的社會選擇函數，都是社會集結算子的特例，並且偏好逆轉假設在阿羅和繆勒各自定義的社會選擇框架內分別等價於阿羅的“獨立性假設”和繆勒的“單調性假設”，從而阿羅的不可能性定理、森的最小自由與帕累托效率兼容的不可能性定理、繆勒和塞特斯維特的一般不可能性定理，均可視為艾利亞斯一般不可能性定理的特例。艾利亞斯的不可能性定理有怎樣的經濟學和社會學結論是人們正在研究的問題。
Proof of Arrow’s Impossibility Theorem
From: J. Kelly, Social Choice Theory: An Introduction
http://www.tulane.edu/~dnelson/COURSES/IntroPE/arrow.pdf