アローの不可能性定理の証明
はじめに
本記事ではアローの不可能性定理の証明を解説します。
本記事の特徴
- 証明の全体像を把握できるように整理
（命題の関係性を示す図を作成） - 証明の理解しやすさを優先して補題の主張を緩めて記載
（証明の正確性に問題はありません） - 数式を使って正確に記載
- 改行とタブを多用して論理記号の範囲を明確に記載
参考書
- 林、ミクロ経済学[増補版] [1]
前提知識
- 社会的厚生関数の定義
- アローの不可能性定理の主張内容
記号
- $n \in \mathbb{N}$：エージェントの数
- $\mathcal{A} = \{ a_1, ..., a_n \}$：エージェントの集合
- $m \in \mathbb{N}$：選択肢の数
- $\Gamma = \{ \gamma_1, ..., \gamma_m \}$：選択肢の集合
- $\Sigma$：選好順序の集合（選択肢集合のすべての順列）
- $\Omega \subseteq \Sigma$：実行可能な選好順序の集合
- ${\succ}_i \in \Omega$：エージェント$i \in \mathcal{A}$の選好順序
- ${\succ} \in \Omega^n$：$n$人のエージェントの選好順序の集合（単に選好順序と呼ぶ）
- $x \succ_i y$：エージェント$i$は選択肢$x \in \Gamma$を選択肢$y \in \Gamma$よりも上位と評価
- $f: \Omega^n \rightarrow \Sigma$：社会的厚生関数
- $x \ f({\succ}) \ y$：社会的厚生関数$f$は選択肢$x \in \Gamma$を選択肢$y \in \Gamma$よりも上位と評価
仮定
アローの不可能性定理では以下の4つの条件が満たされることを仮定します。
$\Omega = \Sigma$
$\forall x, y \in \Gamma, \forall {\succ} \in \Omega^n,$
$\forall i \in \mathcal{A}, x \succ_i y$
$\Rightarrow$
$x \ f({\succ}) \ y$
$\forall x, y \in \Gamma,
\forall {\succ}, {\succ}' \in \Omega^n, $
$\forall i \in \mathcal{A}, x \succ_i y \Leftrightarrow x \succ_i' y$
$\Rightarrow$
$x \ f({\succ}) y \Leftrightarrow x \ f({\succ}') y$
定理
本章ではアローの不可能性定理を証明します。
まずは、定理の中心となる「特定のペアに決定権を持つ集団」を定義します。
以下の条件を満たすとき、集団$\mathcal{G} \subseteq \mathcal{A}$は選択肢$x, y \in \Gamma$の決定権を持つと呼ぶ。（以下の命題を$\isdecisive(\mathcal{G}, x, y)$と表記する。）
$\forall {\succ} \in \Omega^n,$
$\forall i \in \mathcal{G}, x \succ_i y$
$\Rightarrow$
$x \ f({\succ}) \ y$
また、決定権の条件を緩めた「弱決定権」も定義します。
以下の条件を満たすとき、集団$\mathcal{G} \subseteq \mathcal{A}$は選択肢$x, y \in \Gamma$の弱決定権を持つと呼ぶ。（以下の命題を$\isweaklydecisive(\mathcal{G}, x, y)$と表記する。）
$\forall {\succ} \in \Omega^n,$
$
\begin{cases}
\forall i \in \mathcal{G}, & x \succ_i y \\
\forall i \not \in \mathcal{G}, & y \succ_i x
\end{cases}$
$\Rightarrow$
$x \ f({\succ}) \ y$
定理の証明は決定権の概念のみでも行えますが、弱決定権も導入することで補題の証明が簡潔になります。決定権を持てば弱決定権も持ちますので、定理の証明を理解する上では、弱決定権を決定権と読み替えていただいて問題ありません。
では、アローの不可能性定理を証明します。証明は複数の補題から構成されているため、本章では補題が成り立つことを前提に定理を証明し、次章で補題を証明します。
$\exists i \in \mathcal{G}, \forall x, y \in \Gamma, \isdecisive(\{i\}, x, y)$
証明の全体像（どの補題を使ってどの補題を示すのか）を図1に示します。矢印の元の命題を使って矢印の先の命題を証明します。
証明の全体像
アローの不可能性定理は「（前述の仮定の下で）任意のペアに決定権を持つ個人が存在してしまう」（独裁になってしまう）という定理です。その存在を直接証明するのは難しいので、条件を緩めた「特定のペアに決定権を持つ集団」に対して、集団を個人に狭める＆特定ペアを任意ペアに拡張することで導きます。
まずは、特定のペアに決定権を持つ集団が存在することを示します（補題2）。
次に、補題2における集団を個人に狭めるために、決定権を持つ集団の真の部分集合に、他のペアの決定権を持つものが存在することを示します（補題3）。補題2で示した集団に補題3を繰り返し適用することで、特定のペアに決定権を持つ個人がいることを示せます（補題4）。
最後に、補題4の特定ペアから任意ペアに拡張するために、特定のペアに決定権を持つ集団は、任意のペアに決定権を持つことを示します（補題5）。これを補題4に適用することで、任意のペアに決定権を持つ個人が存在することを示せます（定理1）。
補題
本章では定理の構成要素となる補題を証明します。
$\exists \mathcal{G} \subseteq \mathcal{A}, \exists x, y \in \Gamma, \isweaklydecisive(\mathcal{G}, x, y)$
【満場一致性】より、集団$\mathcal{G}$をエージェント集合$\mathcal{A}$、特定のペア$x, y$を選択肢集合から取り出した任意のペアとすると、補題が成り立ちます。
$\forall \mathcal{G} \subseteq \mathcal{A}, \forall x, y \in \Gamma,$
$
\begin{cases}
|\mathcal{G}| \geq 2 \\
\isweaklydecisive(\mathcal{G}, x, y)
\end{cases}$
$\Rightarrow$
$\exists \mathcal{G}' \subset \mathcal{A},\exists z, w \in \Gamma, \isweaklydecisive(\mathcal{G}', z, w)$
補題が成り立つ集団$\mathcal{G}'$とペア$z, w$を具体的に構成することで証明します。
任意の集団$\mathcal{G}$とペア$x, y$を取り出し、補題の条件を満たすと仮定します。集団$\mathcal{G}$を二つの真の部分集合$\mathcal{G}_1, \mathcal{G}_2 \subset \mathcal{A}$に分割します。任意の選択肢$z \in \Gamma \setminus \{ x, y \}$を取り出します。以下の条件(※)を満たす選好順序${\succ} \in \Omega^m$を取り出します。なお、【無制約性】より、以下の条件を満たす選好順序は任意の$x, y, z$で存在します。
\begin{cases}
\forall i \in \mathcal{G}_1, & x \succ_i y \succ_i z \\
\forall i \in \mathcal{G}_2, & z \succ_i x \succ_i y \\
\forall i \not \in \mathcal{G}, & y \succ_i z \succ_i x
\end{cases}
社会的厚生関数$f$による選択肢$x, y, z$の評価を考えます。
- 選択肢$x, y$について
集団$\mathcal{G}$はペア$x, y$で弱決定権を持つことから、$x \ f({\succ}) \ y$となります。 - 選択肢$x, z$について
$x \ f({\succ}) \ z$と$z \ f({\succ}) \ x$の両方がありえますので、それぞれの場合を検討します。- $x \ f({\succ}) \ z$である場合
【独立性】より、条件(※)を満たす任意の選好順序${\prec}' \in \Omega^m$で$x \ f({\succ}') \ z$が成り立ちます。これより、集団$\mathcal{G}_1$がペア$x, z$で弱決定権を持つことになります。したがって、集団$\mathcal{G}'$を集団$\mathcal{G}_1$、ペア$z, w$をペア$x, z$とすると、補題が成り立ちます。 - $z \ f({\succ}) \ x$である場合
$x \ f({\succ}) \ y$と$z \ f({\succ}) \ x$より、$z \ f({\succ}) \ x$となります。このとき、【独立性】より、条件(※)を満たす任意の選好順序${\prec}' \in \Omega^m$で$z \ f({\succ}') \ x$が成り立ちます。これより、集団$\mathcal{G} \setminus \mathcal{G}_1$がペア$z, x$で弱決定権を持つことになります。したがって、集団$\mathcal{G}'$を集団$\mathcal{G} \setminus \mathcal{G}_1$、ペア$z, w$をペア$z, x$とすると、補題が成り立ちます。
- $x \ f({\succ}) \ z$である場合
$\exists i \in \mathcal{A}, \exists x, y \in \Gamma, \isdecisive(\{i\}, x, y)$
補題2で示した集団に補題3を繰り返し適用することで、最終的には個人からなる集団が特定のペアに決定権を持つことを示せます。
$\forall \mathcal{G} \subseteq \mathcal{A},$
$\exists x, y \in \Gamma, \isweaklydecisive(\mathcal{G}, x, y)$
$\Rightarrow$
$\forall z, w \in \Gamma, \isdecisive(\mathcal{G}, z, w)$
任意の集団$\mathcal{G} \in \mathcal{A}$を取り出します。補題の条件を満たすペア$x, y \in \Gamma$が存在すると仮定します。任意のペア$z, w \in \Gamma \setminus \{ x, y \}$を取り出します。
以下の条件を満たす任意の選好順序${\succ} \in \Omega^m$を取り出します。
$\begin{cases}
\forall i \in \mathcal{G}, & z \succ_i x \succ_i y \succ_i w \\
\forall i \not \in \mathcal{G}, & y \succ_i x, z \succ_i x, y \succ_i w
\end{cases}$
集団$\mathcal{G}$はペア$x, y$で決定権を持つことから、$x \ f({\succ}) \ y$となります。また、【満場一致性】より、$z \ f({\succ}) \ x, y \ f({\succ}) \ w$となります。以上より、$z \ f({\succ}) \ w$となります。
以下の条件を満たす任意の選好順序${\succ}' \in \Omega^m$を取り出します。
$\begin{cases}
\forall i \in \mathcal{G}, & z \succ_i w \\
\forall i \not \in \mathcal{G}, & z \succ_i w \Leftrightarrow z \succ'_i w
\end{cases}$
【独立性】より、$f({\succ})$と$f({\succ}')$での$z, w$の評価は等しくなります。したがって、$z \ f({\succ}') \ w$となります。
以上より、集団$\mathcal{G}$はペア$z, w$で決定権を持ちます。
（本証明は選択肢が4つ以上あることを前提とした証明ですが、選択肢が3つでも示せる証明もあります。）