论文笔记[11]——Gibbard-Satterthwaite 定理

文章: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:

  1. \(\left(P_{1}^{1}, \ldots, P_{n}^{1}\right)=\left(P_{1}^{\prime}, \ldots, P_{n}^{\prime}\right)\)
  2. \(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.