ISEGORIA / 数学百科事典
ゲーム理論：相手も選ぶときの戦略
結果が他人の選択にも左右されるとき、最善の手は相手が何をすると予想するかで決まり、相手もあなたについて同じように考えます。ナッシュ均衡とは、だれも一人だけでは変えたくない選択の組で、全員に良いこともあれば、全員に悪いこともあり、確率を混ぜなければ存在しないこともあります。推論の代わりに成功によって戦略が広まるとすると、同じ利得が集団を循環させます。そして純粋な対立のゲームでは、最適に確率を混ぜることが一組の双対な線形計画になります。
前提知識: 確率、期待値、線形最適化
予想してから操作し、計算例と問いで理解を確かめてください。グラフは数式の図示であり、証明ではありません。
1. 二人、二つの選択、ナッシュ均衡
二人のゲームでは、各プレイヤーが行か列を選び、表が両者の利得を与えます。どちらのプレイヤーも一人だけ手を変えて得をしない選択の組がナッシュ均衡です。表の上では、逸脱の矢印が一本も出ていないマスです。プレイヤーは確率を混ぜることもでき、行は第 1 行を確率 p で、列は第 1 列を確率 q で選びます。相手の混合に対する各プレイヤーの最適応答は階段関数で、均衡はちょうど二つの最適応答のグラフが交わる所です。混合均衡は、各プレイヤーの混合が相手を無差別にする所です。有名なゲームを選んで戦略の点をドラッグしてください。流線は両プレイヤーがより良い応答へ流れていく様子を示します。
計算例. 鹿狩りでは、鹿を狩ると相手も鹿を狩れば 4、そうでなければ 0 で、兎を狩れば確実に 3 です。行は \(4q=3\) のとき無差別なので \(q^*=3/4\)、対称性から \(p^*=3/4\) です。この混合均衡ではどちらもちょうど 3 を期待し、安全な兎と変わりません。男女の争いでは、行は \(3q=2(1-q)\) のとき無差別で \(q^*=2/5\)、列は \(2p=3(1-p)\) のとき無差別で \(p^*=3/5\) です。このとき二人とも \(6/5\) を期待し、どちらの協調した結果の 2 や 3 よりも少なくなります。
注意点. ナッシュ均衡は安定性の条件であって、予測や推奨ではありません。囚人のジレンマにはただ一つの均衡がありますが、二人とも喜んで別の結果と交換するでしょう。また均衡が複数あるゲームは、どれが実際に選ばれるかについて何も言いません。流線は二集団のレプリケーター動学で、学習の自然なモデルの一つです。他の学習の規則は、均衡は同じでも別の流れを与えます。
均衡で確率を混ぜるプレイヤーは、なぜ混ぜる選択肢の間で無差別でなければならないのですか？
混合の期待利得は、純粋戦略の利得を確率で重みづけた平均だからです。ある選択肢の方が厳密に多く払うなら、すべての確率をそれに移せば平均が上がるので、その混合は最適応答ではありません。だから各プレイヤーの均衡での混合は相手の利得で決まります。それは自分のためではなく、相手を無差別にするように選ばれるのです。
2. レプリケーター動学：グー、チョキ、パー
推論するプレイヤーの代わりに、戦略が成功に比例して広まる大きな集団を考えます。ある戦略の割合は、それが集団の平均よりどれだけ良いかに等しい率で増えます。じゃんけんではどの戦略も他の戦略に負けるので、集団は循環します。循環が収まるかどうかは、負けの損失を 1 としたときの勝ちの利得 w というただ一つの数で決まります。勝ちの価値が負けの損失より大きければ混ざることが得になり、どの軌道も三分の一ずつの点へ渦を巻いて入ります。小さければ循環は激しい好況と崩壊へ育ちます。w = 1 では三つの割合の積が保存され、循環は永遠に続きます。出発点をドラッグし、w を変えてください。
計算例. \(A\) のどの列も和が \(w-1\) なので \(\sum_i(Ax)_i=w-1\) で、平均利得は \(x\cdot Ax=(w-1)(x_1x_2+x_2x_3+x_3x_1)\) です。\((x_1+x_2+x_3)^2=1\ge3(x_1x_2+x_2x_3+x_3x_1)\) なので括弧の中は決して負にならず、\(\log(x_1x_2x_3)\) は \(w>1\) のとき増え、\(w<1\) のとき減ります。中心の近くの運動は固有値 \((1-w)/6\pm i(w+1)/(2\sqrt3)\) の渦です。\(w=0.5\) では \(0.083\pm0.433i\) で、14.5 時間単位ごとに一回転し、一回転ごとに \(e^{0.083\times14.5}=3.3\) 倍に広がります。
注意点. レプリケーター動学がモデルにするのは個人ではなく集団です。割合は成功の差によって変わり、それは模倣でも繁殖でも強化学習でもかまいませんが、だれも最適化はしていません。\(w<1\) では軌道は境界に近づくだけで、決して到達しません。有限の集団なら、それよりずっと前に偶然である戦略を失うでしょう。ワキモンユタトカゲや一部の細菌の群集は、自然界のじゃんけんの例としてよく挙げられます。
w = 1 のとき、なぜ割合の積がちょうど保存されるのですか？
\(w=1\) ではゲームはゼロ和で \(A=-A^{T}\) なので、平均利得 \(x\cdot Ax\) はどの集団でも 0 で、各割合は \((Ax)_i\) の率で変わります。すると \(\frac{d}{dt}\sum\log x_i=\sum(Ax)_i\) で、これは \(A\) の各列の和が 0 なので \(w-1=0\) です。等高線が中心を囲む閉曲線になる保存量があると、どの軌道も周期的になるしかありません。
3. ゼロ和ゲームとミニマックス定理
ゼロ和ゲームでは一方の得は他方の損なので、行は、列がどんな混合にも行に最も痛い列で答えると仮定すべきです。固定した p に対して各列は p について線形な利得を行に与え、行が当てにできるのはそれらの直線の最も低いもの、つまり下側の包絡線だけです。最良の保証はその包絡線の頂上です。列も反対側から同じように考えることができ、フォン・ノイマンのミニマックス定理は二つの保証が一致すると言います。行が確保でき、列が行をそこまで抑えられる、ただ一つの値 v があるのです。二つの最適な混合を求めることは、一組の双対な線形計画です。p をドラッグして、列の最適応答が変わる様子を見てください。
計算例. PK では、キーパーが左へ跳ぶとき、キッカーが左へ蹴れば確率 0.58、右へ蹴れば 0.93 で得点します。キーパーが右へ跳ぶときは 0.95 と 0.60 です。二本の跳ぶ直線を等しくおく \(0.93-0.35p=0.60+0.35p\) から \(p^*=0.33/0.70=0.471\) が得られます。47% の割合で左へ蹴れば、キーパーが何をしても確率 0.765 で得点できます。キーパーの最適な混合は左右に半々で跳び、決してとどまらないことです。とどまると \(0.83\times0.471+0.80\times0.529=0.814\) の失点を許すからです。これらの確率は例示で、プロの PK について報告されている範囲から選んでいます。
注意点. この定理には混合戦略が必要です。純粋戦略だけでは、コイン合わせのように行の最良の保証はふつう列の保証より厳密に小さくなります。またゲームがゼロ和である必要もあります。一般のゲームでは保証は一致しないことがあり、ナッシュ均衡がその役を引き継ぎます。図による方法が使えるのは行の純粋戦略が二つだけだからで、それより多いと包絡線は単体の上の曲面になり、線形計画がその仕事をします。
止まることはどちらのキックに対しても最悪の選択ではないのに、なぜキーパーは決して真ん中にとどまらないのですか？
キッカーの最適な混合に対しては、とどまると 0.814 の失点を許しますが、どちらに跳んでも 0.765 だからです。\(p^*\) で値より上にある列は、最適な混合に決して入りません。それに少しでも重みを混ぜると、キッカーが直面する直線がどこかで \(v\) を超え、キッカーに値より多くを与えてしまいます。とどまるのは予測できるキッカーへの良い答えですが、最適なキッカーに対しては、二つの跳ぶ方向の間で確率を混ぜる方が優れています。