中村ナンバー

協力ゲーム理論および社会選択理論において、中村ナンバー (なかむらナンバー、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 をシンプルゲーム (投票ゲーム) という（それぞれの提携に 1 または 0 の値を与える提携ゲームと考えることもできる）。ここでは 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_33 が非循環的である、あるいはサイクルを含まないとは、任意の有限個の選択肢 formula_35 について、もし formula_36, formula_37,…, formula_38 ならば formula_39 となることをいう。非循環的な関係は非対称的であるため、選好に該当することに注意しなければならない。
(選好) プロファイルとは、個人の選好 formula_40 の列 (リスト) formula_41 のことである。ここで、formula_42 は個人 formula_43 がプロファイル formula_44 において、選択肢 formula_30 を選択肢 formula_31 より好むことを表している。
選好付きシンプルゲーム.
シンプルゲーム formula_8 とプロファイル formula_44 のペア formula_49 を選好付きシンプルゲーム（譲渡可能な効用を前提としない投票ゲーム）という。 formula_49 が与えられたとき、任意の formula_51に対して、ある勝利提携 formula_12 が存在して、すべての formula_53 に対して formula_42 となることを formula_55 と表す。この formula_56を formula_26 上の支配関係（社会選好）という。
選好付きシンプルゲーム formula_49 に対し、formula_56によって支配されない選択肢全てからなる集合（つまり、formula_56 に関して formula_26 上で極大要素となる選択肢の全てからなる集合）を formula_49 のコアといい formula_63と表す。この定義は、formula_64formula_65となる formula_66 が存在しないformula_67と言い換えることができる。
定義.
シンプルゲーム formula_8 の中村ナンバー formula_69 とは、共通部分が空集合となるような勝利提携の集合のうち、最も小さな濃度（提携数）をもつ集合のその濃度のことである。なお、
であるとする。formula_8が拒否権プレーヤーなしのシンプルゲームであれば、formula_74 が成り立つ。
例.
人数が有限の場合の例.
（Austen-Smith and Banks (1999), Lemma 3.2 を参照）以下では formula_75（有限集合）、 formula_8 は単調でプロパーとする.
たかだか可算個の個人がいる場合の例.
シンプルゲームに関わる代表的な性質（単調かどうか、プロパーかどうか、強いかどうか、拒否権プレーヤーなしかどうか、有限かどうか）がその中村ナンバーにあたえる制限については、Kumabe and Mihara (2008) が調べ上げている（その結果は以下の表「可能な中村ナンバー」に要約されている）。特に、アルゴリズムによって「計算可能」でかつ拒否権プレーヤーをもたないシンプルゲームが3より大きい中村ナンバーをもつとき、そのシンプルゲームはプロパーかつ強くないことが分かっている。
非循環的な選好に対する中村の定理.
中村の定理 (Nakamura, 1979, Theorems 2.3 and 2.5).
formula_8 をシンプルゲームとする。非循環的な選好からなる任意のプロファイル formula_44 にたいしてコア formula_63 が非空となることは、formula_26 が有限かつ formula_95 となることと同値である。
リマーク
サイクルを含み得る選好に対する中村の定理の変種.
このセクションでは「非循環的な選好」という通常の仮定を捨てることにする。
そのかわり与えられた「アジェンダ」(agenda, 個人のグループが当面直面している「機会集合」) 上で極大要素を持つような選好をここでは考える。
単純な考察にするため、ここでは集合 formula_26 自体をアジェンダとみなすことにする。
選択肢 formula_114 が選好 formula_40 に関して「極大 (要素) である」
(あるいは formula_40 が「極大要素 formula_30 を持つ」) とは、
formula_118 となるような formula_119が存在しないことである。
もし選好が選択肢全体の集合上で非循環的であれば、その選好は任意の「有限」部分集合 formula_26 上で極大値を持つ。
中村の定理の変種 (variant) を述べる前に、「コア」を強めた解概念を導入しておく。
たとえある提携が存在してそれに属するすべての個人 formula_43 が選択肢 formula_30 に「不満を持っている」
(各 formula_43 がなんらかのべつの選択肢 formula_124 を formula_30 より好むの意) としても、
選択肢 formula_30 がコア formula_63 には属してしまうことがある。
次の解概念はそのような選択肢 formula_30 を除外するものである:
以下の結果は容易に示すことができる: formula_130 は各人の選好の極大要素集合だけに依存し、それらの集合のユニオンにふくまれる。
また、任意の選好プロファイル formula_44 について、formula_138 となる。
中村定理の変種 (Kumabe and Mihara, 2011, Theorem 2).
formula_8 をシンプルゲームとする。以下の3つのステートメントは同値である:
注意