孫　雯,杜國(guó)平

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

?

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

孫雯1,2,杜國(guó)平1

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

摘要：自20世紀(jì)70年代吉伯德-薩特思韋特防策略不可能性定理確立后，引起了數(shù)學(xué)、經(jīng)濟(jì)學(xué)、計(jì)算機(jī)科學(xué)和哲學(xué)等諸多領(lǐng)域中學(xué)者的廣泛關(guān)注。然而，在國(guó)內(nèi)外文獻(xiàn)中，對(duì)吉伯德-薩特思韋特防策略不可能性定理的邏輯研究還比較少?；诖?，借助公理化的方法探討吉伯德-薩特思韋特防策略不可能性定理，并形式化地給出定理的內(nèi)容和證明，力圖把精細(xì)的邏輯推理應(yīng)用于復(fù)雜的過(guò)程分析中，使防策略投票這一過(guò)程形式化、清晰化，以期能指導(dǎo)人們進(jìn)行合理、有效的決策活動(dòng)。

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

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

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

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

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

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

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

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

定義1.1集合A上的二元關(guān)系R：

自反性 —— ?x∈A

xRx

非自反性 —— ?x∈A

﹁(xRx)

對(duì)稱(chēng)性 —— ?x,y∈A

如果xRy，那么yRx

非對(duì)稱(chēng)性 —— ?x,y∈A

如果xRy，那么﹁(yRx)

反對(duì)稱(chēng)性 —— ?x,y∈A

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

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

如果xRy并且yRz，那么xRz

完全性 —— ?x,y∈A

或者xRy或者yRx

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

定義1.3(線性序)如果具有傳遞性、完全性、反對(duì)稱(chēng)性，那么集合A上的二元關(guān)系R是一個(gè)線性序(linear ordering)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

證明：假設(shè)V是NM并且NI，那么通過(guò)過(guò)渡引理，V有CP。

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

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

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

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

可見(jiàn)，在這兩個(gè)示例中，下面的一行都和CP有矛盾：通過(guò)向左移動(dòng)，i可以操縱下行右邊的選票。得證。

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

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

令Q是i和j改變他們選票的結(jié)果，i對(duì)應(yīng)它的選票P(pán)′，j對(duì)應(yīng)它的選票P(pán)″。那么，如下所示：

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

對(duì)于P來(lái)說(shuō)，i是唯一有效的投票者。令R是任意的意向表，R0是所有投票者的結(jié)果，除了i改變他們的選票P(pán)為選票R，這個(gè)投票并沒(méi)有改變，并且在R0中，i仍是唯一的有效投票者。從而得到，在R中，i決定投票的結(jié)果。所以，對(duì)于任意的意向表，i是唯一有效的投票者，因此，i是獨(dú)裁者。

四、結(jié)語(yǔ)

通過(guò)邏輯形式化的方法，來(lái)刻畫(huà)吉伯德-薩特思韋特防策略投票不可能性定理，這對(duì)于讀者認(rèn)識(shí)和理解社會(huì)選擇中的策略投票提供了一個(gè)十分重要的分析視角。更富有啟發(fā)性的是，將社會(huì)選擇理論中的吉伯德-薩特思韋特防策略投票不可能性定理，轉(zhuǎn)化為一個(gè)純形式化的表達(dá)，構(gòu)建了和自動(dòng)推理的聯(lián)系，以期最終實(shí)現(xiàn)定理的機(jī)器自動(dòng)證明，這也是邏輯作為工具應(yīng)用到社會(huì)選擇中的重要價(jià)值。另一方面，吉伯德-薩特思韋特防策略不可能性定理中存在著很多精細(xì)的問(wèn)題，它們?yōu)檫壿嬏峁┝艘粋€(gè)很好的直觀來(lái)源和分析舞臺(tái)。對(duì)此，目前國(guó)外學(xué)者的更進(jìn)一步的想法是采用更具表達(dá)力的形式化工具，來(lái)進(jìn)一步形式化投票變化過(guò)程，以展示某些情境下的精細(xì)結(jié)構(gòu)。可見(jiàn)，社會(huì)選擇中的投票互動(dòng)及其變化的復(fù)雜性反過(guò)來(lái)又可以為形式化本身的研究提供思想源泉，從而激發(fā)邏輯的進(jìn)一步發(fā)展，促其產(chǎn)生新的邏輯分支和分析工具。因此，從一個(gè)學(xué)科的角度去研究另一個(gè)學(xué)科的理論，用一個(gè)學(xué)科中的方法來(lái)研究另一個(gè)學(xué)科中的問(wèn)題，最終完美地刻畫(huà)和解決策略投票問(wèn)題，這在今天具有重要的理論意義和現(xiàn)實(shí)意義。

參考文獻(xiàn)：

[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.

(責(zé)任編輯張佑法)

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

中圖分類(lèi)號(hào)：B81

文獻(xiàn)標(biāo)識(shí)碼：A

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

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

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

收稿日期：2015-10-09

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

引用格式：孫雯,杜國(guó)平.吉伯德-薩特思韋特防策略不可能性定理的邏輯初探[J].重慶理工大學(xué)學(xué)報(bào)(社會(huì)科學(xué))，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.