吉伯德-薩特思韋特防策略不可能性定理的邏輯初探

孫　雯,杜國平

(1.中國社會科學院 哲學研究所，北京　100732； 2.河北師范大學 馬克思主義學院，石家莊　050024)

?

吉伯德-薩特思韋特防策略不可能性定理的邏輯初探

孫雯1,2,杜國平1

(1.中國社會科學院 哲學研究所，北京100732； 2.河北師范大學 馬克思主義學院，石家莊050024)

摘要：自20世紀70年代吉伯德-薩特思韋特防策略不可能性定理確立后，引起了數學、經濟學、計算機科學和哲學等諸多領域中學者的廣泛關注。然而，在國內外文獻中，對吉伯德-薩特思韋特防策略不可能性定理的邏輯研究還比較少。基于此，借助公理化的方法探討吉伯德-薩特思韋特防策略不可能性定理，并形式化地給出定理的內容和證明，力圖把精細的邏輯推理應用于復雜的過程分析中，使防策略投票這一過程形式化、清晰化，以期能指導人們進行合理、有效的決策活動。

關鍵詞：吉伯德-薩特思韋特防策略不可能性定理；邏輯形式化；社會選擇

一、對公平投票的質疑：吉伯德-薩特思韋特防策略不可能性定理

19世紀后期，投票選舉理論的奠基人之一道奇森(Dodgson)就關注于對投票規則的研究，認為人們在投票時的行為更傾向于策略投票。在現代社會中，從村民自治選舉到舉國參與的總統選舉，投票在社會生活中被廣泛地應用。然而，在投票選舉的過程中，用社會選擇規則集結的個人偏好都是個人所表達出來的偏好，而不一定是其真實偏好。在正常情況下，個人的表達偏好與其真實偏好應該是一致的，但不排除在某些特殊情況下，個人出于某種目的而謊報自己的真實偏好，使決策結果發生有利于自己的變化，這就是所謂的“策略投票”。策略投票使得選舉結果并不能體現人們的真實意愿，這嚴重影響了公眾的權利。因此，防止策略投票操縱選舉結果，也即“防策略”就顯得尤為重要。從直觀上講，防止策略投票就是要求投票者不能從謊報他們的偏好中獲益，進而可以抑制社會選擇中的策略投票，促使投票者都投出自己的真實選票，從而使選舉結果體現人們的真實意愿，以充分保障社會的公平和正義。

20世紀50年代，諾貝爾經濟學獎得主肯尼斯·約瑟夫·阿羅(Kenneth J.Arrow)對投票選舉方式做了更深入的研究，提出了著名的阿羅不可能性定理。阿羅將社會選擇問題劃歸為尋找一個合理的將個人偏好聚合為集體選擇的法則，也稱之為社會福利函數。他指出，社會福利函數在滿足一些合理性條件的前提下將不存在，這被稱為“阿羅不可能定理”。具體來講，社會福利函數應滿足無限制定義域(unrestricted domain)、無關選項相獨立(independence of irrelevant alternatives)、帕累托最優原則(Pareto principle)與無獨裁者(Non-dictator)4個條件。但是，當有3個或更多候選人時，滿足這些條件的任何理性群體決策將不存在。可見，隨著候選人和投票者的增加，“程序民主”必將越來越遠離“實質民主”。

在實際的社會選擇中，個人的表達偏好常常與其真實偏好不一致，在有策略行為存在的情況下，再沿用阿羅不可能性定理的形式來描述社會選擇問題顯然已不準確。20世紀70年代，在阿羅定理的基礎上，阿蘭·吉伯德(Allan Gibbard)和馬克·薩特思韋特(Mark Satterthwaite)提出了吉伯德-薩特思韋特(Gibbard-Satterthwaite)防策略投票不可能性定理，證明了當存在3個或更多候選人時，任何合理的投票系統都可以被操縱。換句話說，總是存在讓投票者通過投出一個非真實意愿的選票而受益的可能。吉伯德-薩特思韋特防策略不可能性定理證明了策略投票的必然性，這在理論界引起了很大的震動，特別是對經濟領域資源合理配置理論的存在性和合理性提出了巨大的挑戰。

