中村の定理の謎

前回の記事「コアにかんする中村の定理」から続く．

徳島駅から関西空港駅までの経路をJR おでかけネットで今調べると，
所要時間 4時間04分，金額 12,660円，乗車距離 387.4 km，乗り換え 3回
という経路が出て来る．一方 Yahoo! 路線情報を調べると，
所要時間 3時間11分，金額 4,000円，乗車距離 181.0 km，乗り換え 0 回
という経路が出て来る．大部分のひとは Yahoo! のほうが出した経路の方を選ぶだろう．JR おでかけネットのパフォーマンスが悪いのは，Yahoo! とちがってバス路線の情報を出さないからだ．(設定によっては出してくれるかもしれない．ここに載せたのは，あくまでボク個人が一度だけトライしたときの結果だ．) JR おでかけネットは，ひじょうに遠回りになる高松・岡山経由の鉄道路線を出すのだ．(Yahoo! のほうもベストではないかもしれない．海上交通もあるだろうから．)

すぐ手に入る道具を使わない．手許にある道具に備わっている機能を利用しない．そのことによって簡単にできるはずの仕事をひじょうにめんどうなやり方でやっているひとは少なくないだろう．複数ファイルの一括検索ができることを忘れて，何十というファイルをひとつひとつ検索したことがあるひともいるかもしれない．ボクの知り合いのある東大生は，テキストエディタ (ワードプロセッサだったかも) のワードラップ機能を知らず，とても長い行のある文書を読むために画面を何度も右左にスクロールしていたことがあった．複雑なことは理解できるのに教え方が下手な教員がときどきいるのは，彼らが遠回りな論理で物事を理解できるため，簡単な論理を追求する努力をしないためかもしれない．そういうのは頭がいいというべきか悪いというべきか分からないが，ある種の美意識が欠けているとは言えるだろう．

じつは「中村の定理」のオリジナル論文 (Nakamura, 1979) にも，この類いの遠回りが見られるという．中村の定理がどう記述されているか，細かい点は省略して代表的な形を 3 つ挙げてみよう．(定理の意味は分からなくても，3 つの形の構造に注目してくれれば，この記事のポイントは把握できるはず．) 以下で X は選択肢集合であり，「X の要素数が中村ナンバー未満」は「#X <ν(ω)」と前の記事では書いた条件．いうまでもなく，→ は only if のことであり，←→ は if and only if のこと．後述する Figures も参照．

  1. Kumabe and Mihara (2006, Theorem 16). 任意の選好プロファイルにたいしてコアが非空である ←→ X が有限である & X の要素数が中村ナンバー未満である．
  2. Nakamura (1979, Theorem 2.3). 任意の選好プロファイルにたいしてコアが非空である → X の要素数が中村ナンバー未満である．
  3. Nakamura (1979, Theorem 2.5). X が有限であるとすると，以下がなりたつ:
    • 任意の選好プロファイルにたいしてコアが非空である ←→ X の要素数が中村ナンバー未満である．

たとえば岡田 (1996; 定理 10.17) は 3 番目の形式になっている．なお，「代表的」とはいったが，最初の形はほかの文献では見たことがない．

リマーク．Nakamura (1979) では，不等式条件「X の要素数が中村ナンバー未満」のところはじっさいは「ω が weak であるか X の要素数が中村ナンバー未満」となっている．シンプルゲームが weak というのはすべての勝利提携のインターセクションが非空であることだから，われわれの中村ナンバーの定義により不等式条件はみたされる．よって「ω が weak である」という条件は省略した．

中村の定理を紹介したたいていのテキストやサーベイでは，個人の数も選択肢の数も有限であることを仮定している．そのため，これら 3 つのちがい---したがって前述した遠回り---が表面化することはない．

上の 2番目と3番目の形はどちらがより一般的ということはない．一般性からは比較不能である．一方，1番目の形は2番目と3番目を特殊な場合としてふくんでいる．つまり，1 は 2 と 3 のいずれよりも一般的なのだ．さらにいえば，より一般的である 1 は 2 と 3 からすぐしめせる．

詳細．「任意の選好プロファイルにたいしてコアが非空である → X が有限である」をしめすのは簡単なので (無限上昇する選好を考えればいい; 詳しくは Kumabe and Mihara (2006) 参照)，2 がしめせれば 1 の →方向はすぐしめせる．一方，3 がしめせれば 1 の ←方向は自動的に導かれる．

なお，Kumabe and Mihara (2006) の主要な貢献は中村の定理の一般化ではないことは指摘しておく．それはシンプルゲームの「計算可能性」がメインのペーパーであり，中村の定理にかんするセクションはあくまでもおまけ的な位置づけだ．しかも，そのセクションで彼らが意図したとおもわれる貢献は 2 と 3 を 1 に一般化したことにあるわけではない．「社会選択における極大要素」で述べたように，「提携とは個人集合の任意の部分集集合である」という仮定を「提携はブール代数を形成する」というより一般的な仮定に置き換えたことにある．

ここで上記の定理形 1, 2, 3 に対応する Figures を挿入しておく．ただし 3 は (3a) と (3b) という主張に分けてある．


