首先引入一些必要的记号和定义。令有穷集 $N=\{1,\ldots,n\}$ 为 $n$ 个投票者构成的集合，令 $X$ 为所有备选项构成的集合，每个投票者 $i$ 对 $X$ 的排序记作 $\succeq_i$，所有投票者对 $X$ 的一组排序 $(\succeq_1,\ldots,\succeq_n)$ 记作 $\vec{\succeq}$，称为一个排序组合。一个投票规则 $V$ 的作用就是，输入一个排序组合 $\vec{\succeq}$，则返回一个社会排序 $V(\vec{\succeq})$。
阿罗意义上的投票规则要求，每个投票者的排序 $\succeq_i$ 和最后得到的社会排序 $\succeq_V$ 都是弱序，即要满足下面两个性质：
- 传递性：对任意 $x,y,z\in X$，若 $x\succeq y$ 且 $y\succeq z$，则 $x\succeq z$；
- 完全性：对任意 $x,y\in X$，要么 $x\succeq y$，要么 $y\succeq x$（由完全性知，弱序也满足自反性，即对任意 $x\in X$，$x\succeq x$）。
我们称满足这些条件的投票规则为阿罗投票规则（阿罗称之为社会福利函数）。
任给弱序 $\succeq$，我们用 $\succ$ 表示其中的严格排序，即 $x\succ y$ 当且仅当 $x\succeq y$ 且并非 $y\succeq x$。我们用 $x\succeq_{V}y$ 表示，在社会排序 $V(\vec{\succeq})$ 中 $x$ 至少和 $y$ 一样好。类似的，$x\succ_V y$ 表示，在社会排序 $V(\vec{\succeq})$ 中 $x$ 严格好于 $y$。
一个阿罗投票规则 $V$ 是独裁的，意指存在某个独裁者 $i\in N$，使得对任意排序组合 $\vec{\succeq}$，对任意 $x,y\in X$，只要 $x\succ_i y$，则 $x\succ_V y$，即社会排序 $\succeq_V$ 中的严格排序完全等同于独裁者 $i$ 的严格排序。现在严格表述阿罗不可能性定理如下：
定理（阿罗不可能性定理）：若 $X$ 中的备选项超过两个，则不存在非独裁的阿罗投票规则 $V$ 能同时满足下面两个条件：
帕累托条件（即一致同意性）：对任意排序组合 $\vec{\succeq}$，对任意备选项 $x,y\in X$，若 $N$ 中投票者一致认为 $x$ 严格好于 $y$，则在社会排序 $\succeq_V$ 中也有 $x$ 严格好于 $y$；
独立性条件：对任意排序组合 $\vec{\succeq},\vec{\succeq'}$，对任意备选项 $x,y\in X$，若排序组合 $\vec{\succeq}$ 与 $\vec{\succeq'}$ 关于 $x,y$ 的个体排序相同，则 $\succeq_V$ 和 $\succeq'_V$ 关于 $x,y$ 的社会排序也相同。
换言之，在备选项超过两个的情况下，同时满足帕累托条件和独立性条件的阿罗投票规则一定是独裁的。为了证明这个定理，我们先引入两个重要概念。
定义 1（决定性联盟）：给定投票规则 $V$，称非空集 $G\subseteq N$ 在 $V$ 下关于 $(x,y)$ 是决定的，若对任意排序组合 $\vec{\succeq}$，只要 $G$ 中的投票者一致认为 $x$ 严格好于 $y$，则社会排序 $\vec{\succeq}$ 中也有 $x$ 严格好于 $y$；称 $G$ 是 $V$ 的决定性联盟，若 $G$ 在 $V$ 下关于所有 $(x,y)$ 都是决定的。
易见，若单点集 $\{i\}$ 是 $V$ 的决定性联盟，则 $i$ 是 $V$ 的独裁者。下面的证明本质上源自 1998 年诺贝尔经济学奖得主 Amartya Sen，他将阿罗的原始证明整理得更清晰了（阿罗的原始证明难以看出独立性条件在证明中的使用）。证明思路如下：
- 根据定义，若 $V$ 满足帕累托条件，则 $N$ 是 $V$ 的决定性联盟。
- 先证明关于决定性联盟的收缩引理：若非单点集 $G$ 是 $V$ 的决定性联盟，则 $G$ 的某个真子集 $G'$ 也是 $V$ 的决定性联盟。
- 由于 $N$ 是有穷的，根据 1、2 归纳可得，存在由一个人构成的决定性联盟，即独裁者。
该证明包含了帕累托条件的明确使用，而独立性条件的使用则暗藏在收缩引理的证明中。为了证明收缩引理，需要引入另一个概念：弱决定性联盟。
定义 2（弱决定性联盟）：给定投票规则 $V$，称非空集 $G\subseteq N$ 在 $V$ 下关于 $(x,y)$ 是弱决定的，若对任意排序组合 $\vec{\succeq}$，只要 $G$ 中的成员一致认为 $x$ 严格好于 $y$，且 $G$ 外的成员（若有的话）一致认为 $y$ 严格好于 $x$，则社会排序 $\succeq_V$ 中也有 $x$ 严格好于 $y$。
显然，若 $G$ 在 $V$ 下关于 $(x,y)$ 的决定的，则 $G$ 也在 $V$ 下关于 $(x,y)$ 也是弱决定的。反之是否成立呢？如果 $V$ 满足帕累托条件和独立性条件，则反过来不仅成立，而且我们还有如下更强的结论：
引理 1（扩展引理）：设 $V$ 是满足帕累托条件和独立性条件的阿罗投票规则。若 $G$ 在 $V$ 下关于 $(a,b)$ 是弱决定的，则 $G$ 是 $V$ 的决定性联盟（即 $G$ 在 $V$ 下关于任意 $(x,y)$ 都是决定的）。
这个结论有些令人意外，其证明需要使用独立性条件。
证明：设 $V$ 是满足帕累托条件和独立性条件的阿罗投票规则。设 $G$ 在 $V$ 关于 $(a,b)$ 是弱决定的，任给 $(x,y)$，我们证明 $G$ 在 $V$ 下关于 $(x,y)$ 是决定的。不妨设 $x,y$ 与 $a,b$ 均不相同（相同的情况类似可证）。任给排序组合 $\vec{\succeq}$，使得 $G$ 中所有成员一致认为 $x$ 严格好于 $y$，只需证 $x\succ_V y$。考虑如下的排序组合 $\vec{\succeq'}$，其中
- $G$ 中的投票者认为：$x\succ' a\succ' b\succ' y$
- $G$ 之外的投票者认为：$x\succ' a$，$b\succ' y$，$b\succ' a$，且对 $x,y$ 的排序与 $\vec{\succeq}$ 保持一致
易见，$G$ 中成员一致认为 $a$ 严格好于 $b$，且 $G$ 外的成员一致认为 $b$ 严格好于 $a$，由于 $G$ 在 $V$ 下关于 $(a,b)$ 是弱决定的，故 $a\succ'_{V}b$。由于在 $\vec{\succeq'}$ 中所有人都认为 $x$ 严格好于 $a$，$b$ 严格好于 $y$，据帕累托条件有，$x\succ'_{V}a$，$b\succ'_V y$，据社会排序的传递性可得，$x\succ'_V y$。注意到 $\vec{\succeq}$ 与 $\vec{\succeq}$ 关于 $x,y$ 的个体排序是一样的，由独立性条件有，$x\succ_V y$，证毕。
有了扩展引理，现在我们可以证明下面的收缩引理了。
引理 2（收缩引理）：设 $V$ 是满足帕累托条件和独立性条件的阿罗投票规则。若非单点集 $G$ 是 $V$ 的决定性联盟，则 $G$ 的某个真子集 $G'$ 也是 $V$ 的决定性联盟。
证明：由于 $G$ 是非单点集，故可将 $G$ 划分成两个不相交的非空子集 $G_{1}$ 和 $G_{2}$。考虑满足如下条件的排序组合 $\vec{\succeq}$（由于备选项超过两个，故可以做到）：
- $G_{1}$ 中的投票者认为：$x\succ y\succ z$；
- $G_{2}$ 中的投票者认为：$y\succ z\succ x$；
- $G$ 之外的投票者（如果有的话）认为：$z\succ x\succ y$。
注意到 $G$ 中所有投票者都认为 $y$ 严格好于 $z$，由 $G$ 是 $V$ 的决定性联盟可得，$y\succ_V z$。现在分别考虑两种情况（由于 $\succeq_V$ 是完全的，故有且仅有两种情况）：
- $x\succ_{V}z$。任给排序组合 $\vec{\succeq'}$，使得 $G_{1}$ 中的成员在 $\vec{\succeq'}$ 中一致认为 $x$ 严格好于 $z$，且 $G_1$ 外的成员一致认为 $z$ 严格好于 $x$，此时 $\vec{\succeq'}$ 和 $\vec{\succeq}$ 关于 $x,z$ 的个体排序相同，故由独立性条件可得，$x\succ'_{V}z$，这意味着 $G_{1}$ 在 $V$ 下关于 $(x,z)$ 是弱决定的，再据扩展引理有，$G_{1}$ 是 $V$ 的决定性联盟。
- $z\succeq_{V}x$。此时，据 $\succeq_{V}$ 的传递性有 $y\succ_{V}x$。同理于情况 1 可证，$G_{2}$ 是 $V$ 的决定性联盟。
综合 1、2，故总有 $G$ 的真子集是决定性联盟，证毕！
没有评论:
发表评论