帰納法を用いたアローの不可能性定理の証明

このブログではこれまでアローの不可能性定理の証明を３パターン扱ってきましたが（例えばExtremal Lemmaを使った証明はこちら：アローの不可能性定理の証明）、

帰納法を用いた証明は取り上げてきませんでした。ただ、やっぱり帰納法を使った証明も捨てがたいので（初めてアイディアを聞いたときにはその発想にすごく驚きました）、まとめてみることにしました。証明は鈴村先生のJER(2000)に従います。

なお、上にリンクを貼った記事ではアローの不可能性定理の主張についても丁寧に取り上げましたが、今回はそのあたりは簡単に取り上げる程度にします（アローの不可能性定理の証明を少なくとも1つは追ったことがあると想定した説明になっています）。またこのブログのこれまでの記事では $\succeq_i$ 、 $\succ_i$ 、 $\sim_i$ などの表記を用いてきましたが、今回はその代わりにそれぞれ $R_i$ 、 $P_i$ 、 $I_i$ を用いるなど、基本的には元論文の表記に従います。

アローの不可能性定理の主張

$N=\{1,..,n\}$ を個人の集合（ $2\ ≤\ n\lt\ \infty$ )、 $X$ を選択肢全体からなる集合（ $3\ ≤\ |X|$ ）とする。

$R_i$ を $i$ さんの $X$ 上の選好とする（そのAsymmetric FactorとSymmetric Factorをそれぞれ $P_i$ 、 $I_i$ とする）。それぞれの個人の選好を並べた $a=(R_1,..,R_n)$ を選好プロファイルと呼び、選好プロファイル全体からなる集合を $A$ で表す*1。

$X$ 上の選好全体からなる集合を $\mathcal{O}$ とする（選好という用語には完備性や推移性は課されているとします）。

Social Welfare Functionとは関数 $F:A\ \rightarrow\ \mathcal{O}$ のことである*2。

また、Social Welfare Function Fと選好プロファイル $a$ について $R^a$ で $F(a)$ を表す（ $F(a)$ という表記よりも $R^a$ の方が「社会さんの選好」を表すものであることが分かりやすいこともあり、このような表記を採用します）。また $P^a$ 、 $I^a$ で $R^a$ のAsymmetric FactorとSymmetric Factorを表す。

Social Welfare Function $F$ が、

·全会一致性を満たすとは、任意の選好プロファイル $a=(R_1,...,R_n)\ \in A$ と任意の選択肢 $x,y\in X$ について、 $\forall\ i\in N$ $x\ P_i\ y$ ならば、 $x\ P^a\ y$ が成り立つことである。

·IIA（独立性）を満たすとは、任意の $a=(R_1^a,...,R_n^a),b=(R_1^b,...,R_n^b)\in A$ と任意の $x,y\in X$ について、 $\forall i \in N$ $x\ R_i^a\ y\ \Leftrightarrow\ x\ R_i^b\ y$ かつ $y\ R_i^a\ x\ \Leftrightarrow\ y\ R_i^b\ x$ ならば $x\ R^a\ y\ \Leftrightarrow\ x\ R^b\ y$ かつ $y\ R^a\ x\ \Leftrightarrow\ y\ R^b\ x$ が成り立つことである。

·非独裁制を満たすとは、Fにおける独裁者が存在しないことである。なお $F$ において $i\in N$ が独裁者であるとは、任意の $a\in A$ と任意の $x,y \in X$ について、 $x\ P_i\ y$ ならば $x\ P^a\ y$ が成り立つことである。

アローの不可能性定理：

全会一致性、IIA、非独裁制の３つを同時に満たすSocial Welfare Functionは存在しない。

帰納法を使った証明のアイディア

さて、お待ちかねの今回の証明のアイディアです！

今回の証明のアイディアは、 $n+1$ 人からなる社会において上の３つの条件（公理）を満たすSocial Welfare Functionが存在すると仮定したとき(実際には存在しないがそう仮定すると)、 $n$ 人からなる社会においても３つの条件（公理）を満たすSocial Welfare Functionが存在する