Figures: Variants of Nakamura's theorem. The following assertions about Fin (finite N), Nak (the Nakamura-number cap), C (nonempty core) are indicated:

  • (1) C ←→ (Fin & Nak)
  • (2) C→Nak
  • (3a, 3b) Fin→(C←→Nak)

Observe the following:

  • (2) extends (3b); its proof by Nakamura (without using "C→Fin") is hard;
  • (1) extends (2) and (3a) (as well as (3b)); the only missing implication "C→Fin" is easy to prove;
  • The proof of (3b) is easier than that of (2) by Nakamura; it actually proves (2) by way of "C→Fin";
  • The proof of (3b) is easily extendable to a more general framework.

わざわざ一般性の低い 2, 3 の形でふたつの定理を提示するよりは，より一般性の高い 1 の形でひとつの定理を提示する方がエレガントであるはずだ．ところが不思議なことに，Nakamura (1979) は 2, 3 の形で提示する方を選んでいる．もちろん，「2, 3 から 1 を導出するのは簡単なので，中村自身はやる必要を感じなかっただけだろう」と憶測することは可能だ．だが，その憶測が正しいとは思えない．2 の証明があまりにも高度なためである．「任意の選好プロファイルにたいしてコアが非空である → X が有限である」という，すぐに使える「道具」があるのに利用していないため，簡単にできるはずの証明が (めんどうとはいわないまでも) 不必要に高度になっているのだ．1 の形を思いつくことができたならば，その「道具」はたちまち利用できたはずだから，そのような証明が遠回りであることにはすぐ気づいたはずだ．

詳細．2 をしめすには，その対偶である「X の要素数が中村ナンバー以上 (すなわち中村ナンバーが X の要素数以下) → ある選好プロファイルにたいしてコアが空である」をしめせばよい．このとき「中村ナンバーが X の要素数以下」という前提部分については，(「任意の選好プロファイルにたいしてコアが非空である → X が有限である」という簡単にしめせる含意を使えば) 一般性を失わずに X の要素数も中村ナンバーも有限であることを仮定できる．ところが Nakamura はこの有限の仮定をもちいずに証明しているため，無限のユニオンやインターセクションを考えるなど，証明がかなりむずかしくなっている．

ちなにみに前述の「詳細」で述べた「提携はブール代数を形成する」という仮定への一般化をしようとすると，Nakamura の証明では問題が出て来る．Nakamura のばあいとちがって，その仮定のもとでは無限個の提携のユニオンやインターセクションが提携になるとは限らないからだ．有限個のユニオンあるいはインターセクションだけを考えれば済むことを利用できればその問題は回避できる．そしてもちろん「任意の選好プロファイルにたいしてコアが非空である → X が有限である」という含意を使えば，有限個のユニオンあるいはインターセクションだけを考えればよいことがしめせる．

以前の記事「ソロモン王のジレンマはセカンドプライス・オークションで解決できるじゃないか！」で紹介した Mihara (2006) のメカニズムは，本人によれば「言われてみればたしかに自明だが，思いつくのはかならずしも自明ではない」例かもしれないとのことだった．「中村の定理」を上の 2, 3 の形の代わりに 1 の形で提示するという単純なアイディアも，この種の思いつきにくい例のひとつなのかもしれない．

もしかするとなにか深いわけ，隠された意図があったのかもしれないが，いまのボクには謎である．だれか分かるひとがいたらコメントして欲しい．

ボク自身は，筑波の Professor Goldchild から授かった中村健二郎遺稿集に収められたオリジナル論文を見たとき，その一般性の高さに感心した記憶がある．(個人の集合も選択肢の集合も無限になることを許している．選好は非循環性だけ仮定している．シンプルゲームに単調性などの条件をつけていない．) そのエレガントな定理の証明が，このように不必要な遠回り (あるいは高度な証明による過剰なエレガントさの追求) によって成り立っていたことは意外だった．

参考文献

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.

H. Reiju Mihara. The second-price auction solves King Solomon's dilemma. Available at SSRN, August 2006.

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月5日，「退屈な穴埋め作業ぼちぼち進行中」に追記を加えた．

「大学入試過去問活用宣言」(実態は「大学入試過去活用制限」?) を受けて，11月9日，「他県とほぼ同じ問題ばかりを入試に出題してしまった清水東高校」に追記を加えた．

追記 (11/10/06).

図とキャプションを追加し，それにともない若干説明を修正した．(フレームワークを限定したり前提を特殊化することにより) 利用できる条件を増やすことで，もともと高い一般性を持つ定理の証明を簡単化することはよく行われる．テキストブックの前書きに「一般性を犠牲にしたうえで完全な証明を与えた」とよくあるのは周知のとおりだ．Kumabe and Mihara (2006) による中村定理のおもしろいのは，(Nakamura の利用しなかった) ある条件 (有限人数条件) をうまく利用することにより証明を簡素化する一方で，一般性も拡張したことだ．(単に定理形 2, 3 を定理形 1 に一般化しただけでなく，「提携」概念がより柔軟に定義できるフレームワークへ拡張している．) 「特殊化を偽装した一般化」とでもよぶべき意外性をそこに見ることができる．
【2006/11/09 20:02 】
| 社会科学 | コメント(2) | トラックバック(0) |
| ホーム |