前書き

有名な定理である、アローの不可能性定理の証明を説明していきたいです。主張自体が有名である一方、数学的にスッキリとした証明は、特に日本語では中々目にしないと思いました。定理の内容は知っているが証明は知らないという方も沢山おられるのではないでしょうか。

準備

$N=\{1,2,...,n\}$を個人の集合とし、$A$を候補者の集合とします。$>_i$を個人$i$の$A$上の完全で反射的で推移的な二項関係とします。これを順序と言います。$A$上の全ての個人の順序の全体集合を$R(A)$と書きます。$n$人がそれぞれ色々な$A$の順序を持っていたとき、全体として$A$上の順序を決定する関数$f$をSWF (social welfare function)といいます。つまり、

$$f:R(A)^n \rightarrow R(A)$$

です。ここからこのSWFに関して3つ定義を述べます。この先、$>_i$は個人$i$の、$>$はあるSWFによる個人全員が定める順序とします。

弱パレート (weakly Pareto)

(定義)
SWFが弱パレートであるとは、任意の$a,b \in A$について、$\forall i \in N$で$a>_ib$なら$a>b$が成立していることです。

IIA (independent of irrelevant alternatives)

(定義)
SWFがIIAであるとは、任意の$a,b \in A$について、$\geq$の$a$と$b$の相対的順序は、個人の$a$と$b$の相対的順序にのみ依存していることです。相対的順序とは、その2つだけの順序関係のことです。

独裁的 (dictatorship)

(定義)
SWFが独裁的とは、ある個人$i^* \in N$がいて、任意の$a,b \in A$について、$a>_{i^*}b$なら$a>b$になることが成立していることです。

具体例、コメント

SWFについて具体的に考えてみましょう。一番簡単な例は恐らく多数決です。$A$の要素で個人の選好で1位になった回数が多い順に並べてみましょう。試しに$A=(a,b,c)$として、個人が3人いるときを考え、それぞれ

$$1:a >_1 b >_1 c , \ 2:a >_2 c >_2 b , \ 3:b >_3 a >_3 c $$

という順序を持つとします。このとき、多数決による結果は$a \geq b \geq c$になります。簡単な例ですが、しかしながら、1位しか見ないので、それ以外の順位はバラバラでも良く、弱パレートやIIAを満たしません。上で定義した3つの仮定は思いの外に強い条件であることがわかります。

他の簡単な例として、ある個人の順序をそのまま掃き出すだけのSWFが考えられます。これは当然、独裁的です。更に、少し考えれば分かりますが、弱パレート的でもあり、IIAでもあります。

どのようなSWFがよい性質を持っているのかが気になります。アローの不可能性定理はその性質に関連した定理です。

アローの不可能性定理

3人かそれ以上の候補者を考える。このとき、任意の弱パレートでIIAなSWFは、独裁的。

コメント

主張をみると、これが有名になっている理由がわかると思います。つまり、複数の個人から全体の順序を作るとき、一見まともそうな仮定から、独裁的な結果が生まれます。それ故、独裁的でないようにする為には、他の仮定を取り去る必要があります。この定理と民主主義とを関連させ、色々なことが言われています。

decisive coalition

ここでひとつ定義を挟みます。
(定義)
SWF$f$に対して、任意の順序で、$a,b \in A$についてdecisive coalition (決定的な連合)とは、個人の集合$C \subseteq N$で、

$$C \subseteq N_{a>b} \ \Rightarrow\ a>b$$

が成立しているものとする。ここで、$N_{a>b}$とは、$a >_i b$としている個人の集合で、

$$N_{a>b}= \{ i \in N \mid a >_i b \}$$

のことです。これはつまり$C$が$a>b$であるための十分条件になっているということである。

また、$C \subseteq N$で、

$$C=N_{a>b} \ \Rightarrow \ a>b$$

が成立しているものを$a,b \in A$について、弱decisive coalitionと呼びます。この場合当然$C$に入ってない個人は$b>_ja$になっています。

(注)
定義から、次の2つの関係が分かります。

(1) SWFが弱パレートであることと、$N$が任意の$a,b \in A$でdecisive coalitionであることとは必要十分。

(2) SWFが独裁的であることと、$N$の中で、任意の$a,b \in A$でdecisiveな人が少なくとも1人存在することとは必要十分。

これらの関係は後で証明で用います。主定理を示す為に、2つ補題を示します。それぞれ補題には名前が付いています。以下、SWFは弱パレートでかつIIAであるとします。

補題1 (Field Expansion Lemma)

