中村ナンバー

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

中村ナンバー未満の選択肢から選ぶ状況では、そのルールは必ず最適な選択肢を選び出せる（ただし、最適な選択肢が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^[2]) は、シンプルゲームが全ての選好順序に対して非空のコア^[3]を持つための必要条件（選択肢集合が有限の場合は十分条件でもある）として、選択肢の数がそのシンプルゲームの中村ナンバーよりも小さいことを挙げている。上記のシンプルゲームの例でいえば、この定理から選択肢が3個以上ある場合選好順序の選び方によってはコアに属する選択肢がなくなるということがわかる。^[5]

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

定義の準備

シンプルゲーム

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

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

選好付きシンプルゲーム

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

選好付きシンプルゲーム $(W,p)$ に対し、 $\succ _{W}^{p}$ によって支配されない選択肢全てからなる集合（つまり、 $\succ _{W}^{p}$ に関して $X$ 上で極大要素となる選択肢の全てからなる集合）を $(W,p)$ のコアといい $C(W,p)$ と表す。この定義は、

$C(W,p):=\{x\in W\mid$ $y\succ _{W}^{p}x$ となる $y\in X$ が存在しない $\}$

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

定義

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

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

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

例

人数が有限の場合の例

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

$W$ が拒否権プレーヤーなしの強いシンプルゲームなら、 $\nu (W)=3$ である。
$W$ が過半数ゲーム（半分を超える個人を含む提携を勝利提携とするシンプルゲーム）なら、 $n\neq 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)^[9] が調べ上げている（その結果は以下の表「可能な中村ナンバー」に要約されている）。特に、アルゴリズムによって「計算可能」で^[10]かつ拒否権プレーヤーをもたないシンプルゲームが3より大きい中村ナンバーをもつとき、そのシンプルゲームはプロパーかつ強くないことが分かっている。

可能な中村ナンバー^[11]
タイプ	有限ゲーム	無限ゲーム
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^[2]). $W$ をシンプルゲームとする。非循環的な選好からなる任意のプロファイル $p$ にたいしてコア $C(W,p)$ が非空となることは、 $X$ が有限かつ $\#X<\nu (W)$ となることと同値である。

リマーク

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

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

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

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

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

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

選択肢

x\in X

が「多数不満なきコア」(core without majority dissatisfaction)

C^{+}(W,p)

に属するとは、任意の

i\in S

にとって

x

が極大でない (

y_{i}\in X

が存在して

y_{i}\succ _{i}^{p}x

となる) ような勝利提携

S\in W

が存在しないことである。

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

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

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

注意

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

脚注

[脚注の使い方]

