社会選択理論

同義語:社会的選択理論social choice theory

概要

社会選択理論(social choice theory)とは、多くの人の選好を集めて集団の選択や順位を決める規則を、規則に課す公理から数学的に調べる分野である。候補が 2 つなら、匿名性・中立性・正の反応性をもつ規則は多数決に限る(May の定理)。候補が 3 つ以上では 2 つずつの多数決が循環することがあり、Borda 得点などの位置得点法は 1 対 1 で全勝する候補を選ばないことがある。Pareto 条件と個人の最小限の自由が両立しないという Sen の定理や、Arrow の不可能性定理がこの分野の基本的な結果である。

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

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

社会選択理論(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$ を 選好プロファイル という。

  • 写像 $f:\mathcal L(X)^n\to X$ を 投票規則 という。1 人の当選者を選ぶ規則である。
  • 写像 $R:\mathcal L(X)^n\to\mathcal L(X)$ を 順位の規則(社会厚生関数)という。社会全体の順位を作る規則である。
    規則が 匿名 であるとは、有権者の番号を入れ替えても結果が変わらないことをいう。

この記事で比べる規則は次のとおりである。いずれも同点は、あらかじめ決めた順に従って解消するとする。

  • 相対多数:1 位に置かれた回数が最も多い候補を選ぶ。
  • 位置得点法:実数 $a_1\ge a_2\ge\dots\ge a_m$($a_1>a_m$)を決め、各人が $k$ 位の候補に $a_k$ 点を与え、合計点で並べる。$a=(1,0,\dots,0)$ が相対多数である。
  • Borda 得点:$a_k=m-k$ の位置得点法。候補 $A$ の合計点を $\beta(A)$ と書く。
  • 決選の繰り返し(instant runoff):1 位に置かれた回数が最も少ない候補を全員の順位から除くことを、1 人が過半数の 1 位を得るまで繰り返す。
対ごとの多数決と Condorcet 勝者

プロファイル $\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 で勝つ」という。

  • ほかのすべての候補に 1 対 1 で勝つ候補を Condorcet 勝者 という。
  • ほかのすべての候補に 1 対 1 で負ける候補を Condorcet 敗者 という。
    Condorcet 勝者があれば必ず選ぶ規則は Condorcet 勝者の基準 を満たすといい、Condorcet 敗者を決して選ばない規則は Condorcet 敗者の基準 を満たすという。

Condorcet 勝者はあれば 1 人である(2 人いれば互いに相手に勝つことになる)。$n$ が奇数なら、どの 2 候補の間でも勝ち負けが決まり、1 対 1 の勝ち負けは候補の上の完全な向きをもつ 二項関係 になる。これが推移的でないとき、Condorcet 勝者がないことがある。
この記事の主張が使える条件は次のとおりである。

  • 有権者は有限人で、各人は同順位のない全順序を申告する(May の定理だけは「どちらでもよい」も許す)。
  • 規則はすべてのプロファイルで定義されている(定義域の制限なし)。
  • 候補の数は、May の定理では 2、それ以外では 3 以上を主に考える。

公式の表

量・主張式・内容根拠
プロファイルの総数$(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 で負けることから従う。

主定理と証明

候補が 2 つのとき:May の定理

候補が $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} $$
で定める。

May の 3 条件

規則 $F$ について次のように定める。$\{-1,0,1\}$ には $-1< 0< 1$ の順序を入れ、$D\le D'$ は各成分で $D_i\le D'_i$ であることとする。

  1. 匿名性:$\{1,\dots,n\}$ の任意の置換 $\sigma$ について $F(D_{\sigma(1)},\dots,D_{\sigma(n)})=F(D)$。
  2. 中立性:$F(-D)=-F(D)$。候補の名前を入れ替えると結果も入れ替わる。
  3. 正の反応性:$F(D)\ge 0$、$D\le D'$、$D\ne D'$ ならば $F(D')=1$。引き分けか $A$ の勝ちのときに誰かが $A$ の側へ動けば、$A$ が勝つ。
May の定理

規則 $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 つ以上のとき:多数決の循環

候補が 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 の逆理)。これがどれくらい起こるかを数える。

3 人 3 候補で循環する確率

$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$ である。

Borda 得点と 1 対 1 の勝負

Borda 得点と 1 対 1 の得票

どのプロファイル $\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 得点

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 の勝ち負けだけを見る。どちらがよいかは公理の選び方の問題である。

個人の自由と全会一致:Sen の定理

社会の選択を、候補の間の 社会の選好 $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$)がないこと、すなわち 非循環 であることが要る。閉路があれば、閉路の候補の集合には負けない候補がない。

