中村ナンバー

協力ゲーム理論および社会選択理論において、中村ナンバー (なかむらナンバー、Nakamura 数、 Nakamura number) とは、投票ルールに代表される集合的意思決定ルールの合理性の度合いをはかる指標となる整数のことである。この名称は、以下の事実を証明した日本人ゲーム理論家中村健二郎 (1947-1979) による。

• 中村ナンバー未満の選択肢から選ぶ状況では、そのルールは必ず最適な選択肢を選び出せる（ただし、最適な選択肢が1つだけとは限らない）。

• 中村ナンバー以上の選択肢から選ぶ状況では、人々の選好の組合せにより当該ルールでは最適なものが定まらない場合がある。そのような状況は、投票のパラドックスに見られるように、選択肢 a が b より、b が c より、c が a より集団的に好まれるといったサイクルが存在する場合に発生する。

つまり、選択の合理性は選択肢数とこの数の大小関係により左右され、大きい中村ナンバーを持つルールほど多くの選択肢を矛盾なく扱える。

概要

中村ナンバーの正確な定義を与える前に、中村ナンバーを付与することのできる意思決定ルールの例を挙げる。 個人1, 2, 3, 4, 5 からなる「多数決ルール」では、多数派となる個人の集合全てを含む集合

$\{\{1,2,3\},\{1,2,4\},\{1,2,5\},\{1,3,4\},\{1,3,5\},\{1,4,5\},\{2,3,4\},\{2,3,5\},\{2,4,5\},\{3,4,5\},$

$\{1,2,3,4\},\{1,2,3,5\},\{1,2,4,5\},\{1,3,4,5\},\{2,3,4,5\},\{1,2,3,4,5\}\}$

が考えられる。このような集合（シンプルゲーム）が中村ナンバーを与えることのできる対象である。勝利提携（シンプルゲームの元である集合のこと）に属する個人が共有する選好が、社会（この例では5人からなる社会）全体の選好（社会選好）となる。

シンプルゲームの「中村ナンバー」とは、勝利提携からなる集合で、その集合に含まれる全ての勝利提携の共通部分が空集合となるようなもののうち、最も元の個数が少ない集合の元の個数のことである。よって、この例における中村ナンバーは3である。このことは、任意の2つの勝利提携の共通部分は少なくとも1人の同じ個人を含むが、$\{1,2,3\}$, $\{4,5,1\}$, $\{2,3,4\}$という3つの勝利提携の共通部分は空になることから確認できる。

中村の定理 (Nakamura, 1979) は、シンプルゲームが全ての選好順序に対して非空のコアを持つための必要条件（選択肢集合が有限の場合は十分条件でもある）として、選択肢の数がそのシンプルゲームの中村ナンバーよりも小さいことを挙げている。上記のシンプルゲームの例でいえば、この定理から選択肢が3個以上ある場合選好順序の選び方によってはコアに属する選択肢がなくなるということがわかる。

選択肢を「順序づける」ことに関しては、社会選択理論における「アローの不可能性定理」その困難さを指摘しているが、選択肢を「選ぶ」ことに関しては、中村の定理がより直接的な関連性を持っている。

定義の準備

シンプルゲーム

$N$ を個人からなる空でない集合とする。 $N$ の部分集合を提携という。提携の集合 $W$ をシンプルゲーム (投票ゲーム) という（それぞれの提携に 1 または 0 の値を与える提携ゲームと考えることもできる）。ここでは $W$ は空集合でなく、かつ空集合を含まないと仮定する。$W$ に属する提携は勝利提携、属さない提携は敗北提携という。シンプルゲーム $W$ が単調であるとは、任意の $S\in W$ と $S\subseteq T$について、$T\in W$ が成り立つことをいう。$W$ がプロパーであるとは、任意の $S\in W$ に対して $N\setminus S\notin W$ となることをいう。$W$ が強いとは、任意の $S\notin W$ に対して $N\setminus S\in W$ となることをいう。拒否権プレーヤーとは、すべての勝利提携に属する個人のことである。シンプルゲームが弱いとは、そのシンプルゲームが拒否権プレーヤーを含むことをいう。$W$ が有限であるとは、ある有限集合 $T\subseteq N$（キャリアと呼ばれることがある）が存在して、任意の提携 $S$ について$S\in W$ と $S\cap T\in W$が同値になることをいう。

