中村ナンバー

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

協力ゲーム理論および社会選択理論において、中村ナンバー (なかむらナンバー、Nakamura 数Nakamura number) とは、(投票ルールに代表される) 集合的意思決定ルールの合理性の度合いをはかる指標 (整数) である。

  • この数未満の選択肢 (候補、オプション) から選ぶ状況では、当該ルールはつねに問題なく「ベストな」ものを選び出せる (ただし「ベストな」ものがひとつだけとは限らない)。

その一方で、

  • この数以上の選択肢から選ぶ状況では、ひとびとの投票の仕方 (「選好」の組合せ) によっては、当該ルールでは「ベストな」ものが定まらない場合がある (投票のパラドックスに見られるように、選択肢 a が b より、b が c より、c が a より集団的に好まれるといったサイクルの生じる場合)。

すなわち選択の合理性は選択肢数とこの数の大小関係に左右され、大きい中村ナンバーを持つルールほど多くの選択肢を矛盾なくあつかえる。たとえば多数決の中村ナンバーは (投票者が4人のケースを除けば) 3であることから、2個までの選択肢なら (パラドックスなど起さずに) うまくあつかえることが分かる。「中村ナンバー」という名称は、上記事実を定理として証明した日本人ゲーム理論家中村健二郎 (1947-1979) にちなむものである。[1]

概要[編集]

中村ナンバーの正確な定義を与える前に、中村ナンバーを付与することのできる意思決定ルールの例を挙げる。 いま、1, 2, 3, 4, 5 からなる個人の集合を想定すると、たとえば「多数決ルール」の背後には、 過半数である3人以上をふくむ「提携」(個人の集合) のあつまり

\{\{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\} \}

が存在するはずである。意思決定ルールの背後にある、この種のあつまりが中村ナンバーを与えることのできる対象であり、こういう任意の提携のあつまりのことを 「シンプルゲーム」(単純ゲーム; 投票ゲーム) とよぶ。 そして、そういうあつまりに属する提携をそのシンプルゲームおける「勝利提携」とよび、それ以外の提携を「敗北提携」という。 勝利提携に属する個人 (上の例では最低3人) 全員が選択肢 x を選択肢 y より好ましいとするとき、 (上の例では5 人の) 社会全体としてもそれと同じ順序付け (「社会選好」) が実現する。

シンプルゲームの「中村ナンバー」とは、インターセクション (共通部分) が空集合となるような勝利提携のあつまりのうちもっとも提携数が少ないものの、その提携数のことである (この数だけ勝利提携を集めることでインターセクションを空集合にできることがあるが、これ未満の数を集めてもけっしてインターセクションを空にはできない)。 たとえば上の例におけるシンプルゲームの中村ナンバーは3である。なぜなら任意の2つの勝利提携のインターセクションは少なくともひとりの個人をふくみ、 その一方で次の3つの勝利提携のインターセクションは空になるためである: \{1,2,3\}, \{4,5,1\}, \{2,3,4\}.

中村の定理 (Nakamura, 1979[2]) は、 シンプルゲームがすべての選好プロファイル (各個人の選好の) にたいして非空の「コア」を持つ (つまり「ベストな」選択肢の集合が空集合にならない) ための必要条件として以下を挙げている (選択肢集合が有限のばあいは十分条件でもある): 選択肢の数がそのシンプルゲームの中村ナンバーよりも小さいこと。 ここで「与えられた選好プロファイルについてのシンプルゲームのコア」とは、 ある勝利提携に属する個人すべてが x より好むような選択肢 y が存在しないような 選択肢 x の集合 (すなわち社会選好の極大要素の集合) のことである。 上記の過半数シンプルゲームの例でいえば、選択肢が3個以上あるばあい、選好プロファイルの選び方によっては コアに属する選択肢がなくなる (「ベスト」といえるものが存在しない) ことをこの定理は意味する。[4]

中村の定理にはいくつかの変種があり、たとえば以下の各条件をみたすようなすべての選好プロファイルにたいしてコアが非空になるための条件を挙げている: (i) 「非循環性」をみたす選好; (ii) 「推移性」をみたす選好; (iii) 「線形順序」となる選好。 また、これらとは異なる変種として、合理性にかんする弱い要件である「非循環性」さえ取り除いた定理 (Kumabe and Mihara, 2011[5]) があり、 その定理は極大要素を持つような個人選好からなるすべてのプロファイルにたいしてコアが非空になるための条件を挙げている。

