文章：Svensson L G, Reffgen A. The proof of the Gibbard–Satterthwaite theorem revisited[J]. Journal of Mathematical Economics, 2014, 55: 11-14.
Gibbard-Satterthwaite 定理：对于至少有 \(3\) 个候选人的投票，若它是 中立 且 strategy-proof 的，则它一定是一个 dictatorial.
The voting model
- \(N=\{1,\ldots,1\}\) voter；
- \(A=\{a_1,\ldots,a_m\}\) 候选人；
- 偏好 \(P\)：\(A\) 上的序. 序 \(P\) 的第 \(k\) 位用 \(r_k(P)\) 表示.
- \(A\) 上的所有偏好用 \(\Sigma\) 表示. i.e. profile \((P_1,\ldots,P_n)\in\Sigma^n\).
- \(P_{-i}\)：\(P\) 的序列中抠掉 voter \(i\)，\(P_{-\{i,j\}}\) 同理.
一个投票规则是映射 \(f:\Sigma^n\to A\).
Def. 1 (strategy-proof)
Def. 2 (dictatorial)
Def. 3 (neutral)
Gibbard-Satterwaite theorem 候选人至少三个，若投票机制 \(f\) 是满射，则 \(f\) 是 strategy-proof 的 \(\Rightarrow\) \(f\) 是 dictatorial.
Two basic properties of strategy-proof rules
Lemma 1 （单调性） 设 \(f\) 是 strategy-proof rule. 若 \(f(P_1,\ldots,P_n)=a\) 且对 \((P_1',\ldots,P_n')\in\Sigma^n\) 有 \(a P_i x\Rightarrow a P_i' x\)，\(\forall i\in N, \forall x\in A\)，则 \(f(P_1',\ldots,P_n')=a\).
- 总结一下：只要大家在谎报偏好时，都没有降低 \(a\) 的位次，那么结果就仍然会是 \(a\).
Lemma 2 （Pareto 最优） 设 \(f\) 是 strategy-proof 的满射. 若 \((P_1,\ldots,P_n)\in\Sigma^n\) 对 \(\forall i\in N\) 都满足 \(aP_ib\)，则 \(f(P_1,\ldots,P_n)\neq b\).
一种归纳证明
先来一个例子： \(N=\{1,2\}\)，\(A=\{a,b,c\}\)，\(P=(P_1,P_2)\). 我们需要在 \(N\) 中找一个 dictator.
考虑 \(P_1=(a,b,c), P_2=(b,a,c), P_2'=(b,c,a)\)：不妨设 \(f(P_1,P_2)=a\).
- 由 Pareto 最优性，\(f(P_1,P_2)\neq c\). 考虑到 \(a,b\) 的对称性，不妨设 \(f(P_1,P_2)=a\).
- 由 Pareto 最优性，\(P_1\) 和 \(P_2'\) 中，\(b\) 都比 \(c\) 好，故 \(f(P_1,P_2')\neq c\).
- 由 strategy-proof 可知 \(f(P_1,P_2')\neq b\).
换言之，\(f(P_1,P_2')\) 只能是 \(a\). 这实际上是在说，\(1\) 是 dictator.
我们现在来证明，每个候选人都存在一个 dictator.
先考虑 \(n=2\) 情形.，我们来证明如下定理：
Th. 1. 设 \(N=\{1,2\}\)，且 \(|A|\geqslant 3\)，则 strategy-proof 的满射都是 dictatorial.
Proof. 取 \(a,b\in A\)，构造 \((\bar{P_1},\bar{P_2})\in \Sigma^2\)，s.t. 其第一位和第二位分别是 \(ab\) 和 \(ba\). 不妨设 \(f(\bar{P_1},\bar{P_2})=a\). 然后证明无论 \(2\) 怎么改偏好，都不会改变最终结果.
以下引理对于归纳至关重要：
Lemma 3. 令 \(f: \Sigma^n\to A\) 是满射，且是 strategy-proof 的. 对于 \(i,j\in N\)，定义 \(f_{i,j}\)： \[f_{i,j}: \Sigma^{n-1}\to A, ~~~(P_i,P_{-\{i,j\}})\mapsto f(P_i,P_i,P_{-\{i,j\}}).\] 则 \(f_{i,j}\) 也是满射，并且也是 strategy-proof 的.
Proof. 满射比较容易证明，可直接由 \(f\) 是满射得到. 对于 strategy-proof 性质，首先我们考虑除 \(i,j\) 外的其他 voter. 如果存在一个非 \(i,j\) 的 voter 能够操纵投票结果，这将与 \(f\) 的 strategy-proof 性质矛盾. 换言之，只有 \(i\) 和 \(j\) 有可能能够操纵投票结果. 我们再对 \(i\) 和 \(j\) 进行讨论即可.
Th. 2 若候选人的个数至少是 \(3\)，则 strategy-proof 的满射 \(f\) 一定是 dictatorial.
Proof. 现在只需要考虑 \(n\geqslant 3\) 的情况了，设 \(<n\) 的情形全部成立，下证 \(n\) 的情形成立.
考虑 \(n\) 情形下的 \(f\)，则其诱导的 \(f_{i,j}\) 都是 strategy-proof 的满射，因而都是 dictatorial. 则有且仅有以下两种情况：
- 对于一些 \(f_{i,j}\)，dictator 是某个 \(k\in N\backslash\{a,b\}\)，则可证明（用 lemma 1 的单调性） \(k\) 同样是 \(f\) 的 dictator.
- 对 \(\forall f_{i,j}\)，\(i\) 是 dictator，可以证明这种情况是不可能的.
中立情形下的直接证明
两个前提：(1) 中立，(2) \(m\geqslant n\). （Excuse me？？投票人比候选人还少？？）
Theorem 3. 至少 \(3\) 个候选人，且 \(m\geqslant n\). 则 neutral + strategy-proof \(\Rightarrow\) dictatorial.
Proof. 令 \(P\in\Sigma\)，s.t. \(r_k(P)=a_k\)，取 \(A\) 上的置换 \(\pi\)：\(\pi(a_k)=\begin{cases} a_{k+1}, & 1\geqslant k\geqslant n - 1\\ a_1, & k=n\\ a_k, & k>n \end{cases}\)，考虑 profile \(\left(P, \pi P, \pi^{2} P, \ldots, \pi^{n-1} P\right) \in\Sigma^n\)，这时前 \(n\) 个候选人的标号恰好完全轮换了一次. 这时 \(a_n\) 及下标更小的 \(a_i\) 要比下标更大的 \(a_j\) Pareto 占优（为什么？），因此由(1) neutral \(\Rightarrow\) surjective; (2) Lemma 2. 可得 \(f\left(P, \pi P, \ldots, \pi^{n-1} P\right)=a_{i}\)，其中 \(i\leqslant n\)，那么不妨设它就是 \(a_1\).
现在，取 profile \(\left(P_{1}^{\prime}, \ldots, P_{n}^{\prime}\right) \in \Sigma^{n}\)，s.t. 在这个 profile 中，只有\(1\) 把 \(a_1\) 排第一，\(a_n\) 排第二；其他人都把 \(a_n\) 排第一，\(a_1\) 排第二. 那么，相比 \((P,\pi P,\ldots)\) 那个 profile，\(a_1\) 的地位没有下降，故 \(f(P_1',\ldots,P_n')=a_1\).
现在来定义一列 profile：
- \(\left(P_{1}^{1}, \ldots, P_{n}^{1}\right)=\left(P_{1}^{\prime}, \ldots, P_{n}^{\prime}\right)\)；
- 当 \(j\geqslant 2\) 时，对 \(i\neq j\)，取 \(P_i^j=P_i^{j-1}\)；对 \(i=j\)，取 \(r_1(P_i^i)=a_n\)，\(r_m(P_i^i)=a_1\).
由 Pareto 最优性，\(f\left(P_{1}^{j}, \ldots, P_{n}^{j}\right) \in\left\{a_{1}, a_{n}\right\}\)，而 strategy-proof 要求这个结果不能是 \(a_n\). 那就只能是 \(a_1\) 了！进一步，在 \((P_1^n,\ldots,P_n^n)\) 中，除了 \(1\) 把 \(a_1\) 放在第一位之外，其他人都把 \(a_1\) 放到了最后. 但尽管如此，选举的获胜者仍然是 \(a_1\). 单调性告诉我们，这里没有别的原因，只能说 \(a_1\) 真的强. 换言之，voter \(1\) 是一个 dictator.