Pareto 条件と最小限の自由

プロファイルごとに社会の選好 $P_\pi$ を与える規則について、次のように定める。

  1. Pareto 条件:すべての $i$ で $x\succ_iy$ ならば $xP_\pi y$。
  2. 最小限の自由:2 人の異なる有権者 $i,j$ と、候補の 2 つの異なる対 $\{x,y\}$、$\{z,w\}$ があって、$i$ は $\{x,y\}$ で、$j$ は $\{z,w\}$ で 決定的 である。ここで $i$ が $\{x,y\}$ で決定的とは、すべての $\pi$ で $x\succ_iy\Rightarrow xP_\pi y$ かつ $y\succ_ix\Rightarrow yP_\pi x$ となることである。

自分の部屋の壁の色のように、本人だけが決めてよい事柄があるという考えを、最も弱い形で表したのが最小限の自由である。

Sen の定理

すべてのプロファイルで定義され、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の不可能性定理 の記事にある。

計算の手順

具体的なプロファイルで規則を比べるときは、次の順に進める。

  1. プロファイルを表にする:同じ順位をとる人数をまとめ、順位ごとに人数を書く。
  2. 1 対 1 の得票表を作る:各対について $N_\pi(A,B)$ を数える。$N_\pi(B,A)=n-N_\pi(A,B)$ なので半分だけでよい。
  3. Condorcet 勝者・敗者を探す:得票表で全勝・全敗の候補を探し、なければ循環を書き出す。
  4. 順位ごとの票数を数える:各候補が $k$ 位に置かれた回数 $v_k(A)$ を数える。位置得点法の点は $\sum_ka_kv_k(A)$ である。
  5. Borda 得点を検算する:$\beta(A)=\sum_k(m-k)v_k(A)$ と、得票表の行の和 $\sum_{B\ne A}N_\pi(A,B)$(prop-sc-borda)が一致することを確かめる。
  6. 規則ごとの当選者を比べる:相対多数、Borda 得点、決選の繰り返し、Condorcet 勝者を並べ、食い違いがあれば、どの性質の違いによるかを規則と性質の表で確かめる。

例題

相対多数は Condorcet 敗者を選びうる

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)にある。

Borda 得点は Condorcet 勝者を選ばないことがある

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 にある。

どの位置得点法でも Condorcet 勝者が単独の 1 位にならないプロファイル

81 人の順位が次のとおりとする。

人数3012910101
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)にある。

May の 3 条件の 1 つだけを外した規則

$n=3$ とする。

  1. 重み付きの多数決 $F(D)=\operatorname{sgn}(2D_1+D_2+D_3)$:誰かが $A$ の側へ動けば和は増えるので正の反応性をもち、中立である。$D=(1,-1,-1)$ では和が $0$ で引き分け、並べ替えた $(-1,1,-1)$ では和が $-2$ で $B$ の勝ちなので匿名でない。
  2. 同数なら $A$:$p\ge q$ なら $A$、$p< q$ なら $B$。匿名で正の反応性をもつが、全員が「どちらでもよい」のとき $A$ を選び、$F(-D)=-F(D)$ が $D=(0,0,0)$ で成り立たないので中立でない。
  3. 特別多数:$p>2q$ なら $A$、$q>2p$ なら $B$、それ以外は引き分け。匿名で中立だが、$D=(1,-1,0)$(引き分け)から 3 人目が $A$ へ動いた $(1,-1,1)$ は $p=2$、$q=1$ で引き分けのままなので、正の反応性をもたない。
本を読むのは誰か

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 による。

関連項目

参考文献

[1]
Anna R. Karlin, Yuval Peres, Game Theory, Alive, American Mathematical Society, 2017, 頁は著者公開版(2016-12-13)のもの:第 13 章 Social Choice and Voting。§13.1 Figure 13.2(p. 217)、§13.2(p. 218)、Theorem 13.4.2(p. 220)、§13.5(pp. 220–221)、§13.6(pp. 221–223、Figure 13.12 は p. 223)

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