Arrowの不可能性定理(Arrow's impossibility theorem)とは、候補が 3 つ以上あり有権者が有限人のとき、各人の順位から社会の順位を作る規則で、全会一致と無関係な選択肢からの独立性(2 候補の社会での上下は各人のその 2 候補の上下だけで決まる)を満たすものは、ある 1 人の順位をそのまま出す独裁の規則に限る、という定理である。2 候補ずつの多数決が循環しうること(Condorcet の逆理)とあわせて、投票や順位の集計の仕組みに課せる条件の限界を表す。候補が 2 つの場合、単峰的な選好に限る場合、無限人の場合には独裁でない規則がある。
3 人が 3 つの案 $A,B,C$ を次のように順位づけたとする。
| 有権者 | 1 位 | 2 位 | 3 位 |
|---|---|---|---|
| 1 | $A$ | $B$ | $C$ |
| 2 | $B$ | $C$ | $A$ |
| 3 | $C$ | $A$ | $B$ |
2 案ずつ多数決をとると、$A$ は $B$ に $2$ 対 $1$ で、$B$ は $C$ に $2$ 対 $1$ で、$C$ は $A$ に $2$ 対 $1$ で勝つ。個人の順位はどれも矛盾がないのに、多数決で作った社会の順位は $A>B>C>A$ と循環し、順位にならない。これを Condorcet の逆理という。
では、多数決以外のうまい集計の規則はあるだろうか。K. Arrow は、すべての人の順位を入力として社会の順位を出力する規則に、2 つの穏やかな条件――全員が $A$ を $B$ より上に置くなら社会もそうする(全会一致)、社会での $A$ と $B$ の上下は各人の $A$ と $B$ の上下だけで決まる(無関係な選択肢からの独立性)――を課すと、案が 3 つ以上あるかぎり、そのような規則は「ある 1 人の順位をそのまま社会の順位にする」独裁の規則しかないことを示した。これが Arrowの不可能性定理(Arrow's impossibility theorem)である。
この記事では、定理を正確に述べ、ピボットとなる有権者を見つける短い証明を示す。さらに、代表的な集計規則がどの条件を満たすかの表、条件を確かめる手順、条件を 1 つずつ外したときに独裁でない規則が作れること(単峰的な選好での多数決、無限人の有権者と超フィルターなど)を例とともに述べる。投票・委員会の決定・推薦順位の統合など、順位を集める仕組みを設計するときの限界を示す定理である。
$X$ を候補(選択肢)の有限集合とし、$m:=|X|$ とする。有権者を $1,\dots,n$ とする。$X$ 上の 全順序(同順位のない順位)全体を $\mathcal L(X)$ と書き、順位 $\succ\in\mathcal L(X)$ で $A\succ B$ は「$A$ を $B$ より上に置く」と読む。
$\pi=(\succ_1,\dots,\succ_n)\in\mathcal L(X)^n$ を 選好プロファイル という。写像 $F:\mathcal L(X)^n\to\mathcal L(X)$ を 社会厚生関数(順位の集計規則)といい、$F(\pi)$ を $\rhd_\pi$ と書いて 社会の順位 と呼ぶ。
社会厚生関数 $F$ について、次のように定める。
定理が使える条件は次のとおりである。
| 規則 | 出力が全順序 | 全会一致 | IIA | 独裁でない | 根拠 |
|---|---|---|---|---|---|
| 2 候補ずつの多数決($n\ge3$ 奇数) | × | ○ | ○ | ○ | ex-arrow-condorcet |
| Borda 得点(同点は固定の順で) | ○ | ○ | × | ○($n\ge2$) | ex-arrow-borda |
| 相対多数で 1 位を決め、残りで繰り返す | ○ | ○ | × | ○($n\ge3$) | KP17 p. 219 |
| 独裁($v$ の順位をそのまま出す) | ○ | ○ | ○ | × | 定義から |
| 定数(いつも同じ順位を出す) | ○ | × | ○ | ○($n\ge2$) | ex-arrow-table |
| 単峰的な選好に限った多数決($n$ 奇数) | ○ | ○ | ○ | ○($n\ge3$) | prop-arrow-black |
| 超フィルターによる規則(無限人) | ○ | ○ | ○ | ○ | prop-arrow-ultrafilter |
Borda 得点は、各人が $k$ 位の候補に $m-k$ 点を与え、合計点の順に並べる規則である。最後の 2 行は定理の条件 (iii)・(ii) を外した場合で、そのときは 4 つの性質をすべて満たす規則がある。
$m\ge3$、$n\ge1$ とする。社会厚生関数 $F:\mathcal L(X)^n\to\mathcal L(X)$ が全会一致と IIA を満たすならば、$F$ は独裁である。逆に、独裁の規則は全会一致と IIA を満たす。
ある候補 $B$ を全員が最下位から 1 人ずつ最上位へ動かすと、社会での $B$ の位置が最下位から最上位へ一気に変わる瞬間がある(lem-arrow-pivotal)。そのとき動かした有権者が独裁者であることを、IIA と推移性で示す。証明は prf-thm-arrow-main にある。
以下、$F$ は全会一致と IIA を満たすとする。候補 $B$ がある人の順位で最上位か最下位にあるとき、$B$ はその人にとって 端 にあるという。
プロファイル $\pi$ で、候補 $B$ がすべての有権者にとって端にあるならば、$B$ は社会の順位 $\rhd_\pi$ でも最上位か最下位にある。
そうでないとすると、$A\rhd_\pi B\rhd_\pi C$ となる候補 $A,C$ がある。各有権者の順位で、$C$ が $A$ より下にあれば $C$ を $A$ のすぐ上に動かしたプロファイルを $\pi'$ とする。$B$ は端にあるので、この操作で $A$ と $B$、$B$ と $C$ の上下はどの人でも変わらない($B$ が最上位なら $C$ は動いても $B$ の下、最下位なら上のまま)。IIA から $A\rhd_{\pi'}B$、$B\rhd_{\pi'}C$ で、推移性から $A\rhd_{\pi'}C$ である。一方 $\pi'$ では全員が $C\succ'_iA$ なので、全会一致から $C\rhd_{\pi'}A$ であり、矛盾である。$\square$
各候補 $B$ について、有権者 $v$ とプロファイル $\pi^1,\pi^2$ で次を満たすものがある:$\pi^1$ と $\pi^2$ は $v$ の順位だけが違い、$B$ は $\pi^1$ では $v$ にとって最下位、$\pi^2$ では最上位である。$B$ は両方のプロファイルですべての人にとって端にある。$B$ は $\rhd_{\pi^1}$ で最下位、$\rhd_{\pi^2}$ で最上位である。この $v$ を $B$ のピボット という。
全員が $B$ を最下位に置くプロファイル $\sigma^0$ をとり、$\sigma^k$ を、有権者 $1,\dots,k$ が(他の候補の順序は変えずに)$B$ を最上位へ移したものとする。全会一致から $B$ は $\rhd_{\sigma^0}$ で最下位、$\rhd_{\sigma^n}$ で最上位である。どの $\sigma^k$ でも $B$ は全員にとって端にあるので、lem-arrow-extremal から $B$ は $\rhd_{\sigma^k}$ で最上位か最下位である。$B$ が最上位になる最小の $k$ を $v$ とし、$\pi^1:=\sigma^{v-1}$、$\pi^2:=\sigma^v$ とすればよい。$\square$
$v$ が $B$ のピボットならば、$B$ と異なる相異なる候補 $A,C$ と任意のプロファイル $\pi$ について、$A\succ_vC$ ならば $A\rhd_\pi C$ である。
$\pi^1,\pi^2$ を lem-arrow-pivotal のプロファイルとする。$\pi$ から次のように $\pi^3$ を作る:$v$ 以外の各人 $i$ は、$B$ だけを $\pi^2$($\pi^1$ と同じ)での $i$ にとっての端の位置へ移す。$v$ は $A$ を最上位、$B$ を 2 位に置き、他の候補の順序は $\pi$ のままにする。
独裁の規則が全会一致と IIA を満たすのは定義から明らかなので、前半を示す。候補 $B$ をとり、lem-arrow-pivotal の $B$ のピボットを $v$、そのプロファイルを $\pi^1,\pi^2$ とする。lem-arrow-dictator-off から、$v$ は $B$ を含まない対の上下を決める。
$B$ を含む対 $\{A,B\}$ を考える。$m\ge3$ なので $C\notin\{A,B\}$ がとれる。$C$ のピボット $w$ は、lem-arrow-dictator-off から $C$ を含まない対、とくに $\{A,B\}$ の上下を決める。$B$ は $\rhd_{\pi^1}$ で最下位なので $A\rhd_{\pi^1}B$、$\rhd_{\pi^2}$ で最上位なので $B\rhd_{\pi^2}A$ である。$w$ がこの対の上下を決めるので、$w$ の $A$ と $B$ の上下は $\pi^1$ と $\pi^2$ で逆になっている。$\pi^1$ と $\pi^2$ で順位が違うのは $v$ だけなので $w=v$ である。よって $v$ は $\{A,B\}$ の上下も決め、すべての対で $A\succ_vC\Rightarrow A\rhd_\pi C$ となる。$\rhd_\pi$ と $\succ_v$ はともに全順序なので $\rhd_\pi=\succ_v$ である。$\square$
$m=2$ では lem-arrow-dictator-off が空の主張になり、最後の段の $C$ もとれない。実際、候補が 2 つなら多数決は 3 つの性質をすべて満たす(ex-arrow-table)。
与えられた集計規則やプロファイルについて、次の順に調べる。
冒頭の 3 人では $N(A,B)=N(B,C)=N(C,A)=2>\frac32$ で、手順 2 の矢印は $A\to B\to C\to A$ の閉路になる。2 候補ずつの多数決は全会一致(全員が $A\succ B$ なら $N(A,B)=n$)と IIA($A,B$ の比較は $N(A,B)$ だけで決まる)を満たし、$n\ge3$ のときどの 1 人の順位とも一致しないプロファイルがあるので独裁でもない。thm-arrow-main と矛盾しないのは、出力が全順序にならないからである。
5 人のプロファイル $\pi$ を、3 人が $A\succ B\succ C$、2 人が $B\succ C\succ A$ とする。Borda 得点(1 位 2 点、2 位 1 点)は $A$ が $6$、$B$ が $3+4=7$、$C$ が $2$ で、$B\rhd A$ である。$\pi'$ を、3 人が $A\succ C\succ B$、2 人が $B\succ A\succ C$ とすると、$A$ と $B$ の上下は各人で $\pi$ と同じ(3 人が $A$ を上、2 人が $B$ を上)だが、得点は $A$ が $6+2=8$、$B$ が $4$、$C$ が $3$ で $A\rhd' B$ である。第 3 の候補 $C$ の位置だけで $A,B$ の社会の上下が入れ替わった。
$m=3$、$n=2$ とする。IIA から、対 $\{A,B\}$ の社会での上下は「$A$ を上に置く人の集合」$S\subset\{1,2\}$ だけで決まる。全会一致から $S=\{1,2\}$ なら $A$ が上、$S=\emptyset$ なら $B$ が上で、残る $S=\{1\},\{2\}$ の決め方は $2^2=4$ 通りある。3 つの対で $4^3=64$ 通りの組合せのうち、36 通りのすべてのプロファイルで出力が推移的になるものを調べ尽くすと、ちょうど 2 つ(有権者 1 の独裁と有権者 2 の独裁)が残る。$n=3$ では対ごとに $2^6=64$ 通り、合わせて $64^3=262144$ 通りのうち 3 つ(各人の独裁)が残る。これは thm-arrow-main の主張どおりであり、数え上げは計算機で行った。
5 つの候補を数直線上の点 $1< 2< 3< 4< 5$ とし(政策の左右の位置など)、5 人の順位を
$$
1\succ2\succ3\succ4\succ5,\quad2\succ3\succ1\succ4\succ5,\quad4\succ3\succ5\succ2\succ1,\quad4\succ5\succ3\succ2\succ1,\quad5\succ4\succ3\succ2\succ1
$$
とする。各人の順位は自分の 1 位(峰)から離れるほど下がる(単峰的)。峰は $1,2,4,4,5$ で中央値は $4$ である。手順 1 の得票表から $4$ は他のすべての候補に $3$ 票以上で勝ち、多数決の社会の順位は $4\rhd3\rhd5\rhd2\rhd1$ と全順序になる。prop-arrow-black がこれを保証する。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| (i) $m\ge3$ | $m=2$、$n=3$ の多数決 | 全会一致・IIA を満たし、出力は全順序だが独裁でない |
| 全会一致 | 定数の規則($n\ge2$) | IIA を満たし独裁でない |
| IIA | Borda 得点 | 全会一致を満たし独裁でない(ex-arrow-borda) |
| (iv) 出力が全順序 | 2 候補ずつの多数決($n\ge3$ 奇数) | 全会一致・IIA を満たし独裁でない(ex-arrow-condorcet) |
| (iii) 定義域全体 | 単峰的な選好に限った多数決 | 全会一致・IIA・全順序の出力を満たし独裁でない(prop-arrow-black) |
| (ii) 有限人 | 超フィルターによる規則 | 4 つの性質をすべて満たす(prop-arrow-ultrafilter) |
1 行目:2 候補 $A,B$ では順位は 2 通りで、出力は自動的に全順序である。多数決は全会一致と IIA を満たし、2 人が $A\succ B$、1 人(有権者 1)が $B\succ A$ のとき出力は $A\rhd B$ なので、有権者 1 は独裁者でなく、同様に誰も独裁者でない。2 行目:定数の規則 $\rhd_\pi=\rhd_0$ は IIA を満たす。全員が $\rhd_0$ の逆順を申告すると全会一致に反する。$n\ge2$ なら、有権者 $v$ が $\rhd_0$ と違う順位を申告するプロファイルで出力は $\succ_v$ と違うので、独裁でない。$\square$
$X$ に全順序 $<$(軸)を固定する。順位 $\succ$ は、最上位 $p$ があって $x< y\le p$ または $p\le y< x$ ならば $y\succ x$ となるとき 単峰的 という。$n$ が奇数で各人の順位が単峰的ならば、2 候補ずつの多数決の関係 $A\rhd B:\iff N(A,B)>\frac n2$ は全順序であり、各人の峰の中央値が最上位である。
$n$ が奇数なので、相異なる $A,B$ について $A\rhd B$ と $B\rhd A$ のちょうど一方が成り立つ。まず峰の中央値 $p^*$ が全員に勝つことを示す。$x< p^*$ なら、峰が $p^*$ 以上の人($\frac{n+1}2$ 人以上)は $x< p^*\le p_i$ から $p^*\succ_ix$ なので $p^*\rhd x$ である。$x>p^*$ も同様である。
単峰的な順位を部分集合 $Y\subset X$ に制限したものも、軸を制限すれば単峰的である。実際、$Y$ での最上位を $p'$ とし、$x< y\le p'$($x,y\in Y$)とする。$y=p'$ なら $y\succ x$ は明らかで、$y\le p$ なら単峰性から $y\succ x$ である。$y\ne p'$ かつ $y>p$ なら $p< y< p'$ なので $y\succ p'$ となり、$p'$ が $Y$ の最上位であることに反する。$p'\le y< x$ の場合も同様である。
推移性を示す。$A\rhd B\rhd C$ で $C\rhd A$ とすると、3 点 $\{A,B,C\}$ に制限したプロファイルも単峰的で、上の議論からその峰の中央値は 3 点のどれにも勝つが、3 点はどれも他のどれかに負けているので矛盾である。よって $A\rhd C$ である。$\square$
有権者の集合を $\mathbb N$ とし、$\mathcal U$ を $\mathbb N$ 上の単項でない 超フィルター とする。プロファイル $(\succ_i)_{i\in\mathbb N}$ に対し $A\rhd B:\iff\{i\mid A\succ_iB\}\in\mathcal U$ と定めると、$\rhd$ は全順序であり、この規則は全会一致と IIA を満たし、独裁でない。
$S_{AB}:=\{i\mid A\succ_iB\}$ とおく。$S_{BA}$ は $S_{AB}$ の補集合なので、超フィルターの性質から $A\rhd B$ と $B\rhd A$ のちょうど一方が成り立つ。$S_{AB},S_{BC}\in\mathcal U$ ならば $S_{AB}\cap S_{BC}\subset S_{AC}$ で、共通部分も上位集合も $\mathcal U$ に入るので $A\rhd C$ である。全会一致は $\mathbb N\in\mathcal U$ から、IIA は定義が $S_{AB}$ だけによることから従う。$v$ が独裁者なら、$v$ だけが $A\succ B$ とするプロファイルで $A\rhd B$ となり $\{v\}\in\mathcal U$ だが、これは $\mathcal U$ が単項でないことに反する。$\square$
同じ構成を有限人の有権者で行うと、有限集合上の超フィルターは 1 点 $v$ を含む集合全体(単項)しかないので、規則は $v$ の独裁になる。単項でない超フィルターの存在が、無限人での反例を可能にしている。
| 誤り | 正しくは | なぜ |
|---|---|---|
| すべての投票制度は等しく悪い | 制度ごとに満たす性質が違い、比べる意味がある | 定理は 4 つの性質を同時に満たせないと言うだけ |
| 多数決なら矛盾は起きない | 2 候補ずつの多数決は循環しうる | Condorcet の逆理 |
| 候補が 2 つでも成り立つ | $m\ge3$ が必要 | 2 候補の多数決は独裁でない |
| IIA は「候補を 1 人取り下げても順位が変わらない」と同じ | プロファイルを替えても 2 候補の比較が他の候補の位置によらないこと | 候補の集合は固定している |
| 独裁者は全会一致の例外的な人 | 独裁者の順位が常に社会の順位そのもの | def-arrow-conditions の 3 |
定理は KP17 の Theorem 13.3.1(p. 219)で、同書は社会厚生関数を ranking rule、全会一致を unanimity、IIA を independence of irrelevant alternatives と呼び(p. 218)、証明(§13.7、pp. 224–226)は J. Geanakoplos によるものを基にしていると注記している(p. 230)。この記事の prf-thm-arrow-main はその証明の段を整理したもので、3 つ目の候補をとる段で $m\ge3$ を使う。prop-arrow-black の証明、prop-arrow-ultrafilter の証明、ex-arrow-count の数え上げは書き下ろしたものである。同順位を許す場合も同じ形の定理が成り立つ(KP17 p. 230 の注)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する