吉伯德-薩特思韋特防策略不可能性定理在西方經濟學理論，特別是社會選擇理論中有著十分重要的地位和意義。在過去的30年里，國外許多學者從經濟學和數學的角度對吉伯德-薩特思韋特防策略不可能性定理進行分析，G?rdenfors[1]、Schmeidler、Sonnenschein[2]、Barberá[3]、Benoit[4]、Arunava Sen[5]和Tayor[6]都對這個定理進行過證明。本文使用邏輯形式化的方法來深入探討吉伯德-薩特思韋特防策略不可能性定理，這對于讀者理解定理的內容和證明，具有重要的意義。同時，對于國內哲學和邏輯工作者而言也有重要的參考價值。

二、吉伯德-薩特思韋特防策略不可能性定理的內容

首先，我們使用集合論和相關邏輯語言來描述吉伯德-薩特思韋特防策略投票不可能性定理的基本思想。

定義1.1集合A上的二元關系R：

自反性 —— ?x∈A

xRx

非自反性 —— ?x∈A

﹁(xRx)

對稱性 —— ?x,y∈A

如果xRy，那么yRx

非對稱性 —— ?x,y∈A

如果xRy，那么﹁(yRx)

反對稱性 —— ?x,y∈A

如果xRy并且yRx，那么x=y

傳遞性 —— ?x,y,z∈A

如果xRy并且yRz，那么xRz

完全性 —— ?x,y∈A

或者xRy或者yRx

定義1.2(弱序)如果R具有傳遞性和完全性，那么集合A上的二元關系R是一個弱序(weak ordering)。

定義1.3(線性序)如果具有傳遞性、完全性、反對稱性，那么集合A上的二元關系R是一個線性序(linear ordering)。

如果R是A的一個弱序，那么R是完全的就表示R也是自返的。直覺上，一個弱序就表示有平局的情況，xRy可以解釋為x至少像y一樣好。一個線性序就沒有平局的情況。xRy解釋為或者x=y或者x優于y。

定義1.4R是A上的一個弱序，有偏好(strict preference)P和無差異(indifference)I， 即xPy?﹁(yRx)，xIy?xRy∧yRx。Pi和Ii指第i個投票者的偏好和無差異性。如果R是A的一個弱序，那么關系I就表示相等，關系P就表示A的一個線性序。

如果P是一個(A,n)-斷面，那么P可以寫作〈P1,…,Rn〉,也可以表示為(?1,…,?n)。Ri(或?i)是第i個投票者的選票，表示“投票者i想要的或喜愛的”。

定義1.6設A是一個非空集合，由A的所有子集組成的集合叫做A的冪集，記作ρ(A)，即ρ(A)={x|x?A}。

P(A)是所有(A,n)-斷面的集合，對于n∈Ν，函數V:P(A)→A是A的一個單值投票規則(resolutevotingrule)。函數V:P(A)→ρ+(A)是A的一個投票規則(votingrule)。函數V:P(A)→ρ+(A)→ρ+(A)，且V(P)(v)?v，是A的一個社會選擇函數(socialchoicefunction)。函數V:P(A)→ord(A)，是A的一個社會福利函數(socialwelfarefunction)。

定義1.7(防策略)令P～iP′：表示P和P′僅在投票者i的選票中不同。如果P～iP′，則V(P)iV(P′)，那么單值投票規則V是防策略(strategy-proof)或防操縱的(non-manipulable)，簡寫為NM)。

定義1.8(非強加)如果?a∈A?P∶a∈V(P)，那么投票規則V是非強加的(non-imposed，簡記為NI)。這意味著任意候選人都可以成為獲勝者。

定義1.9(獨裁的)如果存在某些k，使得V:P(A)→A，且映射任意P到?k排序的頂端，那么單值投票規則V是獨裁的(dictatorship)。

定義1.10(有效的)對于V和P，如果存在某些P′，具有P～iP′且V(P)≠V(P′)，那么這個投票者i是有效的(effective)。

在上述準備的基礎上，著名的“吉伯德-薩特思韋特防策略投票不可能性定理”可以表示為：

定理1.1(吉伯德-薩特思韋特防策略投票不可能性定理)

