中村ナンバー

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

中村ナンバー未満の選択肢から選ぶ状況では、そのルールは必ず最適な選択肢を選び出せる。
中村ナンバー以上の選択肢から選ぶ状況では、人々の選好の組合せにより当該ルールでは最適なものが定まらない場合がある。そのような状況は、投票のパラドックスに見られるように、選択肢 a が b より、b が c より、c が a より集団的に好まれるといったサイクルが存在する場合に発生する。つまり、選択の合理性は選択肢数とこの数の大小関係により左右され、大きい中村ナンバーを持つルールほど多くの選択肢を矛盾なく扱える。

1. 概要
-----

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

が考えられる。このような集合が中村ナンバーを与えることのできる対象である。勝利提携に属する個人が共有する選好が、社会全体の選好となる。

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

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

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

2. 定義の準備
--------

2.1. シンプルゲーム
------------

を個人からなる空でない集合とする。 の部分集合を提携という。提携の集合 をシンプルゲーム  という。ここでは は空集合でなく、かつ空集合を含まないと仮定する。 に属する提携は勝利提携、属さない提携は敗北提携という。シンプルゲーム が単調であるとは、任意の と について、 が成り立つことをいう。 がプロパーであるとは、任意の に対して となることをいう。 が強いとは、任意の に対して となることをいう。拒否権プレーヤーとは、すべての勝利提携に属する個人のことである。シンプルゲームが弱いとは、そのシンプルゲームが拒否権プレーヤーを含むことをいう。 が有限であるとは、ある有限集合 が存在して、任意の提携 について と が同値になることをいう。

を「選択肢」の集合とし、その濃度 は最小でも2とする。ここで選好とは、 上の非対称的な関係、すなわち  ならば、 となる関係 を指す。選好 が非循環的である、あるいはサイクルを含まないとは、任意の有限個の選択肢 について、もし , ,…, ならば となることをいう。非循環的な関係は非対称的であるため、選好に該当することに注意しなければならない。

 プロファイルとは、個人の選好 の列  のことである。ここで、 は個人 がプロファイル において、選択肢 を選択肢 より好むことを表している。

2.2. 選好付きシンプルゲーム
----------------

シンプルゲーム とプロファイル のペア を選好付きシンプルゲームという。 が与えられたとき、任意の に対して、ある勝利提携 が存在して、すべての に対して となることを と表す。この を 上の支配関係という。

選好付きシンプルゲーム に対し、によって支配されない選択肢全てからなる集合を のコアといい と表す。この定義は、

となる が存在しないと言い換えることができる。

3. 定義
-----

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

 となるとき、
それ以外のとき であるとする。が拒否権プレーヤーなしのシンプルゲームであれば、 が成り立つ。

4. 例
----

4.1. 人数が有限の場合の例
---------------

以下では 、 は単調でプロパーとする.

が拒否権プレーヤーなしの強いシンプルゲームなら、 である。
が過半数ゲームなら、 のケースでは となり、 のケースでは となる。
が -ルールで、 のとき、 となる。ただし は 以上の最小の整数。

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

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



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

中村の定理 . をシンプルゲームとする。非循環的な選好からなる任意のプロファイル にたいしてコア が非空となることは、 が有限かつ となることと同値である。

リマーク

中村の定理は、以下に近い形で  参照されることも多い : 非循環的な選好からなる任意のプロファイル にたいして支配関係 が非循環的になることは、任意の有限な にたいして となることと同値である 。
定理中で「非循環的な選好からなる任意のプロファイル にたいして」を「否定推移的な  選好からなる任意のプロファイル にたいして」あるいは「線形順序である  選好からなる任意のプロファイル にたいして」と言い換えても、得られたステートメントは正しい。
上記定理は -シンプルゲームに拡張できる。 ここで は、 の部分集合からなる任意のブール代数であり、それに属する要素を「提携」とみなす。 の例としては、ルベーグ可測集合の-代数などがある。「-シンプルゲーム」とは、 の部分族である。選好プロファイルは以下の意味で可測なものに限定するのが適切である: プロファイル が「可測である」とは、任意の について、 となることである。

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

このセクションでは「非循環的な選好」という通常の仮定を捨てることにする。 そのかわり与えられた「アジェンダ」 上で極大要素を持つような選好をここでは考える。 単純な考察にするため、ここでは集合 自体をアジェンダとみなすことにする。 選択肢 が選好 に関して「極大  である」  とは、 となるような が存在しないことである。 もし選好が選択肢全体の集合上で非循環的であれば、その選好は任意の「有限」部分集合 上で極大値を持つ。

中村の定理の変種  を述べる前に、「コア」を強めた解概念を導入しておく。 たとえある提携が存在してそれに属するすべての個人 が選択肢 に「不満を持っている」  としても、 選択肢 がコア には属してしまうことがある。 次の解概念はそのような選択肢 を除外するものである:

選択肢 が「多数不満なきコア」 に属するとは、任意の にとって が極大でない  ような勝利提携 が存在しないことである。以下の結果は容易に示すことができる: は各人の選好の極大要素集合だけに依存し、それらの集合のユニオンにふくまれる。 また、任意の選好プロファイル について、 となる。

中村定理の変種 . をシンプルゲームとする。以下の3つのステートメントは同値である:

;
極大要素を持つ選好からなる任意のプロファイル に対して多数不満なきコア が非空となる;
極大要素を持つ選好からなる任意のプロファイル に対してコア が非空となる。注意

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

7. 脚注
-----

8. 関連項目
-------

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