コアにかんする中村の定理

キーワード: 中村健二郎，中村の定理，中村ナンバー，中村数，コア，シンプルゲーム，単純ゲーム，投票ゲーム，社会選択理論，実証政治理論，投票理論，選挙研究． Kenjiro Nakamura, Nakamura's theorem, Nakamura number, core, simple games, voting games, social choice theory, positive political theory, voting theory, election studies.

「中村の定理」(Nakamura, 1979) といえば，げんざい社会選択を学ぶひとの間ではかなり有名な結果だ (リマーク参照)．投票ルールが「合理的に」あつかえる選択肢の数は限定されることを主張したものである．たとえば過半数にもとづく多数決は，選択肢が2 個ならば過半数に支持される選択肢をいつも 1 つだけ選びだすことができるが，選択肢が 3 個以上になるとそうはいかない．ある過半数が選択肢 a を b より，べつの過半数が b を c より，さらにべつの過半数が c を a より支持するといった「サイクル」ができることがあるためだ．社会にとってのベストな選択肢を見つけるという重要問題に独特なアプローチで迫り，エレガントな定理に結実させたのが Nakamura (1979) だ．

リマーク．たとえば実証政治理論の大学院レベル本格的テキストである Austen-Smith and Banks (1999) のかなりの部分は「中村の定理」の発想を軸に展開していると言える．(いい本だが経済学徒向きではない．社会選択を勉強したい経済学徒ならとりあえず MWG の Chapter 21 を読めばじゅうぶんだろう．ただし中村の定理は MWG には載っていない．) 社会選択の文献では，中村の定理が貢献した分野であるシンプル・ゲーム (協力ゲームの一種) のコアに関する理論は以前あまり注目されていなかった．社会選択と協力ゲーム理論との交流は意外と限定されていたのかもしれない．たとえば協力ゲームのペーパーを多く載せていた International Journal of Game Theory が経済学文献データベース EconLit に収録されるようになったのは創刊後ずいぶん経ってからだ．ちまたのつまらない議論で「中村ナンバーだって、あの当時すごい業績ではあっても非常にマイナーですよ」と言い出すひとが現れても不思議ではない．

中村の定理を手っ取り早く知るには岡田 (1996) が手頃だ．証明は Kumabe and Mihara (2006) が分かりやすく，かつ一般性も高い．

なお，この記事は「選好」「極大要素の存在: 美人ホールを求めて」「社会選択における極大要素」からなるシリーズにつづくものだ．

「社会選択における極大要素」の記事で，「社会選好 P が非循環的であることが社会としての『ベスト』な選択肢の存在のための必要十分条件であることがわかる」「では，社会選好 P は非循環的になるのだろうか？　それはばあいによる．選好プロファイル次第だ」と説明した．選好プロファイル，つまりひとびとの選好によって極大要素が存在したりしなかったりということでは「安定性」の面から不満が残る．では，つねに極大要素が存在するような条件はあるのか？　それに答えたのが「中村の定理」である．

定義．個人の集合 N 上で定義されるシンプルゲーム ω を考える．(つまり ω は任意の提携のあつまり．ω に属する提携を《勝利提携》と呼び，そのような提携は「多数派」とみなされることになる．) ω の《中村ナンバー》ν(ω) とはインターセクションが空集合になるような勝利提携の最小個数である．つまり勝利提携を ν個うまくあつめればそれらの交わりを空集合にできるが，それ未満の数 (ν-1 個など) あつめても交わりが決して空集合にはならないような数νのことだ．もし勝利提携をすべてあつめても交わりが空集合にならないばあいは，選択肢集合 X の要素数 #X より大きい任意の数 (たとえば 2 の #X 乗，つまり 2#X とか) をもって中村ナンバーとする．

例．個人が 3 人いる，つまり N={1, 2, 3} とする．過半数とは 2 人以上であり，過半数の提携のあつまりは ω={{1, 2}, {1, 3}, {2, 3}, {1, 2, 3}} である．この４つの勝利提携から2個だけ取って来てもそれらのインターセクションは空にはならない．たとえば {1, 2} と {1, 3} のインターセクションは {1} であり空集合ではない．一方，最初の3つの勝利提携を取りだせばそれらのインターセクションは空集合になる．したがってこのシンプルゲーム ω の中村ナンバーは 3 である．

例．個人が n 人いるとする．サイズが n-1 以上の提携を勝利提携とする．つまり勝利提携は以下の n+1 個である: 全員からなる提携，個人 1 だけが除かれた提携，個人 2 だけが除かれた提携，……，個人 n だけが除かれた提携．全員からなる提携以外の任意の提携を2個取ってくればそれらのインターセクションからは2人の個人が除外される．3個取ってくればそれらのインターセクションからは3人の個人が除外される，……という具合であることから，すべての個人が除外されるためには全員からなる提携以外の n 個の提携を取って来る必要があることが分かる．したがってこのシンプルゲームの中村ナンバーは n である．

例．個人が n 人いるとする．勝利提携とは個人 1 と 2 を含む提携のことだとする．(個人 1, 2 は「拒否権プレーヤー」とも呼ばれる．) すると勝利提携をいくらあつめても必ず個人 1, 2 はふくまれるのでインターセクションが空集合になることはない．したがってこのシンプルゲームの中村ナンバーは 2#X とみなす．

いうまでもなく，中村ナンバーはシンプルゲーム ω だけで決まる数であり，選択肢の数や選好プロファイルとは無関係である．

