ゲーム理論とコンピュータサイエンスとの関わりについて：

What computer science can teach economics

ゲーム理論はビジネススクールでも教えられる程、現代社会では重要な分野となっている。しかし、ゲーム理論の課題の一つに、均衡が存在するとしてそれを本当に経済主体がそれを発見できるのかという問題がある。これに対しMITのConstantinos Daskalakisによる研究が紹介されている（BerkeleyでのPh.D. Dissertationだ）。

ナッシュ均衡自体については説明は必要ないだろう。非協力ゲームのおいて、他のプレーヤーの戦略を所与としたときにどのプレーヤーも自分の戦略を変更することで利得を増やすことができないような戦略の組である。

In soccer, a penalty kick gives the offensive player a shot on goal with only the goalie defending. The goalie has so little reaction time that she has to guess which half of the goal to protect just as the ball is struck; the shooter tries to go the opposite way. In the game-theory version, the goalie always wins if both players pick the same half of the goal, and the shooter wins if they pick different halves. So each player has two strategies — go left or go right — and there are two outcomes — kicker wins or goalie wins.

It’s probably obvious that the best strategy for both players is to randomly go left or right with equal probability; that way, both will win about half the time. And indeed, that pair of strategies is what’s called the “Nash equilibrium” for the game.

記事中ではサッカーのペナルティーキックが上げられている。キッカーとキーパーは右と左の二つの選択肢しか持っていない。キーパーはキッカーの動きを見てから行動する暇がないのでこれは実質的に二人の行動は同時に起きていると考えられる。この時、最適な戦略は右と左を同じ確率で選択することだ。相手がそういしているならこちらが確率を変えても結果は同じだ。これがペナルティーキックというゲームのナッシュ均衡になっている。

Of course, most games are more complicated than the penalty-kick game, and their Nash equilibria are more difficult to calculate. But the reason the Nash equilibrium is associated with Nash’s name  — and not the names of other mathematicians who, over the preceding century, had described Nash equilibria for particular games — is that Nash was the first to prove that every game must have a Nash equilibrium.

大抵のゲームはペナルティーキックよりも複雑であり、ナッシュ均衡もまた計算が困難だ。ジョン・ナッシュが素晴らしいのは、均衡概念を定義した点ではなく、どんなゲームもナッシュ均衡を持つことを証明四タテんである。

Many economists assume that, while the Nash equilibrium for a particular market may be hard to find, once found, it will accurately describe the market’s behavior.

そしてエコノミストの多くはナッシュ均衡を実際に見つけるのが困難であっても、一度見つかれば市場の行動を性格に記述すると仮定している。

Daskalakis, working with Christos Papadimitriou of the University of California, Berkeley, and the University of Liverpool’s Paul Goldberg, has shown that for some games, the Nash equilibrium is so hard to calculate that all the computers in the world couldn’t find it in the lifetime of the universe.

紹介されている論文は、このようなエコノミストの仮定に疑問を投げかけるものだ。それによれば、いくつかのゲームにおいて（存在することは証明されている）ナッシュ均衡を見つけるのは極めて困難で、全世界のコンピュータを世界が終わるまで使いつづけても見つからないという。

The argument has some empirical support. Approximations of the Nash equilibrium for two-player poker have been calculated, and professional poker players tend to adhere to it — particularly if they’ve read any of the many books or articles on game theory’s implications for poker. The Nash equilibrium for three-player poker, however, is intractably hard to calculate, and professional poker players don’t seem to have found it.

このことは実証面でも支持されている。二人ポーカーのナッシュ均衡は計算されているし、実際のプレーヤーの行動もそれに近い。しかし三人ポーカーのナッシュ均衡は計算が困難でプロプレーヤーもそれを発見しているようには思われない。

Daskalakis’s thesis showed that the Nash equilibrium belongs to a set of problems that is well studied in computer science: those whose solutions may be hard to find but are always relatively easy to verify.

DaskalakisはこれをコンピュータサイエンスにおけるP/NP問題として捉える。ナッシュ均衡の計算は、解を得るのが難しいが確認するのは簡単なNP問題の一種だと証明した。

これに対し彼は三つの方向性を提示している：

One is to say, We know that there exist games that are hard, but maybe most of them are not hard.”

一つは、計算が簡単なナッシュ均衡の集合を確定すること、

The second route, Daskalakis says, is to find mathematical models other than Nash equilibria to characterize markets — models that describe transition states on the way to equilibrium, for example, or other types of equilibria that aren’t so hard to calculate.

二つ目はナッシュ均衡とは異なる概念を用いること、

Finally, he says, it may be that where the Nash equilibrium is hard to calculate, some approximation of it — where the players’ strategies are almost the best responses to their opponents’ strategies — might not be.

三つ目は近似的な解を見つけることだ。

応用分野であればそもそも解の計算が非常に困難なモデルを避けるのが普通だから三つ目の対策にあたるだろうか。