社会選択理論(social choice theory)とは、多くの人の選好を集めて集団の選択や順位を決める規則を、規則に課す公理から数学的に調べる分野である。候補が 2 つなら、匿名性・中立性・正の反応性をもつ規則は多数決に限る(May の定理)。候補が 3 つ以上では 2 つずつの多数決が循環することがあり、Borda 得点などの位置得点法は 1 対 1 で全勝する候補を選ばないことがある。Pareto 条件と個人の最小限の自由が両立しないという Sen の定理や、Arrow の不可能性定理がこの分野の基本的な結果である。
社会選択理論(social choice theory)は、多くの人の好み(選好)を集めて、集団としての選択や順位を決める規則を数学的に調べる分野である。選挙の投票方式、委員会の議決、審査員の採点の集計などが対象で、規則に望ましい性質を公理として課し、その性質をもつ規則がどれだけあるか(1 つに決まるか、存在しないか)を調べる。
候補が 2 つなら、多数決が自然な規則である。May の定理(thm-sc-may)は、有権者を平等に扱い、候補を平等に扱い、支持が増えれば結果が良くなる、という 3 つの性質をもつ規則が多数決ただ 1 つであることを示す。ところが候補が 3 つ以上になると事情が変わる。2 つずつの多数決は循環しうるし(prop-sc-cycle)、得点で順位を付ける方式は、他のすべての候補に 1 対 1 で勝つ候補を選ばないことがある(ex-sc-positional)。こうした困難の極端な形が、全会一致と独立性を満たす順位の集計規則は独裁しかないという Arrowの不可能性定理 である。
この記事は社会選択理論の入口として、基本の定義、May の定理、Condorcet の考え方と Borda 得点の関係(prop-sc-borda、cor-sc-borda-condorcet)、個人の自由と全会一致が両立しないという Sen の定理(thm-sc-sen)を証明つきで述べ、代表的な投票方式を性質で比べる。
候補(選択肢)の有限集合を $X$、その個数を $m=|X|$、有権者を $1,\dots,n$ とする。$X$ 上の 全順序 全体を $\mathcal L(X)$ と書き、$A\succ B$ を「$A$ を $B$ より好む」と読む。
$\pi=(\succ_1,\dots,\succ_n)\in\mathcal L(X)^n$ を 選好プロファイル という。
この記事で比べる規則は次のとおりである。いずれも同点は、あらかじめ決めた順に従って解消するとする。
プロファイル $\pi$ と候補 $A\ne B$ に対し、$A$ を $B$ より好む人数を
$$
N_\pi(A,B)=\#\{i\mid A\succ_iB\}
$$
と書く。$N_\pi(A,B)+N_\pi(B,A)=n$ である。$N_\pi(A,B)>n/2$ のとき「$A$ は $B$ に 1 対 1 で勝つ」という。
Condorcet 勝者はあれば 1 人である(2 人いれば互いに相手に勝つことになる)。$n$ が奇数なら、どの 2 候補の間でも勝ち負けが決まり、1 対 1 の勝ち負けは候補の上の完全な向きをもつ 二項関係 になる。これが推移的でないとき、Condorcet 勝者がないことがある。
この記事の主張が使える条件は次のとおりである。
| 量・主張 | 式・内容 | 根拠 |
|---|---|---|
| プロファイルの総数 | $(m!)^n$ | 定義 |
| 1 対 1 の得票 | $N_\pi(A,B)+N_\pi(B,A)=n$ | def-sc-condorcet |
| 候補 2 つの規則で匿名・中立・正の反応性 | 多数決に限る | thm-sc-may |
| 3 人 3 候補で一様に選ぶとき循環する確率 | $\dfrac{12}{216}=\dfrac1{18}$ | prop-sc-cycle |
| Borda 得点 | $\beta(A)=\sum_{B\ne A}N_\pi(A,B)$ | prop-sc-borda |
| Borda 得点の平均 | $\dfrac{n(m-1)}2$ | prop-sc-borda |
| Condorcet 勝者の Borda 得点 | 平均より大 | cor-sc-borda-condorcet |
| Condorcet 敗者 | Borda 得点で 1 位にならない | cor-sc-borda-condorcet |
| Pareto・最小限の自由・非循環 | 同時には満たせない | thm-sc-sen |
| 規則 | 匿名 | 単調 | Condorcet 勝者の基準 | Condorcet 敗者の基準 | 根拠 |
|---|---|---|---|---|---|
| 相対多数 | ○ | ○ | × | × | ex-sc-plurality |
| Borda 得点 | ○ | ○ | × | ○ | ex-sc-borda、cor-sc-borda-condorcet |
| $a_1>a_2\ge a_3$ の位置得点法($m=3$) | ○ | ○ | × | 規則による | ex-sc-positional |
| 決選の繰り返し | ○ | × | × | ○ | KP17 p. 221 |
単調 とは、ある人が候補 $A$ を順位の中で上げ、他の候補の並びは変えないとき、$A$ の社会での順位が下がらないことである。位置得点法では $A$ の点だけが増えるか変わらず、他の候補の点は増えないので単調である。相対多数は位置得点法の 1 つなので、Condorcet 敗者の基準を満たさない位置得点法がある一方、Borda 得点は満たす。最後の行の性質は KP17 p. 221 による。単調性と Condorcet 勝者の基準を満たさないことは同頁の例で示され、Condorcet 敗者の基準は、敗者が最後の 2 人に残っても 1 対 1 で負けることから従う。
候補が $A$、$B$ の 2 つで、各人は「$A$ を支持」「どちらでもよい」「$B$ を支持」のどれかを申告するとし、これを $D_i=1,0,-1$ で表す。規則 は写像 $F:\{-1,0,1\}^n\to\{-1,0,1\}$ で、$F(D)=1,0,-1$ をそれぞれ「$A$ が選ばれる」「引き分け」「$B$ が選ばれる」と読む。多数決 は、$p(D)$ を $D_i=1$ の人数、$q(D)$ を $D_i=-1$ の人数として
$$
F_{\mathrm{maj}}(D)=\begin{cases}1&(p(D)>q(D))\\0&(p(D)=q(D))\\-1&(p(D)< q(D))\end{cases}
$$
で定める。
規則 $F$ について次のように定める。$\{-1,0,1\}$ には $-1< 0< 1$ の順序を入れ、$D\le D'$ は各成分で $D_i\le D'_i$ であることとする。
規則 $F:\{-1,0,1\}^n\to\{-1,0,1\}$ が匿名性・中立性・正の反応性をすべて満たすための必要十分条件は、$F=F_{\mathrm{maj}}$ であることである。
多数決は 3 条件を満たす $F_{\mathrm{maj}}(D)$ は $s(D)=p(D)-q(D)=\sum_iD_i$ の符号である。$s$ は成分の並べ替えで変わらないので匿名である。$s(-D)=-s(D)$ なので中立である。$D\le D'$、$D\ne D'$ なら $s(D')>s(D)$ なので、$s(D)\ge0$ から $s(D')>0$、すなわち $F_{\mathrm{maj}}(D')=1$ となり、正の反応性をもつ。
3 条件を満たせば多数決 $F$ が 3 条件を満たすとする。2 つの $D$、$D'$ で $(p(D),q(D))=(p(D'),q(D'))$ なら、$D'$ は $D$ の成分の並べ替えなので、匿名性から $F(D)=F(D')$ である。よって $F(D)=G(p(D),q(D))$ となる関数 $G$ がある($p+q\le n$)。$-D$ では $p$ と $q$ が入れ替わるので、中立性から $G(q,p)=-G(p,q)$ で、特に $G(p,p)=-G(p,p)$ より $G(p,p)=0$ である。
$p>q$ のとき $G(p,q)=1$ を示す。$(p(D'),q(D'))=(p,q)$ となる $D'$ をとり、$D'$ で $A$ を支持する $p$ 人のうち $p-q$ 人だけを「どちらでもよい」に替えたものを $D$ とする。$D$ では $A$ の支持も $B$ の支持も $q$ 人なので $F(D)=G(q,q)=0\ge0$ である。$D\le D'$、$D\ne D'$ なので、正の反応性から $F(D')=1$、すなわち $G(p,q)=1$ である。
$p< q$ のときは $G(p,q)=-G(q,p)=-1$ である。以上で、$G(p,q)$ は $p-q$ の符号に等しく、$F=F_{\mathrm{maj}}$ である。
3 つの条件はどれも外せない。重み付きの多数決、同数のとき $A$ を選ぶ規則、特別多数の規則がそれぞれ 1 つずつの条件だけを満たさない(ex-sc-may-counter)。
候補が 3 つ以上になると、2 つずつの多数決は順位を作らないことがある。3 人が $A\succ B\succ C$、$B\succ C\succ A$、$C\succ A\succ B$ と順位を付けると、$A$ は $B$ に、$B$ は $C$ に、$C$ は $A$ に 2 対 1 で勝つ(Condorcet の逆理)。これがどれくらい起こるかを数える。
$n=3$、$m=3$ とし、各人が 6 通りの順位から独立に一様に 1 つを選ぶとする。2 つずつの多数決が循環する(Condorcet 勝者がない)確率は $\frac{12}{216}=\frac1{18}$ である。循環するのは、巡回する 3 つの順位 $A\succ B\succ C$、$B\succ C\succ A$、$C\succ A\succ B$ を 1 人ずつがとるか、その逆向きの 3 つ $A\succ C\succ B$、$C\succ B\succ A$、$B\succ A\succ C$ を 1 人ずつがとるときに限る。
$n=3$ は奇数なので、どの 2 候補の間でも 1 対 1 の勝ち負けが決まる。3 候補の上の完全な向きは、推移的(勝者がいる)か循環かのどちらかである。循環が $A\to B\to C\to A$($A$ が $B$ に勝つ、など)の向きのときを数える。
3 本の矢印 $A\succ B$、$B\succ C$、$C\succ A$ のそれぞれについて、その向きに順位を付けた人を「支持者」と呼ぶ。勝つためには各矢印に 2 人以上の支持者が要るので、支持の総数は $6$ 以上である。一方、1 人の順位は推移的なので、3 本すべてを支持することはなく(支持すると $A\succ B\succ C\succ A$ となる)、1 人の支持は 2 本以下で、総数は $6$ 以下である。よって各人はちょうど 2 本を支持し、各矢印の支持者はちょうど 2 人である。
ちょうど 2 本を支持する順位は $A\succ B\succ C$($A\succ B$ と $B\succ C$)、$B\succ C\succ A$($B\succ C$ と $C\succ A$)、$C\succ A\succ B$($C\succ A$ と $A\succ B$)の 3 つで、残りの 3 つの順位は 1 本だけを支持する。この 3 つの順位をとる人数を $x,y,z$ とすると $x+y+z=3$ で、各矢印の支持者が 2 人であることから $x+z=x+y=y+z=2$、すなわち $x=y=z=1$ である。3 人への割り振りは $3!=6$ 通りある。逆向きの循環も同じく 6 通りで、合わせて 12 通り、確率は $12/6^3=1/18$ である。
どのプロファイル $\pi$ と候補 $A$ についても
$$
\beta(A)=\sum_{B\ne A}N_\pi(A,B)
$$
が成り立つ。とくに Borda 得点の候補にわたる平均は $\dfrac{n(m-1)}2$ である。
有権者 $i$ が $A$ を $k$ 位に置くと、$A$ が得る点は $m-k$ で、これは $i$ の順位で $A$ より下にいる候補の数に等しい。したがって、$i$ が $A$ に与える点は、$A\succ_iB$ となる $B$ の個数である。$i$ について足すと
$$
\beta(A)=\sum_{i=1}^n\#\{B\mid A\succ_iB\}=\sum_{B\ne A}\#\{i\mid A\succ_iB\}=\sum_{B\ne A}N_\pi(A,B)
$$
となる。各人は合計 $0+1+\dots+(m-1)=\frac{m(m-1)}2$ 点を配るので、得点の総和は $\frac{nm(m-1)}2$、平均は $\frac{n(m-1)}2$ である。
Condorcet 勝者の Borda 得点は平均 $\frac{n(m-1)}2$ より大きく、Condorcet 敗者の Borda 得点は平均より小さい。とくに Condorcet 敗者は、Borda 得点で 1 位にならない(同点の 1 位にもならない)。
Condorcet 勝者 $A$ では各 $B\ne A$ について $N_\pi(A,B)>\frac n2$ なので、prop-sc-borda から $\beta(A)>(m-1)\frac n2$ である。Condorcet 敗者 $L$ では各 $B\ne L$ について $N_\pi(L,B)< \frac n2$ なので $\beta(L)< \frac{n(m-1)}2$ である。平均より小さい候補があれば平均より大きい候補もあるので、$L$ の得点は最大でない。
ただし Condorcet 勝者が Borda 得点で 1 位になるとは限らない(ex-sc-borda)。1 対 1 で僅差で勝つ候補より、多くの人に大差で好まれる候補のほうが Borda 得点は高くなりうる。Borda 得点は好みの強さ(順位の差)を数え、Condorcet の考え方は 1 対 1 の勝ち負けだけを見る。どちらがよいかは公理の選び方の問題である。
社会の選択を、候補の間の 社会の選好 $P_\pi$(候補の上の非対称な 二項関係。$xP_\pi y$ は「社会は $y$ より $x$ を選ぶ」)で表す。各集合から $P_\pi$ で負けない候補を選ぶためには、$P_\pi$ に有向閉路($x_1P_\pi x_2P_\pi\cdots P_\pi x_kP_\pi x_1$)がないこと、すなわち 非循環 であることが要る。閉路があれば、閉路の候補の集合には負けない候補がない。
プロファイルごとに社会の選好 $P_\pi$ を与える規則について、次のように定める。
自分の部屋の壁の色のように、本人だけが決めてよい事柄があるという考えを、最も弱い形で表したのが最小限の自由である。
すべてのプロファイルで定義され、Pareto 条件と最小限の自由を満たし、どのプロファイルでも社会の選好が非循環である規則は存在しない。
規則がこれらの条件をすべて満たすとして矛盾を導く。$i,j$ と対 $\{x,y\}$、$\{z,w\}$ を最小限の自由のものとする。2 つの対は異なるので、共通の候補は 1 つか 0 である。$i,j$ 以外の有権者を「ほか」と呼ぶ。
共通の候補が 1 つのとき 名前を付け替えて、$i$ の対を $\{x,y\}$、$j$ の対を $\{y,z\}$($x,y,z$ は異なる)とする。プロファイルを
$$
i:\ z\succ x\succ y,\qquad j:\ y\succ z\succ x,\qquad \text{ほか}:\ z\succ x\succ y
$$
とする。$i$ は $x\succ_iy$ なので $xPy$、$j$ は $y\succ_jz$ なので $yPz$ である。全員が $z\succ x$ なので Pareto 条件から $zPx$ である。$xPyPzPx$ は閉路である。
共通の候補がないとき $x,y,z,w$ は異なる。プロファイルを
$$
i:\ w\succ x\succ y\succ z,\qquad j:\ y\succ z\succ w\succ x,\qquad \text{ほか}:\ w\succ x\succ y\succ z
$$
とする。$i$ から $xPy$、$j$ は $z\succ_jw$ なので $zPw$ である。全員が $w\succ x$ と $y\succ z$ なので、Pareto 条件から $wPx$、$yPz$ である。$xPyPzPwPx$ は閉路である。
どちらの場合も非循環に反する。(候補の他の部分の順位は任意に補ってよい。)
この定理は、全会一致(Pareto 条件)という弱い要請と、個人に小さな決定権を認める要請とが、選択の整合性のもとでは両立しないことを示す。Arrowの不可能性定理 と違い、独立性の条件を使わない。
順位の規則に全会一致と「2 候補の社会での上下はその 2 候補についての各人の上下だけで決まる」という独立性を課すと、候補が 3 つ以上なら独裁しか残らない。これが Arrowの不可能性定理 で、Condorcet の逆理(prop-sc-cycle)が多数決以外でも避けられないことを示す。当選者を 1 人選ぶ規則についても、偽の順位を申告して得をする人がいない規則は、すべての候補を選びうるかぎり候補が 3 つ以上なら独裁しかない(Gibbard–Satterthwaite の定理、KP17 Theorem 13.4.2、p. 220)。一方、選好を単峰的なものに制限すると、有権者が奇数人なら 2 つずつの多数決が順位を作る。その主張と証明は Arrowの不可能性定理 の記事にある。
具体的なプロファイルで規則を比べるときは、次の順に進める。
20 人のうち 9 人が $A\succ B\succ C$、6 人が $B\succ C\succ A$、5 人が $C\succ B\succ A$ とする。1 位の票は $A$ が 9、$B$ が 6、$C$ が 5 で、相対多数は $A$ を選ぶ。ところが 1 対 1 では $B$ が $A$ に $11$ 対 $9$、$C$ も $A$ に $11$ 対 $9$ で勝ち、$A$ は Condorcet 敗者である。$B$ は $C$ に $15$ 対 $5$ で勝つので $B$ が Condorcet 勝者である。比率 45%・30%・25% のこの例は KP17 Figure 13.2(p. 217)にある。
5 人のうち 3 人が $A\succ B\succ C$、2 人が $B\succ C\succ A$ とする。$A$ は $B$ にも $C$ にも $3$ 対 $2$ で勝つ Condorcet 勝者である。Borda 得点は $\beta(A)=3\cdot2=6$、$\beta(B)=3\cdot1+2\cdot2=7$、$\beta(C)=2\cdot1=2$ で $B$ が 1 位になる。prop-sc-borda で検算すると、$\beta(B)=N(B,A)+N(B,C)=2+5=7$ である。平均は $\frac{5\cdot2}2=5$ で、cor-sc-borda-condorcet のとおり $\beta(A)=6>5$ だが、$B$ はそれ以上を得ている。3 人と 2 人の比を 60% と 40% にした例が KP17 p. 222 にある。
81 人の順位が次のとおりとする。
| 人数 | 30 | 1 | 29 | 10 | 10 | 1 |
|---|---|---|---|---|---|---|
| 1 位 | $A$ | $A$ | $B$ | $B$ | $C$ | $C$ |
| 2 位 | $B$ | $C$ | $A$ | $C$ | $A$ | $B$ |
| 3 位 | $C$ | $B$ | $C$ | $A$ | $B$ | $A$ |
1 対 1 では $N(A,B)=30+1+10=41>40.5$、$N(A,C)=30+1+29=60$ で、$A$ は Condorcet 勝者である。順位ごとの票数は、1 位が $A{:}\,31$、$B{:}\,39$、$C{:}\,11$、2 位が $A{:}\,39$、$B{:}\,31$、$C{:}\,11$ である。
$m=3$ の位置得点法 $(a_1,a_2,a_3)$ で $a_1>a_2\ge a_3$ とする。全員に $a_3$ を引き $a_1-a_3$ で割っても順位は変わらないので、$(1,s,0)$、$0\le s< 1$ とみてよい。点は
$$
A:\ 31+39s,\qquad B:\ 39+31s,\qquad C:\ 11+11s
$$
で、$B$ と $A$ の差は $8-8s>0$、$B$ と $C$ の差は $28+20s>0$ である。したがって $a_1>a_2$ のすべての位置得点法で $B$ が単独の 1 位になり、Condorcet 勝者 $A$ は選ばれない。$a_1=a_2$($s=1$)のときは $A$ と $B$ が同点になる。このプロファイルは KP17 Figure 13.12(p. 223)にある。
$n=3$ とする。
1 冊の本について、候補を「1 さんが読む($x$)」「2 さんが読む($y$)」「誰も読まない($z$)」とする。1 さんは本を嫌い $z\succ x\succ y$(自分が読むくらいなら誰も読まないほうがよいが、2 さんが読むよりは自分が読むほうがまし)、2 さんは本を好み、1 さんに読ませたいので $x\succ y\succ z$ とする。1 さんは自分が読むかどうか $\{x,z\}$、2 さんも自分が読むかどうか $\{y,z\}$ で決定的とする。1 さんの好みから $zPx$、2 さんの好みから $yPz$ である。2 人とも $x\succ y$ なので、Pareto 条件から $xPy$ となり、$xPyPzPx$ が閉路になる。2 つの対は $z$ を共有しており、prf-sc-sen の 1 つ目の場合で名前を付け替えたものである。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| May:匿名性 | 重み付きの多数決 $\operatorname{sgn}(2D_1+D_2+D_3)$ | 中立・正の反応性をもつが多数決でない(ex-sc-may-counter の 1) |
| May:中立性 | 同数なら $A$ を選ぶ規則 | 匿名・正の反応性をもつが多数決でない(ex-sc-may-counter の 2) |
| May:正の反応性 | 特別多数($p>2q$ で $A$) | 匿名・中立だが多数決でない(ex-sc-may-counter の 3) |
| May:候補が 2 つ | 3 候補の 2 つずつの多数決 | 循環して当選者が決まらない(prop-sc-cycle) |
| Sen:Pareto 条件 | $i$ と $j$ の決定的な対だけで $P$ を定め、他の対は比べない | $P$ の弧は 2 本以下で非循環、最小限の自由を満たす |
| Sen:最小限の自由 | 有権者 $i$ の順位をそのまま $P$ にする | Pareto 条件と非循環を満たす($j$ は決定的でない) |
| Sen:非循環 | 決定的な対と Pareto 条件で決まる対だけを $P$ に入れる | Pareto 条件と最小限の自由を満たすが、prf-sc-sen のプロファイルで閉路ができる |
| Sen:すべてのプロファイルで定義 | 全員が同じ順位をもつプロファイルだけに限り、その順位を $P$ にする | 3 条件を満たす |
Sen の行の 1 つ目では、2 つの決定的な対が異なるので、$P$ の弧は互いに異なる対の上に高々 2 本で、閉路(2 本なら同じ対の両向きが要る)はできない。3 つ目の規則が非対称であることは、Pareto 条件で決まる向きが決定的な人の向きと一致することから分かる。
| 誤り | 正しくは | なぜ |
|---|---|---|
| 多数決なら矛盾は起きない | 候補が 3 つ以上なら 2 つずつの多数決は循環しうる | prop-sc-cycle |
| Borda 得点で 1 位なら Condorcet 勝者 | 一致しないことがある | ex-sc-borda |
| 点の付け方を工夫すれば Condorcet 勝者をいつも選べる | どの位置得点法でも Condorcet 勝者が単独の 1 位にならないプロファイルがある($a_1>a_2$ なら別の候補が 1 位) | ex-sc-positional |
| Condorcet 敗者はどの規則でも選ばれない | 相対多数は選びうる | ex-sc-plurality |
| May の定理は候補が何個でも多数決を特徴づける | 候補が 2 つの場合の定理である | 3 候補では多数決が順位を作らない |
| 自由の尊重と全会一致は両立する | 選択の整合性(非循環)と合わせると両立しない | thm-sc-sen |
| 循環は珍しい例外にすぎない | 3 人 3 候補で一様に選ぶと確率 $1/18$ で起こる | prop-sc-cycle |
規則の性質(匿名性・単調性・Condorcet 勝者の基準と敗者の基準)は KP17 §13.5(pp. 220–221)に、相対多数・決選の繰り返し・Borda 得点・位置得点法の分析は同書 §13.6(pp. 221–223)にある。Borda 得点が 1 対 1 の得票の和に等しいことも同書 p. 222 に述べられている。投票規則と順位の規則の定義は同書 §13.2(p. 218)にある。thm-sc-may、prop-sc-cycle、prop-sc-borda、cor-sc-borda-condorcet、thm-sc-sen の証明と、ex-sc-may-counter・ex-sc-sen の規則とプロファイルはこの記事で組み立てた。May の定理は K. May に、自由についての定理は A. Sen による。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する