Arrowの不可能性定理

同義語:Arrow's impossibility theoremArrowの定理

概要

Arrowの不可能性定理(Arrow's impossibility theorem)とは、候補が 3 つ以上あり有権者が有限人のとき、各人の順位から社会の順位を作る規則で、全会一致と無関係な選択肢からの独立性(2 候補の社会での上下は各人のその 2 候補の上下だけで決まる)を満たすものは、ある 1 人の順位をそのまま出す独裁の規則に限る、という定理である。2 候補ずつの多数決が循環しうること(Condorcet の逆理)とあわせて、投票や順位の集計の仕組みに課せる条件の限界を表す。候補が 2 つの場合、単峰的な選好に限る場合、無限人の場合には独裁でない規則がある。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 全順序, 二項関係

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$ と書いて 社会の順位 と呼ぶ。

3 つの性質

社会厚生関数 $F$ について、次のように定める。

  1. 全会一致:すべての $i$ で $A\succ_iB$ ならば $A\rhd_\pi B$。
  2. 無関係な選択肢からの独立性(IIA):2 つのプロファイル $\pi,\pi'$ で $\{i\mid A\succ_iB\}=\{i\mid A\succ'_iB\}$ ならば、$A\rhd_\pi B\iff A\rhd_{\pi'}B$。
  3. 独裁:ある有権者 $v$ があって、すべての $\pi$ で $\rhd_\pi=\succ_v$。この $v$ を 独裁者 という。

定理が使える条件は次のとおりである。

  • (i) 候補は 3 つ以上($m\ge3$)。
  • (ii) 有権者は有限人。
  • (iii) 各人はどんな全順序でも申告でき(定義域が $\mathcal L(X)^n$ 全体)、同順位はない。
  • (iv) 出力は全順序(推移的で、どの 2 候補も上下が決まる)。
    IIA は「$A$ と $B$ の社会での上下を決めるとき、第 3 の候補 $C$ の位置は見ない」という条件で、2 候補の比較に順位の強さや他の候補との距離を使うことを禁じる。

集計規則と条件の表

規則出力が全順序全会一致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 つの性質をすべて満たす規則がある。

主定理と証明

Arrowの不可能性定理

$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$

ピボットは $B$ を含まない対の独裁者

$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$ のままにする。

  • $A$ と $B$ の上下は、$\pi^3$ と $\pi^1$ で全員一致している($v$ 以外は $B$ の位置が同じ、$v$ は $\pi^1$ で $B$ が最下位、$\pi^3$ で $A\succ_vB$)。$B$ は $\rhd_{\pi^1}$ で最下位なので、IIA から $A\rhd_{\pi^3}B$。
  • $B$ と $C$ の上下は、$\pi^3$ と $\pi^2$ で全員一致している($v$ は $\pi^2$ で $B$ が最上位、$\pi^3$ で $B\succ_vC$)。$B$ は $\rhd_{\pi^2}$ で最上位なので、IIA から $B\rhd_{\pi^3}C$。
    推移性から $A\rhd_{\pi^3}C$ である。$\pi^3$ は $\pi$ から $B$ を動かし、$v$ については $A$ を最上位に上げただけなので、$A$ と $C$ の上下は $\pi$ と $\pi^3$ で全員一致している($v$ はもともと $A\succ_vC$)。IIA から $A\rhd_\pi C$ である。$\square$
2 つのピボットは同じ人

独裁の規則が全会一致と 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)。

計算の手順

与えられた集計規則やプロファイルについて、次の順に調べる。

  1. 対ごとの得票表を作る。 各対 $(A,B)$ について、$A\succ_iB$ となる人数 $N(A,B)$ を数える。$N(A,B)+N(B,A)=n$ である。
  2. Condorcet 勝者と循環を見る。 すべての $B\ne A$ に $N(A,B)>\frac n2$ となる $A$ を Condorcet 勝者という。$N(A,B)>\frac n2$ を矢印 $A\to B$ とし、有向閉路があれば 2 候補ずつの多数決は順位を作らない。
  3. IIA を確かめる。 規則の出力で $A\rhd B$ となるプロファイルについて、各人の $A$ と $B$ の上下を保ったまま第 3 の候補だけを動かし、出力の $A,B$ の上下が変わるかを見る。変わる例が 1 つあれば IIA は成り立たない。
  4. 全会一致を確かめる。 全員が $A\succ_iB$ のプロファイルで、出力が $A\rhd B$ かを見る。
  5. 独裁者を探す。 規則が全会一致と IIA を満たすなら、prf-lem-arrow-pivotal の手順(ある候補を 1 人ずつ最下位から最上位へ動かす)で、社会の順位が切り替わる人が独裁者である。

例題

Condorcet の逆理

冒頭の 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 と矛盾しないのは、出力が全順序にならないからである。

Borda 得点は IIA を満たさない

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 を満たし独裁でない
IIABorda 得点全会一致を満たし独裁でない(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$ は全順序であり、各人の峰の中央値が最上位である。

峰の中央値と 3 点への制限

$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 の注)。

Gibbard–Satterthwaite の定理

1 人の当選者を選ぶ規則 $f$ について、どの有権者も偽の順位を申告して得をできない(strategy-proof)とき、$f$ がすべての候補を値にとり、候補が 3 つ以上なら、$f$ は独裁(ある 1 人の 1 位がいつも当選者)である(KP17 Theorem 13.4.2、p. 220)。同書はこれを Arrow の定理に帰着して証明している(§13.8)。投票で戦略的な申告が避けられないことを示す定理で、ゲーム理論 の制度設計の議論の出発点の 1 つである。

関連項目

参考文献

[1]
Anna R. Karlin, Yuval Peres, Game Theory, Alive, American Mathematical Society, 2017, 著者公開版(2016 年 12 月 13 日)の番号と頁:p. 218 の Definition 13.2.2 と全会一致・IIA、p. 219 の Theorem 13.3.1 と相対多数から作る順位の規則が IIA を満たさないこと、p. 220 の Theorem 13.4.2、§13.7(pp. 224–226)の証明、§13.8、p. 230 の注

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する