選択肢集合 X 上の (非循環的) 選好プロファイル (Pi)i∈N とそれから導かれる支配関係あるいは社会選好 P (リマーク参照) を考える．社会選好 P についての X の極大要素の集合 {x∈X: yPx となるような選択肢 y∈X は存在しない} を《コア》と呼んだ．つまりコアとは，社会にとっての「ベスト」な選択肢の集合と考えられる．コアは，シンプルゲーム ω，選択肢集合 X，そして選好プロファイル，の 3 つに依存した概念である．(これら 3 つの部品をまとめて《投票ゲーム》あるいは《選好つきシンプルゲーム (simple game with preferences)》と呼ぶこともある．)

リマーク．ある勝利提携 S∈ω が存在して，すべての i∈S について xPiy となる (つまり x を y より好むひとびとの全員あるいは一部が「多数派」となっている) ときに xPy と書いた．この P を《支配関係》あるいは《社会選好》と呼んだ．(この P は選好プロファイル (Pi)i∈N だけでなく ω にも依存するので，より正確には Pω と書くべき．)

選好 P が非循環的というのは「X の任意のアジェンダ (非空有限部分集合) A が P についての極大要素を持つ」ことと同値だった (「極大要素の存在: 美人ホールを求めて」記事参照)．「中村の定理」の一表現によれば，P がつねに (選好プロファイルにかかわらず) 非循環的になることは「X の任意のアジェンダ A にたいして #A< ν(ω) となる」ことと同値だ．つまり「X の任意のアジェンダがつねに極大要素を持つ」ことと「X の任意のアジェンダA にたいして #A< ν(ω) になる」ことは同値になる．このままでは煩雑なので，以下では任意のアジェンダの代わりに X 自体の極大要素の存在を考えよう．

「中村の定理」は任意の選好プロファイルにたいしてコアが非空になるための必要十分条件を与えている．その条件とは選択肢の数 #X が中村ナンバー以上にならないことである．社会にとっての「ベスト」な選択肢がひとびとの選好にかかわらず決まるためには，選択肢の数が限定されていなければならないわけだ．冒頭で述べた過半数多数決はもちろん (中村ナンバーは 3 なので選択肢 2 個まではうまくあつかえる)，どんな投票ルールであってもだ．定理の表現の仕方にはさまざまなものが考えられるが，ここでは Kumabe and Mihara (2006) に近い形で提示しよう．

中村の定理．シンプルゲーム ω が勝利提携を少なくともひとつ持つとする．また，空集合は勝利提携ではないとする．このとき選好つきシンプルゲームのコアが任意の選好プロファイルについて (極大) 要素を持つための必要十分条件は以下のとおり:

  1. 選択肢集合 X が有限である;
  2. #X <ν(ω) となる．

たとえば中村ナンバーが 2#X となるケース---つまり拒否権プレーヤーが存在するケース---では条件 2 の不等式 #X <ν(ω) は X の要素数にかかわらず成立する．したがってコアが常に非空になることと，X が有限であることは同値になる．ある個人 i がすべての勝利提携に属するならば，社会選好は非循環的になる (もし社会選好がサイクルを持てば i の選好もサイクルを持つことになり矛盾) ことからあきらかだろう．

「中村の定理の謎」につづく．

参考文献

David Austen-Smith and Jeffrey S. Banks. Positive Political Theory I: Collective Preference. University of Michigan Press, Ann Arbor, 1999.

Masahiro Kumabe and H. Reiju Mihara. Computability of simple games: A characterization and application to the core. MPRA Paper 437, Munich University Library, July 2006.

Andreu Mas-Colell, Michael D. Whinston, and Jerry R. Green (MWG). Microeconomic Theory. Oxford University Press, New York, 1995.

K. Nakamura. The vetoers in a simple game with ordinal preferences. International Journal of Game Theory, Vol. 8, pp. 55-61, 1979.

岡田章. ゲーム理論. 有斐閣, 1996. 10.4 節 (323 ページ「次に，譲渡可能な効用を仮定しない投票ゲームについて述べよう」以降), 9.5 節．

追記 (11/13/06; 著者の覚え書き).

「ブログの記事に手を加えるだけでいいから，入門向けの解説記事を書いてくれ」という依頼がいずれ来ないとも限らない (あるいは政治学・選挙研究・数理社会学・数理科学などの学会誌に載せようか?) ．(いずれにせよそういう依頼に応じられるのは，ここにあげた Kumabe らのペーパーと今後出ると予想される続編の掲載先が決まったあとの話で，何年も先だろう．) そういう場合に備えて，細かな点についてメモを残しておく．

任意のアジェンダ A の代わりに選択肢集合 X 自体の極大要素の存在を考える (言いかえればコアを考える) ひとつの理由は，後者が X 上の社会選好の非循環性にかかわるためである．(前者は A 上の社会選好の非循環性にかかわる．X 上で選好サイクルが存在しても，A 上で存在するとはかぎらないことに注意．) 個人選好の X 上での非循環性を仮定した現フレームワークでは，前者を考えたほうがストレートというわけだ．

無限の選択肢集合 X を許すひとつの理由は，個人が無限人いるばあい，中村ナンバーが無限になる可能性があるためだ．このとき X が無限でも中村の不等式 2 自体はみたされることがある．
【2006/11/05 12:02 】
| 社会科学 | コメント(1) | トラックバック(0) |
| ホーム |