David Gale (1921-2008)

デビッド･ゲールが亡くなっていたとは知らなかった。去年の夏ストーニー・ブルックに招待された時に、彼の85歳記念のカンファレンスと誕生日記念ディナーがあって、そこで初めて見かけたんだが、その時はまだまだ元気そうだったのに。

そのカンファレンスの見所は、ゲールの業績をゲール自身が振り返ってサーベイする講演で、これはなかなか面白かった。彼は自分の業績の中で重要なものを3つ選んであげていたが、それはこんな感じ。

まず一つ目は、

１．無限ゲーム　（Gale and Stewart, "Infinite Games with Perfect Information," Contribution to the theory of games II, 1953)

これは(例えば）次のようなゲーム。個人１が０から９までの数を一つ選ぶ。これを $a_1$ とする。それを見た後個人２が０から９までの数を選んで　、これを $a_2$ とする。でそのあと、個人１が $a_3$ を選んで、個人２が $a_4$ と無限に続いていく。そして

$0.a_1a_2a_3a_4,........\in [0,1]$

という数を作って、これがある集合 $A \subset [0,1]$ に入ったら個人１の勝ちで、 $A$ に入らなければ個人２の勝ち。だからこのゲームでは引き分けはなくて、必ず勝ち負けが決まる。このゲームでゲール達が証明したのは、Aが開集合ならば個人１に必勝法があるということと、ある（選択公理を使って構成された）集合Aを使った場合には、どちらの個人にも必勝法が存在しないっていうこと（だったと思う。間違ってるかも）。

この論文はゲーム理論というよりは純粋数学の中でインパクトがあって、幾つかこれに追随する優れた研究が生まれた。一つの問題は、Aがどのような場合に必勝法が存在するかということで、これはMartinという人がAがボレル集合の場合には必勝法が存在する（Borel Determinacy）ことを証明したらしい。もう一つは、Aがなんであっても必勝法が存在するというのは、上で示したように（ZF公理系の元で）選択公理と矛盾するけど、そこで「Aがなんであっても必勝法が存在する」という性質（Axiom of Determinacy）を選択公理の代わりにZF公理系に足した公理系を考えちゃおう、とかいう人達が集合論の方で出て来たとのこと。もうここまでくると、詳しい話は分からないけど。

その次の話題は、

２．マッチング　（Gale and Shapley, "College Admissions and the Stability of Marriage," American Mathematical Monthly, 1962）

これはもちろんゲーム理論業界では最も有名な論文だけど、これに関しては、ゲールはほとんど説明せずにスルーしてしまった。まあカンファレンスの論文がマッチング盛りだくさんだったし、そもそもサーベイするまでもなく結果は同業者に良く知られているから、説明するまでもないということだったんだろう。

で、じつはゲールが講演のほとんどの時間を費やしたのが、最後のトピック。

３．Bridg-it、Chomp、Hexなど、ゲールやナッシュが発明したボードゲーム

Bridg-itとHexはとても似ていて、違う色の駒を二人で交互に置いていって、ボードのはじとはじをつなげたほうが勝ちという単純なゲームだ。ぐちゃぐちゃ説明するよりも、次のような絵を見たほうが手っ取り早いだろう。

これはWikipediaで見つけたHexの図。この図は赤が勝った場合。

Bridg-itはこんな感じ。

彼は、この二つのゲームは似ているけど数学的に見ると重要な部分が違っているんだとか何とかいう話をしていたような気がするんだけど、そこら辺の話はもう忘れてしまった。あ、そういえば、Hexは不動点定理に関連してるらしい。上の絵を見ると、このゲームでは引き分け（どちらもはじとはじをつなげられない）がないのが「明らか」だけど、この事実は２次元のブラウアー不動点定理と同値になっているのだ。（Gale, "The Game of Hex and Brouwer Fixed-Point Theorem," American Mathematical Monthly, 1979）。

Chompはこれとはちょっと違ったゲームだけど、ルールはやっぱり簡単。まず碁石（何でもいいけど）を縦横に数列に並べて長方形を作る。まず個人１が一つ碁石を選び、そしてその碁石の下か右に位置する碁石（右下の碁石すべて）を取り去る。次に個人２が同じことを繰り返し、個人１が....となって、最後に一番左上の碁石を取らされたほうが負け、というルールだ。このゲームにも引き分けがないので、個人１か２に必勝法があるはずだが、じつは個人１に必勝方があることを（ただしそれが何かは明らかではない）簡単に証明することが出来る。さて、どうすればいいだろう？ひまがあったら、ちょっと考えてみると面白いかもしれない。