^ Suzuki, Mitsuo (1981). Game theory and social choice: Selected papers of Kenjiro Nakamura. Keiso Shuppan (鈴木光男編, ゲーム理論と社会選択: 中村健二郎遺稿集) 中村は 1975年に東京工業大学から社会工学専攻で初の博士号を授与されている。
^ ^a ^b ^c ^d Nakamura, K. (1979). “The vetoers in a simple game with ordinal preferences”. International Journal of Game Theory 8 (1): 55–61. doi:10.1007/BF01763051. ISSN 0020-7276.
^ シンプルゲームのコアとは、ある勝利提携に属する個人すべてが選択肢 $x$ より好むような選択肢 $y$ が存在しないような選択肢 $x$ の集合（すなわち社会選好の極大要素の集合）のことである。
^ 岡田章 (1997). ゲーム理論. 有斐閣. ISBN 978-4641067943
^ 日本語でコンパクトにまとまった中村の定理の解説としては、岡田 (1997, 9.5節, 10.4節)^[4] を挙げることができる。
^ ^a ^b ^c ^d Austen-Smith, David; Banks, Jeffrey S. (1999). Positive political theory I: Collective preference. Ann Arbor: University of Michigan Press. ISBN 978-0-472-08721-1
^ もとの中村の定理は直接的には「シンプルな」選好集計ルールにかんするものである。ここで「シンプルな」ルールとは、そのルールにおける「決定的な」提携の族によって完全に規定されるルールであり、ある提携 $S$ が「決定的である」とは、 $S$ に属するすべての個人が $x$ を $y$ より好むときはかならず、社会選好でも $x$ を $y$ より好むことになることをいう。中村ナンバーの役割を重視した社会選択理論のテキストである Austen-Smith and Banks (1999)^[6] は、中村ナンバーをよりひろい (経験上重要な) クラスの選好集計ルールに拡張し (Theorem 3.3)、中村と同様の結果 (Theorem 3.4) を得ている。そのクラスとは、中立性 (選択肢のラベルは重要ではないこと) と単調性 (もし $x$ が社会的に $y$ より好まれるなら、 $x$ への $y$ と比較しての各人の支持を増やしても、この社会選好がたもたれること) を持つ集計ルールからなるものである。
^ 次の集合の最小要素は存在する。なぜなら任意の非空の順序数の集合は最小要素を持つためである。
^ Kumabe, Masahiro; Mihara, H. Reiju (2008). “The Nakamura numbers for computable simple games”. Social Choice and Welfare 31 (4): 621–640. doi:10.1007/s00355-008-0300-5. ISSN 0176-1714.
^ シンプルゲームが「計算可能である」ことの定義は、ライスの定理に類する結果を参照。特に、任意の有限ゲームは計算可能である。
^ 各エントリーには、計算可能なシンプルゲームの持ち得る中村ナンバーを記入している。ただし空集合は敗北提携であると仮定している。 16個あるタイプは以下の基準によって定義されている: 単調かどうか、プロパーかどうか、強いかどうか、拒否権プレーヤーなしかどうか。たとえばタイプ 1110 に対応する行は、単調 (1) でプロパー (1) で強く (1) て拒否権プレーヤーのある (0) 計算可能シンプルゲームのなかで、有限であるものは $+\infty$ に等しい中村ナンバーを持ち、無限であるものは存在しないことを表している。タイプ 1101 に対応する行は、任意の整数 $k\geq 3$ が、このタイプに属するある有限の (また、ある無限の) シンプルゲームの中村ナンバーになる (かつそれ以外の整数 $k<3$ はそういう中村ナンバーになり得ない) ことを表している。拒否権プレーヤーなしのシンプルゲームのなかでは、タイプ 1101 と 0101 のみが3より大きい中村ナンバーを持つことが分かる。
^ " $\Longleftarrow$ " 方向はあきらか。 " $\Longrightarrow$ " 方向は上記定理よりは強いステートメントになっている (証明は本質的に同じ)。これらの結果は「以上に好む」を表す弱選好で述べられることも多い (e.g, Austen-Smith and Banks, 1999, Theorem 3.2^[6])。ここで弱選好 $\succeq$ は以下で定義できる: $x\succeq y\iff y\not \succ x$ . このとき $\succ$ が非対称的であることと $\succeq$ が完備である (complete) こととは同値である。また、 $\succ$ が否定推移的であることと $\succeq$ が推移的であることとは同値である。 $\succ$ が total とは、 $x\neq y$ のとき、 $x\succ y$ あるいは $y\succ x$ となることである。
^ ^a ^b ^c Kumabe, Masahiro; Mihara, H. Reiju (2011). “Preference aggregation theory without acyclicity: The core without majority dissatisfaction”. Games and Economic Behavior 72 (1): 187–201. doi:10.1016/j.geb.2010.06.008. ISSN 08998256.
^ ここで「アジェンダ」とは、選択肢全体を表すなんらかの集合の部分集合のことで、 (いま意思決定が行われれば実際に採用できるような) 実現可能な選択肢からなる集合とみなすことができる。 (ミクロ経済学の消費者理論で言えば、選択肢全体の集合は任意の消費バンドルのあつまりに、アジェンダは予算集合に対応。)
^ 拡張されたフレームワークでは、「提携」から成るブール代数 ${\mathcal {B}}$ と、それより大きな族である「個人の集合で、勝利あるいは敗北のステータスを与えることのできるもの」たちの族 ${\mathcal {B}}'$ とを区別する。たとえば ${\mathcal {B}}$ を帰納的集合 (recursive sets) から成るブール代数、 ${\mathcal {B}}'$ を帰納的可算集合の束とするのは自然である (Kumabe and Mihara, 2011, Section 4.2)。

概要