在線性投票的情況下，n是一個正整數，A是3個或3個以上候選人的集合，若對于(A,n)的任意單值投票規則是防策略(NM)的和非強加(NI)的，則必存在獨裁[7]。

三、吉伯德-薩特思韋特防策略不可能性定理的證明

吉伯德-薩特思韋特防策略投票不可能性定理是社會選擇理論和實施理論中具有標志性的成果，是防策略投票理論的基石。吉伯德-薩特思韋特防策略投票不可能性定理也是比較復雜的，因此它的證明顯得尤為重要。吉伯德-薩特思韋特防策略投票不可能性定理有很多證明方法，Saari方法是目前較新的方法，該證明不僅在數學上十分完美，而且在經濟學與社會選擇理論上更有意義[8]。下面將在第一部分工作的基礎上，運用邏輯形式化的證明方法給出吉伯德-薩特思韋特防策略投票不可能性定理證明的基本思路。

引理2.1(過渡引理)如果V是NM，那么V有CP。

引理2.2(有效引理)如果V是NM并且NI，i對于P是有效的，那么在P中，V(P)是i-選票的頂端。

證明：假設V是NM并且NI，那么通過過渡引理，V有CP。

假定對于P來說，i有效。那么V(P)ix，其中x是在P中i投票的頂端。

因為i是有效的，存在意向表P′，其中P～iP′并且V(P)≠V(P′)。由NM，得到V(P)iV(P′)。

我們也可以這樣看，在Q中，i最喜歡的候選人是x。現在令所有其他投票者改變他們的投票，依次地，通過向上移動x，不改變y和z的順序。那么通過NI，存在j,R,R1，有R≈jR1，V(R)=V(Q)=y，并且V(R1)=x。

假定i在R中無效，在R中，令R′是改變i-選票從xyz到xzy的結果。在Q中，令Q′是改變i-選票從xyz到xzy的結果。那么V(Q′)=z，V(R′)=y。這與CP矛盾。對于R′可以通過毗鄰換位改變選票到達Q′，并且不影響y和z的相關順序，所以i在R中是有效的。

可見，在這兩個示例中，下面的一行都和CP有矛盾：通過向左移動，i可以操縱下行右邊的選票。得證。

定理1.1 (吉伯德-薩特思韋特防策略投票不可能性定理)在線性投票的情況下，n是一個正整數，A是3個或3個以上候選人的集合，若對于(A,n)的任意單值投票規則是防策略(NM)的和非強加(NI)的，則必存在獨裁[7]。

證明：令V是一個單值投票規則，并且是NM和NI，通過NI，使得i對于P是有效的。假設存在另一個對于P的有效投票者j。通過有效引理，對于每個P′，P～iP′，i決定投票。并且對于每個P″，P～jP″，j決定投票。

令Q是i和j改變他們選票的結果，i對應它的選票P′，j對應它的選票P″。那么，如下所示：

假定V(Q)≠V(P′)，那么在P′中，j是有效的。通過有效引理，在P′中，V(P′)應該等價于j的偏愛，但是并非如此。因此V(Q)=V(P′)。相似地，在P″中，i是有效的。通過有效引理，在P″中，V(P″)應該等價于i的偏愛，但是并非如此。矛盾。

對于P來說，i是唯一有效的投票者。令R是任意的意向表，R0是所有投票者的結果，除了i改變他們的選票P為選票R，這個投票并沒有改變，并且在R0中，i仍是唯一的有效投票者。從而得到，在R中，i決定投票的結果。所以，對于任意的意向表，i是唯一有效的投票者，因此，i是獨裁者。

四、結語

