中村ナンバー
協力ゲーム理論および社会選択理論において、中村ナンバー (なかむらナンバー、Nakamura 数、) とは、投票ルールに代表される集合的意思決定ルールの合理性の度合いをはかる指標となる整数のことである。この名称は、以下の事実を証明した日本人ゲーム理論家中村健二郎 (1947-1979) による。
つまり、選択の合理性は選択肢数とこの数の大小関係により左右され、大きい中村ナンバーを持つルールほど多くの選択肢を矛盾なく扱える。
中村ナンバーの正確な定義を与える前に、中村ナンバーを付与することのできる意思決定ルールの例を挙げる。
個人1, 2, 3, 4, 5 からなる「多数決ルール」では、多数派となる個人の集合全てを含む集合
が考えられる。このような集合（シンプルゲーム）が中村ナンバーを与えることのできる対象である。勝利提携（シンプルゲームの元である集合のこと）に属する個人が共有する選好が、社会（この例では5人からなる社会）全体の選好（社会選好）となる。
シンプルゲームの「中村ナンバー」とは、勝利提携からなる集合で、その集合に含まれる全ての勝利提携の共通部分が空集合となるようなもののうち、最も元の個数が少ない集合の元の個数のことである。よって、この例における中村ナンバーは3である。このことは、任意の2つの勝利提携の共通部分は少なくとも1人の同じ個人を含むが、formula_3, formula_4, formula_5という3つの勝利提携の共通部分は空になることから確認できる。
中村の定理 (Nakamura, 1979) は、シンプルゲームが全ての選好順序に対して非空のコアを持つための必要条件（選択肢集合が有限の場合は十分条件でもある）として、選択肢の数がそのシンプルゲームの中村ナンバーよりも小さいことを挙げている。上記のシンプルゲームの例でいえば、この定理から選択肢が3個以上ある場合選好順序の選び方によってはコアに属する選択肢がなくなるということがわかる。
選択肢を「順序づける」ことに関しては、社会選択理論における「アローの不可能性定理」その困難さを指摘しているが、選択肢を「選ぶ」ことに関しては、中村の定理がより直接的な関連性を持っている。
formula_6 を (有限または無限の) 非空な「個人」の集合とする。
集合 formula_6 の部分集合を「提携」とよぶ。
シンプルゲーム (投票ゲーム) とは、提携のあつまり formula_8 のことである。
ここでは formula_8 は非空で空集合をふくまないと仮定する。
formula_8 に属する提携は「勝利」提携、属さない提携は「敗北」提携という。
シンプルゲーム formula_8 が「単調である」とは、任意の formula_12 と formula_13
について、formula_14 がなりたつことをいう。
formula_8 が「プロパーである」とは、任意の formula_12 について、formula_17 となることをいう。
formula_8 が「強い」とは、任意の formula_19 について、formula_20 となることをいう。
「拒否権プレーヤー」とは、すべての勝利提携に属する個人のことである。
シンプルゲームが「弱い」とは、それが拒否権プレーヤーをもつことを意味する。
formula_8 が「有限である」とは、ある有限集合 (キャリアとよばれる) formula_22 が存在して、
任意の提携 formula_23 について、formula_12 と formula_25 が同値になることをいう。
formula_26 を (有限または無限の)「選択肢」の集合とし、その濃度 (要素数) 
formula_27 は最小でも2とする。
ここで (強い; 狭義の) 選好とは、formula_26 上の「非対称的な」関係 formula_29 を指す:
すなわち formula_30 (「formula_31 は formula_32 より好まれる」の意) ならば、
formula_33 となる。
選好 formula_29 が「非循環的である」(「サイクル」をふくまない) とは、任意の有限個の選択肢
formula_35 について、もし
formula_36, formula_37,…, formula_38 ならば、
formula_39 となることをいう。非循環的な関係は非対称的であるため、選好に該当することに注意。
(選好) プロファイルとは、個人の選好 formula_40 の列 (リスト) formula_41 のことである。
ここで、formula_42 は個人 formula_43 がプロファイル formula_44 において、選択肢 formula_31 を選択肢 formula_32 より好むことを表している。
「譲渡可能な効用を前提としない投票ゲーム」(選好つきシンプルゲーム) とは、シンプルゲーム formula_8 とプロファイル formula_44 のペア formula_49 のことである。
いま formula_49 が与えられたとき、 formula_26 上の「支配関係」(社会選好) formula_52 を次のように定義する:
formula_53 とは、ある勝利提携 formula_12 が存在して、すべての formula_55 にたいして formula_42 となること。
formula_49 のコア formula_58 とは、formula_52 によって支配されない選択肢の集合
(formula_52 にかんして formula_26 上で極大要素となる選択肢の集合) である:
シンプルゲーム formula_8 の中村ナンバー (Nakamura 数) formula_66 とは、インターセクションが空集合となるような勝利提携のあつまりのうちもっとも小さなものの濃度 (提携数) のことである: formula_67 (拒否権プレーヤーが存在しない) となるとき、
それ以外のケースでは formula_69 (任意の濃度より大きい) とする。
formula_8 が拒否権プレーヤーなしのシンプルゲームであれば、formula_71 となることは簡単にしめせる。
有限人のばあいの例 (formula_72) (Austen-Smith and Banks (1999), Lemma 3.2 を参照).
以下で formula_8 は単調でプロパーとする.
たかだか可算個の個人がいるばあいの例 (formula_88).
シンプルゲームにかかわる代表的な性質 (単調かどうか、プロパーかどうか、強いかどうか、拒否権プレーヤーなしかどうか、有限かどうか) 
がその中村ナンバーにあたえる制限については、Kumabe and Mihara (2008) が徹底的に調べ上げている
(その結果は以下の表「可能な中村ナンバー」に要約されている)。
特に、アルゴリズムによって「計算可能」で
かつ拒否権プレーヤーをもたないシンプルゲームが3より大きい中村ナンバーをもつとき、
そのシンプルゲームはプロパーかつ強くないことが分かっている。
中村の定理 (Nakamura, 1979, Theorems 2.3 and 2.5).
formula_8 をシンプルゲームとする。非循環的な選好からなる任意のプロファイル formula_44 にたいしてコア formula_58 が非空となることは、formula_26 が有限かつ formula_93 となることと同値である。
リマーク
このセクションでは「非循環的な選好」という通常の仮定を捨てることにする。
そのかわり与えられた「アジェンダ」(agenda, 個人のグループが当面直面している「機会集合」) 上で極大要素を持つような選好をここでは考える。
ノーテーションを節約するため、ここでは集合 formula_26 自体をアジェンダとみなすことにする。
選択肢 formula_112 が選好 formula_40 にかんして「極大 (要素) である」
(あるいは formula_40 が「極大要素 formula_31 を持つ」) とは、
formula_116 となるような formula_117が存在しないことである。
もし選好が選択肢全体の集合上で非循環的であれば、その選好は任意の「有限」部分集合 formula_26 上で極大値を持つ。
中村の定理の変種 (variant) を述べる前に、「コア」を強めた解概念を導入しておく。
たとえある提携が存在してそれに属するすべての個人 formula_43 が選択肢 formula_31 に「不満を持っている」
(各 formula_43 がなんらかのべつの選択肢 formula_122 を formula_31 より好むの意) としても、
選択肢 formula_31 がコア formula_58 には属してしまうことがある。
次の解概念はそのような選択肢 formula_31 を除外するものである:
以下の結果は容易にしめせる: formula_128 は各人の選好の極大要素集合だけに依存し、それらの集合のユニオンにふくまれる。
また、任意の選好プロファイル formula_44 について、formula_136 となる。
中村定理の変種 (Kumabe and Mihara, 2011, Theorem 2).
formula_8 をシンプルゲームとする。以下の3つのステートメントは同値である:
リマーク