選択肢を「順序づけること」にかんしては、社会選択理論における「アローの不可能性定理」という有名な定理が存在し、 個人の集まりが3つ以上の選択肢に順序を与えることの困難さを指摘している。 与えられた選択肢集合からなんらかの選択肢を「選ぶこと」にかんしては、 (順序を持つとは限らない社会選好の極大要素の集合である「コア」に注目した) 中村の定理がより直接的な関連性を持っている。[7] この定理の主張を考えると、「中村ナンバーはどれだけ大きくなりうるか?」という疑問が興味深いものであることが分かる。 この疑問については、以下の結果を挙げることができる:[8] 「拒否権を持つプレーヤー (すべての勝利提携に属する個人) が存在しないような、(有限あるいは) 計算可能なシンプルゲームが 3より大きな中村ナンバーをもつためには、そのシンプルゲームが「強い」ものであってはならない。」 これは、ある敗北提携で、その補集合も敗北提携になっているようものが存在することを意味する。 このことは、3つ以上の選択肢を持つ集合でコアがつねに非空になるためには、 コアのなかに互いに比較できない複数の選択肢をふくまざるをえないことを意味する。[10]

フレームワーク[編集]

N を (有限または無限の) 非空な「個人」の集合とする。 集合 N の部分集合を「提携」とよぶ。 シンプルゲーム (投票ゲーム) とは、提携のあつまり W のことである。 (それぞれの提携に 1 または 0 の値を与える提携ゲームと考えることもできる。) ここでは W は非空で空集合をふくまないと仮定する。 W に属する提携は「勝利」提携、属さない提携は「敗北」提携という。 シンプルゲーム W が「単調である」とは、任意の S \in WS\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 WS\cap T \in W が同値になることをいう。

X を (有限または無限の)「選択肢」の集合とし、その濃度 (要素数) \# X は最小でも2とする。 ここで (強い; 狭義の) 選好とは、X 上の「非対称的な」関係 \succ を指す: すなわち x \succ y (「xy より好まれる」の意) ならば、 y\not \succ x となる。 選好 \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 上の「支配関係」(社会選好) \succ^p_W を次のように定義する: x \succ^p_W y とは、ある勝利提携 S \in W が存在して、すべての i \in S にたいして x \succ_i^p y となること。 (W, p)コア C(W,p) とは、\succ^p_W によって支配されない選択肢の集合 (\succ^p_W にかんして X 上で極大要素となる選択肢の集合) である:

x \in C(W,p) とは、y \succ^p_W x となる y\in X が存在しないこと。

中村ナンバー: 定義と例[編集]

シンプルゲーム W中村ナンバー (Nakamura 数) \nu(W) とは、インターセクションが空集合となるような勝利提携のあつまりのうちもっとも小さなものの濃度 (提携数) のことである: \cap W = \cap_{S \in W} S = \emptyset (拒否権プレーヤーが存在しない) となるとき、[11]

\nu(W)=\min\{\# W': W'\subseteq W;  \cap W'=\emptyset \};[2]

それ以外のケースでは \nu(W)= +\infty (任意の濃度より大きい) とする。

W が拒否権プレーヤーなしのシンプルゲームであれば、2\le \nu(W)\le \# N となることは簡単にしめせる。

有限人のばあいの例 (N=\{1, \ldots, n\}) (Austen-Smith and Banks (1999), Lemma 3.2[6] を参照). 以下で W は単調でプロパーとする.

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

たかだか可算個の個人がいるばあいの例 (N=\{1, 2, \ldots\}). シンプルゲームにかかわる代表的な性質 (単調かどうか、プロパーかどうか、強いかどうか、拒否権プレーヤーなしかどうか、有限かどうか) がその中村ナンバーにあたえる制限については、Kumabe and Mihara (2008)[8] が徹底的に調べ上げている (その結果は以下の表「可能な中村ナンバー」に要約されている)。 特に、アルゴリズムによって「計算可能」で[12] かつ拒否権プレーヤーをもたないシンプルゲームが3より大きい中村ナンバーをもつとき、 そのシンプルゲームはプロパーかつ強くないことが分かっている。

可能な中村ナンバー[13]
タイプ 有限ゲーム 無限ゲーム
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 にたいして」と言い換えても、得られたステートメントは正しい。[14]
  • 上記定理は \mathcal{B}-シンプルゲームに拡張できる。[5] ここで \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, 個人のグループが当面直面している「機会集合」) 上で極大要素を持つような選好をここでは考える。[15] (選好にかんするこの弱い制限は、行動経済学の観点からみても興味深いかもしれない。) ノーテーションを節約するため、ここでは集合 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_ix より好むの意) としても、 選択肢 x がコア C(W,p) には属してしまうことがある。 次の解概念はそのような選択肢 x を除外するものである:[5]

選択肢 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[5]). W をシンプルゲームとする。以下の3つのステートメントは同値である:

  1. \# X < \nu(W);
  2. 極大要素を持つ選好からなる任意のプロファイル p にたいして多数不満なきコア C^+(W,p) が非空となる;
  3. 極大要素を持つ選好からなる任意のプロファイル 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 が導ける)。[16]

関連項目[編集]

脚注[編集]

