如此保证选举公正性能成吗

一个小镇上即将进行大选，候选人有 m ≥ 3 个，选民一共有 n 人。选举时，每个选民在选票上写下一个候选人的名字，然后由计算机根据某种选举机制算出大选的获胜者来。如果把 n 个选民的选票依次记为 x₁, x₂, …, x_n的话，那么选举机制的算法其实就是一个映射到 {1, 2, …, m} 的函数 f(x₁, x₂, …, x_n) 。

为了保证选举程序的公平性，让每个人手中的选票都能发挥作用，政府提出了“差异性原则”：如果每个人的选票都变了，那么竞选的获胜者也应当改变。也就是说，如果对于所有的 i 都有 x_i≠ y_i，那么必有 f(x₁, x₂, …, x_n) ≠ f(y₁, y₂, …, y_n) 。选票系统的算法虽然不是透明的，但政府保证，这个算法满足差异性原则。

差异性原则真的能够保证，每个选民的选票都有足够的权力吗？不是。差异性原则看似很强，但实际情况则是，它不但不能保证每张选票都能影响选举结果，甚至还无法避免有选民独裁选举结果的现象发生。更不可思议的是，事实上独裁现象是必然会发生的——独裁是差异性原则的必然推论！下面我们将证明，对于任意一种满足差异性原则的选票算法，我们都能找到这样一个选民，他的选票独裁了选举结果，获胜者是谁完全由他的选票决定，与其他人的选票无关。

为了便于叙述，我们假设有 6 个选民，有 4 个候选人。因此，选票算法相当于是一个把所有仅由数字 1 到 4 组成的全部 4⁶个 6 位数映射到 {1, 2, 3, 4} 的一个函数。我们不妨把这些 6 位数看作是由所有可能的前 5 位数加上最后一位数得来的。

让我们先来考虑这样一种情形：在所有可能的前 5 位数中，存在一个 5 位数，它后面加上 1 、 2 、 3 、 4 后所对应的获胜者各不相同。不妨假设这个前 5 位数是 14232 吧。也就是说，当 i 取 1 到 4 时， 14232i 正好对应了所有可能的获胜者。下面，我们任意选取另外一个 5 位数组合 x₁x₂x₃x₄x₅， 使得它的每一位数字正好都和 14232 上对应位置的数字不同。考虑 x₁x₂x₃x₄x₅1 所对应的获胜者，它必然和 142321 、 142322 、 142323 、 142324 之一相同；但根据差异性原则，它和 142322 、 142323 、 142324 都不同，因而只可能是和 142321 相同。同理， x₁x₂x₃x₄x₅2 所对应的获胜者也就和 142322 相同，事实上对于每个 i ， x₁x₂x₃x₄x₅i 所对应的获胜者与 14232i 都完全一致。

我们还可以继续推出，事实上，对于任意的前 5 位数组合 y₁y₂y₃y₄y₅都有，对于每个 i ， y₁y₂y₃y₄y₅i 所对应的获胜者都与 14232i 完全一致。为了看出这一点，我们只需要精心选取一个适当的前 5 位数 x₁x₂x₃x₄x₅，使得它和 14232 、 y₁y₂y₃y₄y₅对应位置上的数字都不相同。由前面的推理， x₁x₂x₃x₄x₅i 所对应的获胜者已经与 14232i 一致了，根据同样的道理，y₁y₂y₃y₄y₅i 所对应的获胜者又依次与 x₁x₂x₃x₄x₅i 相同，如此一“传递”便证明了任意 5 位数 y₁y₂y₃y₄y₅都与 14232 拥有完全相同的效力。

也就是说，选举结果与前 5 个人的选票无关，完全被最后一个人的选票独裁了。

接下来，我们来考虑另一种情形：对于所有可能的前 5 位数 x₁x₂x₃x₄x₅，当 i 从 1 取到 4 时，在 x₁x₂x₃x₄x₅i 当中都至少有两个相同的获胜者。下面，我们任选一个前 5 位数组合，比方说 12314 吧，然后给前 5 个人定义 4 个新的选票算法 g_k（这里 k 可以取 1 、 2 、 3 、 4 中的任意一个）：当 y₁y₂y₃y₄y₅≠ 12314 时， g_k(y₁y₂y₃y₄y₅) 就等于 y₁y₂y₃y₄y₅i 当中重复出现的那个获胜者；当 y₁y₂y₃y₄y₅= 12314 时，就让 g_k(y₁y₂y₃y₄y₅) 等于 y₁y₂y₃y₄y₅k 所对应的获胜者。注意到，每一个选票算法 g_k同样满足差异性原则。这是因为，任取每位数字都不相同的两组选票 a₁a₂a₃a₄a₅和 b₁b₂b₃b₄b₅，我们可以假设 a₁a₂a₃a₄a₅在 g_k中所对应的获胜者也就是原来的选票算法中 a₁a₂a₃a₄a₅m 所对应的获胜者（即使 a₁a₂a₃a₄a₅恰好等于 12314 ），其中 m 是某个 1 到 4 之间的数。那么， b₁b₂b₃b₄b₅就不可能再等于 12314 了，因而，一定存在某个 p 和 q ，使得 b₁b₂b₃b₄b₅在 g_k中对应的获胜者和原选票算法中的 b₁b₂b₃b₄b₅p 、 b₁b₂b₃b₄b₅q 都相等。其中， p 和 q 必有一个与 m 不同，比如说 p 吧。那么在原选票算法中，由差异性原则， b₁b₂b₃b₄b₅p 和 a₁a₂a₃a₄a₅m 对应了不同的获胜者。因而在 g_k中， b₁b₂b₃b₄b₅和 a₁a₂a₃a₄a₅也对应了不同的获胜者。

但是 g₁、 g₂、 g₃、 g₄这四个选票算法其实只有一个差别： 12314 所对应的获胜者不同。两个满足差异性原则的选票算法怎么可能只在一处有不同呢？ 12314 和 23421 、 34132 、 41243 两两之间都构成了完全差异的情况，根据差异性原则，它们正好对应了 4 个不同的获胜者；如果后面三种情况对应的获胜者都不变， 12314 所对应的获胜者自然也没有别的选择。因此，两个选票算法绝不可能只在一处有区别。这说明，事实上 g₁、 g₂、 g₃、 g₄这四个选票算法是完全相同的，它们其实都把 12314 映射到了相同的获胜者身上。回顾 g_k的定义，我们立即发现，当 i 从 1 取到 4 时， 12314i 所对应的获胜者是相同的。

根据同样的道理，把 12314 换作任意一个 5 位数组合 z₁z₂z₃z₄z₅， 那么 z₁z₂z₃z₄z₅i 都对应着相同的获胜者。这说明，事实上最后一张选票没有任何权力，获胜者完全由前 5 张选票决定，不随最后一张选票的改变而改变。于是，我们可以无视最后一张选票，递归地对前 5 张选票继续分析，直到发现独裁者为止。至此，我们便完成了整个证明。

不过话说回来，文章开头提到的“差异性原则”，其实是明显不合理的——谁说每个人的选票都变了，结果就一定要变的？这个条件太不自然，当然会造成一些诡异的结果。相比之下，Arrow 不可能性定理则更加令人震撼，在“全体一致性”和“无关候选人独立性”这两个看上去更加自然的条件下，独裁仍然是一个必然推论。因此，最后还是那句颇有些耸人听闻的话：独裁是唯一完美的选举制度。

题目来源：http://www.cs.cmu.edu/puzzle/puzzle13.html

原题答案的叙述方式很怪异，我看了很久才看明白。

复述时做了大量改动，若有疏忽请大家及时指正。