と言えることです。

つまり例えば、 $N=\{1,2,3,4\}$ という社会において３つの条件を満たすSocial Choice Functionが存在すると仮定すると、 $N=\{1,2,3\}$ という社会においても３つの条件を満たすSocial Welfare Functionが存在することを示すことができます。

これを繰り返し用いると、今注目している $n$ 人の社会において３つの条件を満たすものが存在するならば、2人の社会において（ $N=\{1,2\}$ ）3つの条件を満たすSocia Welfare Functionが存在することになります。

しかし、 $2$ 人の社会において３つの条件を満たすSocial Welfare Functionが存在しないことは割と簡単に示せるので、これで証明が完了します。

今回の証明用に定式化を少しいじる

上でアローの不可能性定理の定式化を行いましたが、そこでは $n$ が外生的に与えられているなどして、今回の証明的には表記が微妙なところがあります。そこで、定式化を少しいじります。

$X$ を選択肢全体からなる集合（ $3\ ≤\ |X|$ ）とする。 $2$ 以上の自然数 $n$ について $I(n)$ で $1$ 〜 $n$ さんからなる個人の集合を表す、つまり $I(n)=\{1,..,n\}$ とする。

社会 $I(n)$ における選好プロファイル $(R_1,...,R_n)$ 全体からなる集合を $A_n$ で表す。

社会 $I(n)$ におけるSocial Welfare Functionとは関数 $F^n:A_n\ \rightarrow\ \mathcal{O}$ のことである*3。

アローの不可能性定理：

任意の $2≤n$ について、３つの条件を同時に満たす $I(n)$ におけるSocial Welfare Function $F^n$ は存在しない。

証明

3つの補題を用いて証明します。最初の補題はアローの不可能性定理の他の証明においてよく知られたものであるため証明は省略します（またこの補題は今回の証明においては残りの補題を証明するのに使われるだけです）。また他の補題についてもすごく細かくは証明しません。

まずは補題2と3を証明するのにあると便利な次の補題から。簡単にいうと、全会一致性とIIAの下では、「局所的に独裁者っぽくなっている人」が実際に「独裁者」になることを主張します。

補題1（独裁者補題）

与えられた自然数 $2≤n$ について、 $F^n$ が全会一致性とIIAを満たすとする。このとき、ある $i\in I(n)$ 、ある $x,y\in X$ 、ある $a\in A_n$ が存在して、 $x\ P_i\ y$ かつ $\forall j\neq i$ $y\ P_j\ x$ かつ $x\ P\ y$ ならば、 $i$ は $F^n$ における独裁者である。

Proof：省略

次の補題が今回の証明のメインです。

補題2（人数削減補題）

与えられた自然数 $3≤n$ について、3条件を同時に満たす $F^n$ が存在するとする。このとき、3条件を同時に満たす $F^{n-1}$ も存在する。

Proof:

3つの条件を満たす $F^{n}$ が与えられたときに、

$F^{n-1}$ を次のように構築する。

例えば $n=4$ のケースでは $F^3$ を構築したいわけだが、左図のような選好プロファイル $a\in A_3$ については（ $X=\{x,y,z\}$ ）、 $F^3$ は $F^4$ が右図の選好プロファイルについて割り当てている選好を割り当てることにする（なお、図において本来は $P_1^a$ のように書くべきところを省略して $P_1$ のように書いている）。

つまり、数式で書くと、 $F^{n-1}$ は任意の選好プロファイル $a\in A_{n-1}$ について $F^{n-1}(a)=F^n(a,R^*)$ と定義される。ここで $R^*$ は全部が無差別な選好（つまり $R^*=X\ \times\ X$ ）。

$F^n$ から $F^{n-1}$ を構築しようと考えた場合の１つの自然なやり方になっているかなと思います（技巧的な作り方というよりは自然に作っている印象を受けます）。