$X$ を「選択肢」の集合とし、その濃度（要素数）$\mathrm{\#}X$ は最小でも2とする。ここで（強い、あるいは狭義の）選好とは、$X$ 上の非対称的な関係、すなわち $x\succ y$ (「$x$ は $y$ より好まれる」の意) ならば、$y\succ ̸x$ となる関係 $\succ$ を指す。選好 $\succ$ が非循環的である、あるいはサイクルを含まないとは、任意の有限個の選択肢 $x_1,\dots ,x_m$ について、もし $x_1\succ x_2$, $x_2\succ x_3$,…, $x_{m-1}\succ x_m$ ならば $x_m\succ ̸x_1$ となることをいう。非循環的な関係は非対称的であるため、選好に該当することに注意しなければならない。

(選好) プロファイルとは、個人の選好 $\underset{i}{\overset{p}{\succ }}$ の列 (リスト) $p=(\underset{i}{\overset{p}{\succ }}{)}_{i\in N}$ のことである。ここで、$x\underset{i}{\overset{p}{\succ }}y$ は個人 $i$ がプロファイル $p$ において、選択肢 $x$ を選択肢 $y$ より好むことを表している。

選好付きシンプルゲーム

シンプルゲーム $W$ とプロファイル $p$ のペア $(W,p)$ を選好付きシンプルゲーム（譲渡可能な効用を前提としない投票ゲーム）という。 $(W,p)$ が与えられたとき、任意の $x,y\in W$に対して、ある勝利提携 $S\in W$ が存在して、すべての $i\in S$ に対して $x\underset{i}{\overset{p}{\succ }}y$ となることを $x\underset{W}{\overset{p}{\succ }}y$ と表す。この $\underset{W}{\overset{p}{\succ }}$を $X$ 上の支配関係（社会選好）という。

選好付きシンプルゲーム

$(W,p)$

に対し、

$\underset{W}{\overset{p}{\succ }}$

によって支配されない選択肢全てからなる集合（つまり、

$\underset{W}{\overset{p}{\succ }}$

に関して

$X$

上で極大要素となる選択肢の全てからなる集合）を

$(W,p)$

のコアといい

$C(W,p)$

と表す。この定義は、

$C(W,p):=\{x\in W\mid$$y\underset{W}{\overset{p}{\succ }}x$

となる

$y\in X$

が存在しない

$\}$

と言い換えることができる。

定義

シンプルゲーム $W$ の中村ナンバー $\nu (W)$ とは、共通部分が空集合となるような勝利提携の集合のうち、最も小さな濃度（提携数）をもつ集合のその濃度のことである。なお、

• $\cap W={\cap }_{S\in W}S=\mathrm{\varnothing }$ (拒否権プレーヤーが存在しない) となるとき、$\nu (W)=\min \{\mathrm{\#}{W}^{\prime }:W^{\prime }\subseteq W;\cap W^{\prime }=\mathrm{\varnothing }\}$
• それ以外のとき $\nu (W)=+\mathrm{\infty }$ (任意の濃度より大きい)

であるとする。$W$が拒否権プレーヤーなしのシンプルゲームであれば、$2\le \nu (W)\le \mathrm{\#}N$ が成り立つ。

例

人数が有限の場合の例

（Austen-Smith and Banks (1999), Lemma 3.2 を参照）以下では $N=\{1,\dots ,n\}$（有限集合）、 $W$ は単調でプロパーとする.

• $W$ が拒否権プレーヤーなしの強いシンプルゲームなら、$\nu (W)=3$ である。
• $W$ が過半数ゲーム（半分を超える個人を含む提携を勝利提携とするシンプルゲーム）なら、$n\ne 4$ のケースでは $\nu (W)=3$ となり、$n=4$ のケースでは $\nu (W)=4$ となる。
• $W$ が $q$-ルール（すなわち $q$ 人以上の個人を含む提携を勝利提携とするシンプルゲーム）で、 $n/2<q<n$ のとき、$\nu (W)=[n/(n-q)]$ となる。ただし $[x]$ は $x$ 以上の最小の整数。

たかだか可算個の個人がいる場合の例

シンプルゲームに関わる代表的な性質（単調かどうか、プロパーかどうか、強いかどうか、拒否権プレーヤーなしかどうか、有限かどうか）がその中村ナンバーにあたえる制限については、Kumabe and Mihara (2008) が調べ上げている（その結果は以下の表「可能な中村ナンバー」に要約されている）。特に、アルゴリズムによって「計算可能」でかつ拒否権プレーヤーをもたないシンプルゲームが3より大きい中村ナンバーをもつとき、そのシンプルゲームはプロパーかつ強くないことが分かっている。

可能な中村ナンバー

タイプ	有限ゲーム	無限ゲーム
1111	3	3
1110	+∞	none
1101	≥3	≥3
1100	+∞	+∞
1011	2	2
1010	none	none
1001	2	2
1000	none	none
0111	2	2
0110	none	none
0101	≥2	≥2
0100	+∞	+∞
0011	2	2
0010	none	none
0001	2	2
0000	none	none

非循環的な選好に対する中村の定理

中村の定理 (Nakamura, 1979, Theorems 2.3 and 2.5). $W$ をシンプルゲームとする。非循環的な選好からなる任意のプロファイル $p$ にたいしてコア $C(W,p)$ が非空となることは、$X$ が有限かつ $\mathrm{\#}X<\nu (W)$ となることと同値である。

リマーク

• 中村の定理は、以下に近い形で (コアへの言及なく) 参照されることも多い (e.g., Austen-Smith and Banks, 1999, Theorem 3.2): 非循環的な選好からなる任意のプロファイル $p$ にたいして支配関係 $\underset{W}{\overset{p}{\succ }}$ が非循環的になることは、任意の有限な $B\subseteq X$ にたいして $\mathrm{\#}B<\nu (W)$ となることと同値である (Nakamura 1979, Theorem 3.1)。

• 定理中で「非循環的な選好からなる任意のプロファイル $p$ にたいして」を「否定推移的な (negatively transitive) 選好からなる任意のプロファイル $p$ にたいして」あるいは「線形順序である (すなわち推移的で total) 選好からなる任意のプロファイル $p$ にたいして」と言い換えても、得られたステートメントは正しい。

• 上記定理は $ℬ$-シンプルゲームに拡張できる。 ここで $ℬ$ は、$N$ の部分集合からなる任意のブール代数であり、それに属する要素を「提携」とみなす。$ℬ$ の例としては、ルベーグ可測集合の$\sigma$-代数などがある。「$ℬ$-シンプルゲーム」とは、$ℬ$ の部分族である。選好プロファイルは以下の意味で可測なものに限定するのが適切である: プロファイル $p$ が「可測である」とは、任意の $x,y\in X$ について、$\{i:x\underset{i}{\overset{p}{\succ }}y\}\in ℬ$ となることである。

サイクルを含み得る選好に対する中村の定理の変種

このセクションでは「非循環的な選好」という通常の仮定を捨てることにする。 そのかわり与えられた「アジェンダ」(agenda, 個人のグループが当面直面している「機会集合」) 上で極大要素を持つような選好をここでは考える。 単純な考察にするため、ここでは集合 $X$ 自体をアジェンダとみなすことにする。 選択肢 $x\in X$ が選好 $\underset{i}{\overset{p}{\succ }}$ に関して「極大 (要素) である」 (あるいは $\underset{i}{\overset{p}{\succ }}$ が「極大要素 $x$ を持つ」) とは、 $y\underset{i}{\overset{p}{\succ }}x$ となるような $y\in X$が存在しないことである。 もし選好が選択肢全体の集合上で非循環的であれば、その選好は任意の「有限」部分集合 $X$ 上で極大値を持つ。

中村の定理の変種 (variant) を述べる前に、「コア」を強めた解概念を導入しておく。 たとえある提携が存在してそれに属するすべての個人 $i$ が選択肢 $x$ に「不満を持っている」 (各 $i$ がなんらかのべつの選択肢 $y_i$ を $x$ より好むの意) としても、 選択肢 $x$ がコア $C(W,p)$ には属してしまうことがある。 次の解概念はそのような選択肢 $x$ を除外するものである:

選択肢 $x\in X$ が「多数不満なきコア」(core without majority dissatisfaction) $C^{+}(W,p)$ に属するとは、任意の $i\in S$ にとって $x$ が極大でない ($y_i\in X$ が存在して $y_i\underset{i}{\overset{p}{\succ }}x$ となる) ような勝利提携 $S\in W$ が存在しないことである。

以下の結果は容易に示すことができる: $C^{+}(W,p)$ は各人の選好の極大要素集合だけに依存し、それらの集合のユニオンにふくまれる。 また、任意の選好プロファイル $p$ について、$C^{+}(W,p)\subseteq C(W,p)$ となる。

中村定理の変種 (Kumabe and Mihara, 2011, Theorem 2). $W$ をシンプルゲームとする。以下の3つのステートメントは同値である:

1. $\mathrm{\#}X<\nu (W)$;
2. 極大要素を持つ選好からなる任意のプロファイル $p$ に対して多数不満なきコア $C^{+}(W,p)$ が非空となる;
3. 極大要素を持つ選好からなる任意のプロファイル $p$ に対してコア $C(W,p)$ が非空となる。

注意

• もとの中村の定理と異なり、この変種定理において $X$ が有限であることは、任意のプロファイル $p$ にたいして $C^{+}(W,p)$ あるいは $C(W,p)$ が非空となるための必要条件ではないことに注意。すなわち無限個の選択肢を持つアジェンダ $X$ 上でも、不等式 $\mathrm{\#}X<\nu (W)$ さえみたせば、それらコアに属する要素が存在する。
• 定理の 2, 3 中で「極大要素を持つ選好からなる任意のプロファイル $p$ にたいして」を「極大要素をひとつだけ持つ選好からなる任意のプロファイル $p$ にたいして」あるいは「極大要素を持ち線形順序である選好からなる任意のプロファイル $p$ にたいして」と言い換えても、得られたステートメントは正しい (Kumabe and Mihara, 2011, Proposition 1)。
• もとの中村の定理と同様、この変種定理は $ℬ$-シンプルゲームに拡張できる。さらにこの定理は「中村ナンバー」の概念を拡張することにより「勝利提携の族」$W^{\prime }\subseteq {ℬ}^{\prime }$ にも拡張できる (ステートメント 1, 2 が同値で、それらから 3 が導ける)。

関連項目

• アローの不可能性定理
• 多数決
• 投票の逆理