MathLabs
定理已证明

吉巴德-萨特斯维特定理

命题陈述

设某个社会选择函数从至少 33 个备选方案中为每一份可能的选民排序资料选出唯一的获胜者,且每个备选方案在某份资料下确实都能获胜(满射)。若该函数是策略无懈可击的——没有任何选民能通过谎报排序(相对于其真实排序而言)获得更好的结果——那么它必定是独裁制:某个选民的首选始终是获胜者。

为什么成立?

排序式投票制度常被宣传为能抵抗策略性投票。吉巴德-萨特斯维特定理表明恰恰相反:只要某规则从 33 个或更多备选方案中选出唯一获胜者、对每份资料都有定义、允许每个备选方案有时获胜,且不是独裁制,就必定存在某种情形,使某位选民能通过谎报自己的偏好而获益。

证明思路

证明概要(归约到阿罗定理)。 首先是一条单调性引理:若备选方案 aa 在某份资料下获胜,而资料的变化仅在于某些选民在自己的排序中把 aa 排得更靠前(其余方案的相对顺序不变),那么 aa 仍必须获胜。否则,真实排序为「之前」资料的某位选民就可以谎报为「之后」的资料,把 aa 从落败推向获胜,或反之——无论哪种情形都会与某人的策略无懈可击性相矛盾。

接下来,利用该选择函数为每份资料构造一个派生的社会排序:当从每位选民的选票中删去除 aa 和 bb 之外的所有方案、只剩下两者对决时,aa 仍然获胜,就在派生排序中把 aa 排在 bb 之上。利用原选择函数的满射性与策略无懈可击性,再结合单调性引理,可以验证这个派生排序作为一个社会福利函数满足无限制域、弱帕累托原则和无关方案独立性。

由阿罗不可能性定理,由于至少存在 33 个备选方案,这个派生的社会排序必定是独裁的:某个选民 ii 的排序总是等于该派生社会排序。

最后,验证这同一位选民 ii 的首选方案总是原社会选择函数的获胜者:由于派生排序把 ii 最喜欢的方案排在其他所有方案之上,而派生排序又追踪的是两两比较中谁获胜,因此 ii 最喜欢的方案在每份资料下都必须是整体获胜者。于是,原本策略无懈可击且满射的社会选择函数被选民 ii 所独裁。

用到此定理的主题

分步证明

该定理暂无分步证明。

参考文献

  1. Kenneth J. Arrow (1950). A Difficulty in the Concept of Social Welfare · DOI:10.1086/256963
  2. Allan Gibbard (1973). Manipulation of Voting Schemes: A General Result · DOI:10.2307/1914083
  3. Amartya Sen (1970). Collective Choice and Social Welfare