$C \subseteq N$が、ある候補者のペア$a,b$に対して、弱decisiveであるとする。このとき、$C$は全ての候補者のペアに対して、decisiveである。(弱であるだけではない)

補題1の証明

弱パレートでIIAなSWFに対して、適当な順序を与えてやって証明を目指します。正直、少しややこしいです。候補者が3人も以下と同じような議論が可能です。ここでは、候補者は4人以上であるとします。$a,b$とはそれぞれ異なる候補者$a',b'$を任意に取ってきます。
まず、順序$(>_1',...,>_n')\in R(A)$を$i \in C$について

$$a'>_i' b'$$

になっているものとします。
また、順序$(>_1,...,>_n)\in R(A)$を、$i \in C$について

$$a'>_i a>_i b>_i b'$$

でかつ、$j\notin C$について

$$a'>_j a,\ b>_j b',\ b>_ja$$

で、さらに$a',b'$の$>_j$の相対的順序は$>_j'$と同じように、定めます。

このとき、順序$(>_1,...,>_n)$を入力として、$C$は$a,b$に対して弱decisiveより、結果の順序は$a>b$になります。また、弱パレートなので、$a'>a$と$b> b'$が成立します。これらから推移律より、$a'>b'$が成り立ちます。さて、ここで順序$(>_1',...,>_n')$と$(>_1,...,>_n)$について、$a'$と$b'$の相対的順序は等しいです。よって、IIAの性質から、$a'>'b'$も成り立ちます。

decisive coalitionの定義から、少なくとも$C$に入っているものが$a'>_ib'$になっている順序を考えるだけで良く、それは今順序$(>_1',...,>_n')$に対応するので、$a'>'b'$という結果から、$C$はペア$a',b'$に対してdecisiveであることが示されました。$a',b'$は任意だったので、補題1が示されたことになります。

補題2 (Group Contraction Lemma)

任意のdecisiveな集合$C \subseteq N$　$(|C|\geq 2)$について、$C$は次の条件を満たすような2つの部分集合$C_1,C_2 ( \neq \emptyset )$に分けることができる。条件とは、$C_1 \cup C_2=C$かつ$C_1 \cap C_2 = \emptyset$で、さらに、$C_1$か$C_2$のどちらかは全ての候補者のペアに関してdecisive coalitionになっている事である。

補題2の証明

候補者から異なる3人$a,b,c \in A$を取ってきます。さらに、順序$(>_1,...,>_n)$を

$$a>_ib>_ic\ \ (\forall i \in C_1),$$$$b>_jc>_ja\ \ (\forall j\in C_2),$$$$c>_ka>_kb\ \ (\forall k \in N \setminus (C_1\cup C_2))$$

と定めます。$C$はdecisiveより、全体として$b>c$が成立します。順序の完全性から、$a,c$について、$a>c$か$c\geq a$が成立しています。

(１) $a>c$のとき。今、$\forall i \in C_1$について$a>_ic$で、$\forall j \notin C_1$について$c>_ja$が成立しています。よって、$C_1$は$a,c$について弱decisiveです。補題1から、$C_1$は全ての候補者のペアに関してdecisiveになります。

(２)$c\geq a$のとき。$b>c$と合わせて推移律より$b>a$になります。(1)と同様に考えられて、$C_2$は$b,a$について弱decisive。よって、$C_2$は全ての候補者のペアに関してdecisiveになります。

順序をこちらで1つ定めて証明をしましたが、IIAから相対的順序のみを考えれば、補題1の証明でもあったように、他の順序でもdecisiveであることを示すことができます。

定理の証明

decisive coalitionの定義した後の注釈で述べたことと補題を使えば定理の証明は完了します。SWFは弱パレートより、$N$はdecisive coalition。補題2を繰り返すと、$N$のうちある1人についてdecisiveな集合が存在します。これはつまり、SWFが独裁的であることを意味します。よって、証明終了になります。

まとめ

アローの不可能性定理の証明を見てきて、推移律は強い条件なのではないかと思えてしまいました。ただ、順序として推移律は基本的な定義の一部であり、難しいところです。現実の選好に関しても、賛否両論ありそうですが、仮定としてそこまで強くないようにも思えます。
また、証明でdecisiveな集合を考えるのは割と本質なような気がしますが、いまいち他の分野の議論とイメージで一致するものが分かりません。
まあ、複数の個人から上手に社会全体の順序を定めることの困難さの一端を見ることができ、面白いです。

参考文献

Brandt, F., Conitzer, V., Endriss, U., Lang, J., & Procaccia, A. D. (Eds.). (2016).$\textit{ Handbook of computational social choice.}$ Cambridge University Press.