[ヘルプ]
  1. ^ Suzuki, Mitsuo (1981). Game theory and social choice: Selected papers of Kenjiro Nakamura. Keiso Shuppan.  (鈴木光男編, ゲーム理論と社会選択: 中村健二郎遺稿集) 中村は 1975年に東京工業大学から社会工学専攻で初の博士号を授与されている。
  2. ^ a b c d Nakamura, K. (1979). “The vetoers in a simple game with ordinal preferences”. International Journal of Game Theory 8: 55–50. doi:10.1007/BF01763051.  編集
  3. ^ 岡田 章 (1997). ゲーム理論. 有斐閣. ISBN 978-4641067943. 
  4. ^ 日本語でコンパクトにまとまった中村の定理の解説としては、岡田 (1997, 9.5節, 10.4節)[3] を挙げることができる。
  5. ^ a b c d Kumabe, M.; Mihara, H. R. (2011). “Preference aggregation theory without acyclicity: the core without majority dissatisfaction”. Games and Economic Behavior 72: 187–201. doi:10.1016/j.geb.2010.06.008. http://mpra.ub.uni-muenchen.de/23918/2/MPRA_paper_23918.pdf.  編集
  6. ^ 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. 
  7. ^ もとの中村の定理は直接的には「シンプルな」選好集計ルールにかんするものである。 ここで「シンプルな」ルールとは、そのルールにおける「決定的な」提携の族によって完全に規定されるルールであり、 ある提携 S が「決定的である」とは、S に属するすべての個人が xy より好むときはかならず、 社会選好でも xy より好むことになることをいう。 中村ナンバーの役割を重視した社会選択理論のテキストである Austen-Smith and Banks (1999)[6] は、中村ナンバーをよりひろい (経験上重要な) クラスの選好集計ルールに拡張し (Theorem 3.3)、中村と同様の結果 (Theorem 3.4) を得ている。 そのクラスとは、中立性 (選択肢のラベルは重要ではないこと) と単調性 (もし x が社会的に y より好まれるなら、 x への y と比較しての各人の支持を増やしても、この社会選好がたもたれること) を持つ集計ルールからなるものである。
  8. ^ a b Kumabe, M.; Mihara, H. R. (2008). “The Nakamura numbers for computable simple games”. Social Choice and Welfare 31: 621. doi:10.1007/s00355-008-0300-5.  編集
  9. ^ Kirman, A.; Sondermann, D. (1972). “Arrow's theorem, many agents, and invisible dictators”. Journal of Economic Theory 5: 267. doi:10.1016/0022-0531(72)90106-8.  編集
  10. ^ 単調、プロパー、強い、そして拒否権プレーヤーを持たないといったよい性質を持つシンプルゲームが無限の中村ナンバーを持つことはある。 たとえば単項フィルターでない超フィルターはその例であり、 無限人の個人からなる社会でアローの定理における条件をすべてみたすような集計ルール (社会厚生関数) を定義するために使われている。[9] しかし、アルゴリズムにしたがって計算できないという事実は、このような目的のために超フィルターをもちいることの重大な欠点となっている。
  11. ^ 以下の集合の最小要素は存在する。なぜなら任意の非空の順序数の集合は最小要素を持つためである。
  12. ^ シンプルゲームが「計算可能である」ことの定義は、ライスの定理に類する結果を参照。特に、任意の有限ゲームは計算可能である。
  13. ^ 各エントリーには、計算可能なシンプルゲームの持ち得る中村ナンバーを記入している。 ただし空集合は敗北提携であると仮定している。 16個あるタイプは以下の基準によって定義されている: 単調かどうか、プロパーかどうか、強いかどうか、拒否権プレーヤーなしかどうか。 たとえばタイプ 1110 に対応する行は、単調 (1) でプロパー (1) で強く (1) て拒否権プレーヤーのある (0) 計算可能シンプルゲームのなかで、 有限であるものは +\infty に等しい中村ナンバーを持ち、無限であるものは存在しないことを表している。 タイプ 1101 に対応する行は、任意の整数 k\ge 3 が、このタイプに属するある有限の (また、ある無限の) シンプルゲームの中村ナンバーになる (かつそれ以外の整数 k< 3 はそういう中村ナンバーになり得ない) ことを表している。 拒否権プレーヤーなしのシンプルゲームのなかでは、タイプ 1101 と 0101 のみが3より大きい中村ナンバーを持つことが分かる。
  14. ^ "\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 が推移的であることとは同値である。 \succtotal とは、x\ne y のとき、x\succ y あるいは y\succ x となることである。
  15. ^ ここで 「アジェンダ」とは、選択肢全体を表すなんらかの集合の部分集合のことで、 (いま意思決定が行われれば実際に採用できるような) 実現可能な選択肢からなる集合とみなすことができる。 (ミクロ経済学の消費者理論で言えば、選択肢全体の集合は任意の消費バンドルのあつまりに、アジェンダは予算集合に対応。)
  16. ^ 拡張されたフレームワークでは、「提携」から成るブール代数 \mathcal{B} と、 それより大きな族である 「個人の集合で、勝利あるいは敗北のステータスを与えることのできるもの」たちの族 \mathcal{B}' とを区別する。たとえば\mathcal{B}帰納的集合 (recursive sets) から成るブール代数、\mathcal{B}'帰納的可算集合とするのは自然である (Kumabe and Mihara, 2011, Section 4.2)。