通過邏輯形式化的方法，來刻畫吉伯德-薩特思韋特防策略投票不可能性定理，這對于讀者認識和理解社會選擇中的策略投票提供了一個十分重要的分析視角。更富有啟發性的是，將社會選擇理論中的吉伯德-薩特思韋特防策略投票不可能性定理，轉化為一個純形式化的表達，構建了和自動推理的聯系，以期最終實現定理的機器自動證明，這也是邏輯作為工具應用到社會選擇中的重要價值。另一方面，吉伯德-薩特思韋特防策略不可能性定理中存在著很多精細的問題，它們為邏輯提供了一個很好的直觀來源和分析舞臺。對此，目前國外學者的更進一步的想法是采用更具表達力的形式化工具，來進一步形式化投票變化過程，以展示某些情境下的精細結構。可見，社會選擇中的投票互動及其變化的復雜性反過來又可以為形式化本身的研究提供思想源泉，從而激發邏輯的進一步發展，促其產生新的邏輯分支和分析工具。因此，從一個學科的角度去研究另一個學科的理論，用一個學科中的方法來研究另一個學科中的問題，最終完美地刻畫和解決策略投票問題，這在今天具有重要的理論意義和現實意義。

參考文獻：

[1]GRDENFORSP.Aconciseproofoftheoremonmanipulationofsocialchoicefunctions[J].Publicchoice,1977,32:137-142.

[2]SCHMEIDLERD,SONNENSCHEINH.Twoproofsofthegibbard-satterthwaitetheoremonthepossibilityofastrategy-proofsocialchoicefunction[J].Decisiontheoryandsocialethicstheoryanddecisionlibrary,1978,17:227-234.

[3]BARBERS.Strategy-proofnessandpivotalvoters:adirectproofofthegibbard-satterthwaitetheorem[J].Internationaleconomicreview,1983,24(2):413-417.

[4]BENOITJ.Thegibbard-satterthwaitetheorem:asimpleproof[J].Economicletters,2000,69:319-322.

[5]SENA.Anotherdirectproofofthegibbard-satterthwaitetheorem[J].Economicletters,2001,70(3):81-385.

[6]TAYLORAD.Themanipulabilityofvotingsystems[J].TheAmericanmathematicalmonthly,2002,109(4):321-337.

[7]TAYLORAD.Socialchoiceandthemathematicsofmanipulation[M].Cambridge:Cambridgeuniversitypress,2005:61.

[8]VANEIJCKJ.Ageometriclookatmanipulation[M].Computationallogicinmulti-agentsystems,lecturenotesinartificialintelligence,editedbyJ.Leiteetal,2011:92-104.

(責任編輯張佑法)

Preliminary Study on Logic of Gibbard-Satterthwaite Strategy-Proof Impossibility Theorem

SUN Wen1, 2, DU Guo-ping1

(1.Institute of Philosophy, Chinese Academy of Social Sciences, Beijing 100732, China;2.College of Marxism, Hebei Normal University, Shijiazhuang 050024, China)

Abstract:Since Gibbard-Satterthwaite strategy-proof impossibility theorem was established in the 1970s, it has drawn the widespread attention of scholars in fields of mathematics, economics, computer science and philosophy. However, it is seldom found the research on logics of the Gibbard-Satterthwaite theorem. This paper discussed Gibbard-Satterthwaite strategy-proof impossibility theorem with the axiomatic method, and elaborated the content and proving process of this theorem formally. It is trying to apply the fine logical reasoning to the complex processes analysis to make the strategy-proof voting process more formal and clear, hoping to guide people to make rational and effective decision-making activities.

Key words：Gibbard-Satterthwaite strategy-proofness impossibility theorem; logic formalization; social choice

中圖分類號：B81

文獻標識碼：A

文章編號：1674-8425(2016)03-0013-05

作者簡介：孫雯(1982—)，女，河北石家莊人，河北師范大學馬克思主義學院講師，哲學博士，中國社會科學院哲學研究所博士后，研究方向：現代邏輯。

基金項目：國家社會科學基金重大項目“應用邏輯與邏輯應用研究”(14ZDB014)；河北師范大學人文社會科學基金項目“基于多主體策略邏輯的防操縱研究”(S2014809)

收稿日期：2015-10-09

doi:10.3969/j.issn.1674-8425(s).2016.03.003

引用格式：孫雯,杜國平.吉伯德-薩特思韋特防策略不可能性定理的邏輯初探[J].重慶理工大學學報(社會科學)，2016(3):13-17.

Citation format：SUN Wen, DU Guo-ping.Preliminary Study on Logic of Gibbard-Satterthwaite Strategy-Proof Impossibility Theorem[J].Journal of Chongqing University of Technology(Social Science)，2016(3):13-17.