このようにして構築した $F^{n-1}$ について、 $F^{n-1}$ は３つの条件を満たすことになります。それらを１つずつ示していけばこの補題は証明されます。今回は、 $F^{n-1}$ がIIAを満たすことと全会一致性を満たすことのみ示します。

·IIAについて。下図の青色の選好プロファイル $a,b\in A_{n-1}$ を考える（本来は任意に考えないといけないが今回はロジックを分かりやすく図で示したいため具体的な１つのケースを考える）。このとき選択肢 $x,y$ についてIIAを使用する条件が揃っている（各個人について $x,y$ の比較が $a,b$ の両方で同じ）。

両方の青枠について $F^{n-1}$ が割り当てる選好が $x,y$ について同じであればIIAは満たされるわけであるが、 $F^{n-1}$ がどのように $F^n$ から構築されたかを思い出すと、 $F^n$ が図の2つの黒枠の選好プロファイルに割り当てる選好において（つまり $F^n(a,R^*)$ と $F^n(b,R^*)$ において） $x,y$ の比較が同じになっているといえればよい。そしてこれは $F^n$ がIIAを満たしていることがから示せる。

·全会一致性について。背理法で示すために、 $F^{n-1}$ が全会一致性を満たさないとする。このときある選好プロファイル $a\in A_{n-1}$ とある選択肢 $x,y\in X$ が存在して、 $\forall i\in I(n-1)$ $x\ R_i\ y$ であるが、 $y\ R^a\ x$ が成り立つ。

ここで任意の選択肢 $z\in X\setminus \{x,y\}$ を取ってきて、 $\forall\ i\in I(n-1)$ $x\ P_i^b\ z\ P_i^b\ y$ かつ、 $z\ P_n^b\ x\ I_n^b\ y$ であるような選好プロファイル $b\in A_n$ を考える（ここは常套手段。 $x$ と $z$ の比較について $n$ さんだけ $z\ P_n\ x$ になっていることに注意→補題1を使えそう）。

$F^n$ が $(a,R^*)$ に割り当てる選好において $y\ R^(a,R^*) \ x$ であるため（ $F^{n-1}$ の定義より）、独立性より $y\ R^b\ x$ が成り立つ。また $F^n$ の全会一致性より $z\ P^b\ y$ が成り立つ。したがって推移性より $z\ P^b\ x$ となるが、補題1より $n$ さんが独裁者となり矛盾。よって $F^{n-1}$ は全会一致性を満たす。

Q.E.D.

ちょっと長かかったですが、人数削減補題を示すことができました。最後に次の補題を証明します。

補題3（2人社会補題）

３つの条件を同時に満たす $F^2$ は存在しない。

Proof:

背理法で示すために、３つの条件を同時に満たす $F^2$ が存在するとする。このとき任意の選択肢 $x,y \in X$ （ただし $x\ \neq\ y$ )を取ってきて、 $x\ P_1^a \ y$ かつ $y\ P_2^a\ x$ であるような選好プロファイル $a=(R_1,R_2)\in A_2$ を考える*4。 $R^a$ の完備性より、 $x\ P^a\ y$ または $y\ R^a\ x$ が成り立つ。

前者であれば $1$ さんが局所的に独裁者っぽくなっているため補題1より $1$ さんが独裁者となり $F^2$ の非独裁制に矛盾する。後者の場合（ $y\ R^a\ x$ ）には同じロジックは使えないが（ $P^a$ ではないため）、第3の選択肢 $z$ を取ってきて上手いこと選好プロファイルを考えてあげると補題1を用いてこちらも矛盾を示せる

Q.E.D.

補題２と補題３からアローの不可能性定理が示されます(補題2について「ならば」を使った形にした上で対偶を取るとより分かりやすいかもしれない)。以上が帰納法を用いたアローの不可能性定理の証明です。

Fin.*5