n人ゲームの均衡点 - タイプするサル

Equilibrium points in n-person games
John F. Nash, Jr.
Princeton University
Communicated by S. Lefschetz, November 16, 1949

n人ゲームの概念は以下のように定義できます。プレイヤそれぞれが純粋戦略の有限集合を持ちます。プレイヤn人への報酬の組みは純粋戦略のn個組み(1つ1つの戦略はそれぞれのプレイヤが選択)にそれぞれ確定的に対応します。混合戦略とは純粋戦略上の確率分布ですが、混合戦略においては報酬函数はプレイヤの期待値です。なので、報酬函数は様々なプレイヤが様々な純粋戦略を取る確率に対して多線形形式になります。

One may define a concept of an n-person game in which each player has a finite set of pure strategies and in which a definite set of payments to the n players corresponds to each n-tuple of pure strategies, one strategy being taken for each player. For mixed strategies, which are probability distributions over the pure strategies, the pay-off functions are the expectations of the players, thus becoming polylinear forms in the probabilities with which the various players play their various pure strategies.

戦略の任意のn個組み(それぞれのプレイヤ用に1つ)は、プレイヤの戦略空間n個を掛け合わせた積空間内の点とみなすことができます。
反撃するn個組みの中のプレイヤそれぞれの戦略が反撃されるn個組みの中の他のプレイヤのn - 1個の戦略に対してプレイヤが獲得できる最高の期待値を生み出すなら、そんなn個組みはもう一方を反撃します。自己反撃なn個組みは均衡点と呼ばれます。

Any n-tuple of strategies, one for each player, may be regarded as a point in the product space obtained by multiplying the n strategy spaces of the players. One such n-tuple counters another if the strategy of each player in the countering n-tuple yields the highest obtainable expectation for its player against the n − 1 strategies of the other players in the countered n-tuple. A self-countering n-tuple is called an equilibrium point.

n個組みそれぞれからそれを反撃するn個組みの集合への対応は、積空間からそれ自身への1対多写像を与えます。反撃の定義から、ある点を反撃する点の集合は凸であることがわかります。報酬函数の連続性を使うと、写像のグラフが閉であることがわかります。閉とは以下と同値です: P1, P2, ...とQ1, Q2, ..., Qn, ....が空間内の一連の点で、Qn → Q, Pn → Pでかつ、QnがPnを反撃するなら、 QはPを反撃する。

The correspondence of each n-tuple with its set of countering n-tuples gives a one-to-many mapping of the product space into itself. From the definition of countering we see that the set of countering points of a point is convex. By using the continuity of the pay-off functions we see that the graph of the mapping is closed. The closedness is equivalent to saying: if P1, P2, … and Q1, Q2, …, Qn, … are sequences of points in the product space where Qn → Q, Pn → P and Qn counters Pn then Q counters P.

グラフが閉であり、写像のそれぞれの点の像が凸なので、角谷の定理から写像は不動点(すなわち、像に含まれる点)を持つと結論します。従って均衡点が存在します。

Since the graph is closed and since the image of each point under the mapping is convex, we infer from Kakutani’s theorem that the mapping has a fixed point (i.e., point contained in its image). Hence there is an equilibrium point.

2人ゼロサムの場合、(Von Neumannの)「主定理」と平衡点の存在は同値です。この場合、どんな2つの平衡点もプレイヤの期待値が同じになります。これは一般にはかならずしも成り立ちません。

In the two-person zero-sum case the “main theorem” and the existence of an equilibrium point are equivalent. In this case any two equilibrium points lead to the same expectations for the players, but this need not occur in general.

感想

数学的にデリケートなことを言わなければやっぱり当たり前に聞こえますね。ノーベル賞の素になる概念だと知りながら読んでこれだから、私には先見性とか応用性とかが頭からごっそり欠けているような。

でも色々示唆はありますね。今の世の中、政治とか職業に関する考え方とか、対立的で2極が互いを批判する構図をよく目にします。でも、1極に統一してもそれは均衡点ではない。報酬函数が変わった時に新たな均衡点を探すのは市場がうまくやるにしても、(TPPに参加するとか)報酬函数の変更そのものがパレート効率的でないからもめる。エンジニアがトレードオフを言い訳にするのとよく似ています。パレート改善の夢こそ今の世の中が見たがっているもの。