戦力を3つに分けて2勝したら勝ちのゲームのナッシュ均衡

概要

  • 「分割して番勝負」はゲームの基本的なメカニクスの1つだと思うが、知っていたのは三すくみを含んでいることくらいで、考察したことがなかった。
  • こういう具体例を計算してみると、ナッシュ均衡の特徴付けのどれが便利かが分かってくる。
  • 正六角形（内側を含む）の上の確率分布で辺に垂直な成分への射影がどれも（長さ√3の）線分上の一様分布となるものを挙げよ。

経緯

課金ゲームを無課金で遊んでいたら、レベルカンストで3編成作るのが難しいという困難が発生して、3つに分ける部分がそれなりに重要になってしまう。

ボードゲームでこのタイプの判断が出てくることもよくある。リソースを今使うか後で使うかということ。どちらかというと前の勝敗を見てから後の分割を決めてよいルールになりがちなので違うゲームだが今回は考察しない。

ゲームのメカニクスは構成要素にすぎないが、それぞれの要素について考察しておくと有用そうな気がしたので、最も簡単な「3つに分けて2本とったら勝ち」だけのゲームを解いてみよう。

定式化

（純粋）戦略 $(x, y, z) \in \Delta = \lbrace x + y + z = 1, x ≥ 0, y ≥ 0, z ≥ 0\rbrace$ 上の零和ゲーム。利得は $\mathrm{sign}(x - x') + \mathrm{sign}(y - y') + \mathrm{sign}(z - z')$ で与えられる。

  • ゲームの例として紹介されるときは「石100個を分けて、〜〜」などとされるが連続にした。
  • 勝敗数から線形に利得になることを用いた。
    • 「2勝以上したら勝ち」と表現されがちだが、全勝できないので。
    • 4つ以上に分けるときや合計値が不公平なときは今回のようにはできない。
    • 一方、「サイコロの目を書いて振る」ようなゲームなら分割数（何面ダイスか）によらずこのように扱える。(0, 3, 3) > (2, 2, 2) > (4, 1, 1) > (0, 3, 3) の三すくみがあることは有名（漫画のネタで使われているのも見た）。

混合戦略のナッシュ均衡が存在するかについては、コンパクト集合上の連続関数なら良かったはずで、今回は符号関数 sign が不連続だが sigmoid にかえた場合は存在することは言える。その極限っぽいが存在だけを先に厳密に示す方法はよく分からない。なお、以下で実際に構成できるので良い。

必要条件をつめる

ナッシュ均衡の存在定理を勉強したときには補題がいろいろあったり、どれが重要な特徴付けなのか記憶に残らなかったのだが、実際に手計算していると決まったテクがあるように感じられてくる。（コンピュータで解く場合のアルゴリズムについては私はあまり詳しくないがCounterfactual Regret Minimizationがよく使われているかもしれない。）

ナッシュ均衡を手計算するテクを一言でまとめると、混合戦略であって純粋戦略に exploit されないものを探すと良い。

  • 例1：じゃんけん。対称零和ゲームなので目標の利得は0。ナッシュ均衡になりうる混合戦略（それぞれの手を出す確率）を(p, q, r) (p+q+r=1)とおくと、相手の手に対して q−r≥0, r−p≥0, p−q≥0 を得るので p=q=r=1/3 である。

  • 例2：利得行列 $\begin{pmatrix}1 & -1 \newline -2 & 2\end{pmatrix}$ の零和ゲーム。行を選ぶプレイヤーの混合戦略を (p, q) とおくと、 min(p−2q, −p+2q) を最大化したいので (p, q) = (2/3, 1/3) のとき最大値 0 を得る。同様に列を選ぶプレイヤーの混合戦略 (1/2, 1/2) が求まりこれらについてナッシュ均衡となる。

    • ところで、ある漫画で例2のゲームについてナッシュ均衡と異なる戦略がセオリーとされていたが、人の直感の当てにならなさを表していたのか、キャラの頭の悪さを表していたのか、作者が知らなかっただけなのかどれだろう。

  • 補足：手番が1度きりのゲームのみここでは扱っているが、複数回の手番があるゲームでも、相手の純粋戦略のみ考えればよい。すなわち、どの状態でも相手は非確率的に選択するとしてよい。

では3つに分けて2勝するゲームを考えていこう。対称零和ゲームなので 0 にできれば良い。混合戦略を表す $\Delta$ 上の確率分布 μ(x, y, z) と相手の純粋戦略 $(a, b, c)\in\Delta$ について満たすべき条件は

 \displaystyle
\begin{aligned}
0 &\le \int_\Delta (\mathrm{sign}(x - a) + \mathrm{sign}(y - b) + \mathrm{sign}(z - c)) \mathrm{d}\mu(x,y,z) \newline
& = \int_{0}^{1} \mathrm{sign}(x - a)\mathrm{d}\mu(x)
+ \int_{0}^{1} \mathrm{sign}(y - b)\mathrm{d}\mu(y)
+ \int_{0}^{1} \mathrm{sign}(z - c)\mathrm{d}\mu(z)
\end{aligned}

ただし確率分布 μ(x, y, z) の射影（同時分布に対する周辺分布）を μ(x), μ(y), μ(z) とおいた。さらにcdf（累積分布関数）を f(x), g(y), h(z) とおけば、 $f(a) + g(b) + h(c) \le 3/2$ と同値（厳密にはcdfが端点を1/2だけ算入するように定義をいじる必要があるが）。

また、 x+y+z = 1 だったので、cdfたちは $\int f(x)\mathrm{d}x + \int g(y)\mathrm{d}y + \int h(z)\mathrm{d}z=2$ を満たす。なぜなら、

 \displaystyle
\int_{0}^{1} f(x)\mathrm{d}x
= \int_{0}^{1} (\int_{0}^{x'} \mathrm{d}\mu(x)) \mathrm{d}x'
= \int_{0}^{1}(\int_{x}^{1} \mathrm{d}x') \mathrm{d}\mu(x)
= 1 - \int_{0}^{1} x\mathrm{d}\mu(x)

構成

ここからは予想して証明する感じになっていく。

$f(x) + g(y) + h(z) \le 3/2 \;(x+y+z=1)$ を満たしつつ f, g, h を大きくしようとすると、 f(x) = g(x) = h(x) = min(3x/2, 1) くらいしかないと予想できるので、こうなる分布 μ を構成したい。

言い換えると、正六角形 $\lbrace x+y+z=1, 0\le x\le 2/3, 0\le y\le 2/3, 0\le z\le 2/3\rbrace$ 上の分布で、それぞれの成分が [0, 2/3] 上の一様分布であるものがほしい。

ここで何らかのひらめきにより、 (2/3, 1/3, 0), (0, 2/3, 1/3), (1/3, 0, 2/3) を結ぶ正三角形の周上の一様分布（$\mu_1$ とおく）が条件を満たすことが分かる。このゲームをするように迫られた場合の実用上はこの戦略でとりあえず損しないので覚えておくと良さそう。

別のひらめきにより、正六角形の辺からの距離が辺と中心の距離 (= √6/6) の (1-t) 倍である点の確率密度を t に比例するようにした分布（$\mu_2$ とおく）も条件を満たすことが分かる。実際、 $$ t^{2} + 2\int_{t}^{1} s\mathrm{d}s = 1 = \textrm{const.} $$

分布 μ1, μ2
分布 μ1, μ2

唯一性

このようにナッシュ均衡は唯一ではないが、「内側含む正六角形上の分布で3つの射影がすべて一様」という特徴付けが正しいことは以下のように示せる。

2個めに紹介する有用なテクとして、強そうな戦略が見つかったら相手に代入すると良い。（今回は対称なのでそのまま代入しているが、一般には考察するプレイヤーがここで入れ替わる。）

言い換えた条件の側でいえば、見つけた戦略（確率分布）$\nu=\mu_1$ や $\nu=\mu_2$ で $f(x) + g(y) + h(z) \le 3/2$ を積分することを意味し、 $$ \begin{aligned} \frac{3}{2} &\ge \int_\Delta (f(x)+g(y)+h(z))\mathrm{d}\nu(x,y,z) \newline &= \int f(x)\mathrm{d}\nu(x) + \int g(y)\mathrm{d}\nu(y) + \int h(z)\mathrm{d}\nu(z) \newline &= \frac{3}{2} (\int_0^{\frac{2}{3}}f(x)\mathrm{d}x + \int_0^{\frac{2}{3}}g(y)\mathrm{d}y + \int_0^{\frac{2}{3}}h(z)\mathrm{d}z) \end{aligned} $$ が分かる。 f ≤ 1, g ≤ 1, h ≤ 1, $\int f(x)\mathrm{d}x + \int g(y)\mathrm{d}y + \int h(z)\mathrm{d}z=2$ を思い出すと ν 上確率1で等号成立して $f(x) + g(y) + h(z) = 3/2$ となっている。$\nu = \mu_2$ のほうを用いると内部を含む正六角形上ほとんどいたるところで成立するので、あとは単調性と加法性から線形性を示す関数方程式でよくある議論をすれば f(x) = 3x/2 (0 ≤ x ≤ 2/3) などが出る（はず）。

あとがき

相手を純粋戦略として良いことと、相手にうまい混合戦略を代入すると良いことを紹介した。これらは相反して見えるが、ナッシュ均衡の同値な定義は形式上近い一方うまい使い方に違いが出るということだと思う。

記事を書いていて、線形計画法あたりの分野で知られている話題なのではと思った。（仕事じゃないから先行研究調べないのが許されている。自分で考えるのは楽しい。）

ナッシュ均衡の例を挙げ、そこそこの必要条件を出しただけなので、均衡 (μ, ν) 全体のなす空間をうまく書けるかは未解決。別のfuture workとしては分割前の戦力が不公平な場合や分割数が4以上の場合などがある。知っている方、計算した方がいたら教えてください。

ナッシュ均衡をしっかり手計算したのは、ポーカーのベット部分だけをうまく簡略化して解けないかな、とか考えていたとき以来。結局何回もレイズできる場合を解けずに放置してしまっていて悔しい。

実際のゲームに適用するには、混合戦略のナッシュ均衡が何を意味するか理解しているほうが良く、よくある誤解への解説がこれもmaspyさんのポーカー記事にまとまっている。