概要
チキンゲームの設定を考えました。
以下ルール
-
$n$人の参加者はそれぞれ1~100の数字を紙に書く。ただし他の参加者と相談することはできない。他の参加者が書いた数字を見ることもできない。
-
参加者は紙に書いた数字を賞金として貰える。ただし、他の参加者と書いた数字が被っていた場合、賞金は一切貰えない。
参加者全員が最適な戦略を立てて行動した場合、賞金額の期待値はいくらになるか考えようというお話です。
もちろん協力や相談は無し、全員自分の利益を最大化することを目指します。
混合戦略のすゝめ
どの数字を選ぶのが最適か？
例えば100を選ぶのが最適かどうか考えます。
最適であるということは、参加者全員にとってその行動を取るのが望ましいということです。しかし、参加者全員が100を選んだ場合、全員が選んだ数字が重複してしまい、誰も賞金を獲得できません。これは99, 98, ... , 1を選んだ場合でも同様です。
よって、ある一つの数字を選ぶという行動は最適でないことがわかります。
確率的に数字を選ぶ
次に、確率的に数字を選ぶ方法を検討します。これは、例えば$20$%の確率で100を選び、$10$%の確率で99を選ぶ、といった具合に、事前に各数字を選ぶ確率を決めておくというものです。このような戦略を混合戦略と呼びます。
ここで、最適な混合戦略である良い戦略が存在すると仮定し、その確率分布がどのようなものになるか考えてみます。
まずは結果から
簡単な例(M=10, n=2)
簡単のために、まずは選べる数字を1~10、プレイヤー人数を2人としたときの良い戦略を紹介します。
図は、各選択に配分すべき確率の分布を表しています。横軸は選択する数字、縦軸は選ぶ確率を表しています。
10を選択する確率が最大で、数字が小さくなるにつれて確率を下げていき、6以下は全く選択しないのが良い戦略となっています。
自身がこの戦略を取っている場合、相手がどんなに合理的でも、非合理的でも、10しか選ばないヤンキーでも、一定の期待値以上の利得を担保できます。
全てのプレイヤーが良い戦略をとったとき、このゲームの期待値は約$6.263$になります。
本題(M=100, n=色々)
選べる数字を1~100とし、プレイヤーの人数が2人, 10人, 100人, 1000人のときそれぞれの良い戦略について以下の図に表しました。
これらの図から、このゲームの性質について以下のようなことが言えそうです。
- プレイヤー人数が多いほどゲームの期待値は減少する。
- プレイヤー人数が多いほど選ぶ可能性のある選択肢を広く持つ必要がある。
- 期待値より小さな数字を選ぶ必要はない。
この結果が直感的だと思っていただけたなら幸いですが、根拠を言え。正しい根拠を言え。と思われた方もいると思うので、一応思考の過程について以下に文章をまとめてみました。
主にナッシュ均衡の考え方を元にしています。
思考の過程
ナッシュ均衡とは
ナッシュ均衡は、他のプレーヤーの戦略を所与とした場合、どのプレーヤーも自分の戦略を変更することによってより高い利得を得ることができない戦略の組み合わせである。
ナッシュ均衡の下では、どのプレーヤーも戦略を変更する誘因を持たない。
(ナッシュ均衡 - Wikipediaより引用)
もっと適当に説明すると、全員の戦略が決まっていたときに「あれ、俺戦略変えた方が得じゃね？」となる人がいたらその人の戦略はナッシュ均衡ではありません。
今回求めたいのは、全員が同じ戦略でかつ、「戦略変えたほうが得じゃね？」となる人が一人もいないような戦略です。
xを選んだときの期待値
自分が$x$を選んだ時、他の参加者が誰も$x$を選ばなかった場合のみ$x$万円を得ることができます。
またここで注意して欲しいのが、参加者全員が最適に行動するということは、全員が同じ確率分布に基づいて行動するということです。（そうでない場合、少なくとも誰かが最適でない行動をしていることになるため）
この条件から、$x$を選んだ時の期待値$e_x$は、$x$を選ぶ確率を$p_x$として、以下のように求めることができます。
$$e_x = x(1-p_x)^{n-1} \tag{1}$$
全体期待値を先に仮定する
全体期待値$E=\sum_x p_x e_x$を仮定してみたとき、$p_x, e_x$は以下の２つの条件を満たす必要があります。
- $x \leq E$ならば$p_x = 0$である
- 任意の$x,y > E$において、$e_x = e_y$が成り立つ
この２つが成り立つ理由について解説します。
1. x <= Eならばp_x = 0である
式(1)より、$e_x$は最大でも$x$までしか値を取りえません。
また、$e_x=x$であるためには$p_x=0$である必要があります。
よって、期待値$E$が$x$以上なら、$x$を選ぶ確率を高めることによって得をすることはないと言えます。
逆に言えば、$x$が期待値$E$より大きいなら、$x$を全く選ばないのは勿体ないです。ほんの少しの確率でも$x$を選ぶことによって、得をすることができるからです。
例えば、このゲームのルールを少し変更して、選べる数字を2~99としたとします。そしてこのゲームの期待値が仮に$50$だったとします。
ここで、選べる数字として新たに100を追加しました。
もし他の参加者が全く100を選ばないという戦略を取った場合、自分は100を選ぶことによってゲームの期待値を$100$に上げる(搾取する)ことができます。
よって全く100を選ばないという戦略は最適であるとはいえないので、100を選ぶ確率は0より大きくなることがわかります。
今度は、選べる数字として新たに1を追加しました(そして100の追加はやめておきました)。
もし他の参加者が全く1を選ばないという戦略を取った場合、全く1を選ばなければ期待値は$50$、1を選べば期待値は$1$となります。
この場合、わざわざ期待値が低い選択をするのは損なので、全く1を選ばない選択が最適となります。
これを一般化すると、以下のようになります。
$x \leq E \implies p_x = 0 \tag{a}$
$x > E \implies p_x > 0 \tag{b}$
2. 任意のx,y > Eにおいて、e_x = e_yが成り立つ
例えば$e_x > e_y$となるような$x, y (> E)$の組があった時、$E$を大きくするためには$p_y$を大きくするより$p_x$を大きくする方が得策です。
つまり、$y$を選ぶくらいなら$x$を選んだ方が得なので、ここでの最適な$p_y$は$p_y=0$となり、その分$p_x$を増やした方が得策ということになります。
しかし$y > E$なのに$p_y=0$であるというのは、命題(b)に矛盾します。
よって$e_x > e_y$となるような$x, y (> E)$の組があってはいけません。
このことから、任意の$x,y > E$において、$e_x = e_y$が成り立つことが説明できます。
一般化すると以下のようになります。
$x > E, y > E \implies e_x = e_y \tag{c}$
問題の定式化
ここで今まで出てきた変数をまとめます。
- $n$ : プレイヤーの人数
- $M$ : 選べる数字の上限
- $e_x$ : $x$を選んだときの期待値
- $p_x$ : 良い戦略で$x$を選ぶ確率
- $E$ : ゲーム全体の期待値
出てきた命題をまとめると、
$x \leq E \implies p_x = 0 \tag{a}$
$x > E \implies p_x > 0 \tag{b}$
$x > E, y > E \implies e_x = e_y \tag{c}$
また$e_x, p_x, E$の関係性は、
$e_x = x(1-p_x)^{n-1} \tag{1}$
$E=\sum_x p_x e_x \tag{2}$
$\sum_x p_x = 1 \tag{3}$
ここから、具体的に$e_x, p_x$がどのような値を取るかを考察していきます。
Eを使ってp_xとe_xを表す
まず命題(a)より$x \leq E$のとき$e_x = 0$なので、式(2)を以下のように書き直せます。
$E=\sum_{x>E} p_x e_x \tag{4}$
更に命題(c)と式(3)より、$x>E$となる任意の$x$について、$e_x=k$と置くと、
$E=k \sum_{x>E} p_x = k \tag{5}$
このことから、$x>E$となる任意の$x$について、$e_x=E$であることが示せます。
まとめると、$e_x$は以下のように表せます。
\begin{align}
e_x =
\begin{cases}
0 & (x \leq E)\\
E & (x > E)
\end{cases}
\tag{6}
\end{align}
更に式(1)より、$p_x$は以下のように表せます。
\begin{align}
p_x =
\begin{cases}
0 & (x \leq E)\\
1-(\frac{E}{x})^{\frac{1}{n-1}} & (x > E)
\end{cases}
\tag{7}
\end{align}
Eの値を求めたい
$E$以下の最大の整数を$a$、選べる数字の最大値を$M$とおくと、式(3)より、
$\sum_{a+1}^{M} \left[1-(\frac{E}{x})^\frac{1}{n-1}\right] = 1 \tag{8}$
式(8)より、
$$E={\left[\frac{M-a-1}{\sum_{a+1}^{M} \frac{1}{x}^{\frac{1}{n-1}}}\right]}^{n-1} \tag{9}$$
ここでの$E$は、$M$から$a+1$までの整数を戦略に使用するときの最大期待値と考えることができます。
よって、$a$は$E$が最大となるような$0$から$M-1$までの整数であると考えることができ、更に$E$は極値を一つしかもたないので、三分探索などのアルゴリズムを用いることにより、$\sum^M_{a+1} \frac{1}{x}^{\frac{1}{n-1}}$の計算量と合わせて$O(M\log M)$の計算量で$E$を求めることができます。
まとめ
選べる数字の上限$M$、プレイヤーの人数$n$を与えたとき、
ゲームの期待値$E$、各選択に配分すべき確率$p_1, p_2, \dots , p_M$を求める方法は、
- ${\left[\frac{M-a-1}{\sum_{a+1}^{M} \frac{1}{x}^{\frac{1}{n-1}}}\right]}^{n-1}$が最大になるような整数$a$を求め、この値を$E$とする
- 式(7)に従って、$p_1, p_2, \dots , p_M$を求める
以上の手順で求めることができます。
Pythonコード
以下は選べる数字の上限を100、プレイヤーの人数を10人と設定した時のゲームの期待値$E$、各選択に配分すべき確率$p_1, p_2, \dots , p_M$を求めるコードの一例です。
# 三分探索
def ternary_search(func, lo=0, hi=10**9):
while lo < hi:
mid1, mid2 = (hi+lo*2)//3, (hi*2+lo)//3
if func(mid1) >= func(mid2):
hi = mid2
else:
lo = mid1+1
return lo
# aを固定したときのEを求める
def find_E(m, n, a):
return ((m-a)/sum(j**(1/(1-n)) for j in range(a, m+1)))**(n-1)
# n, mから期待値E, 確率分布p_listを求める
def solve(m, n):
a = ternary_search(lambda a: find_E(m, n, a), lo=1, hi=m)
E = find_E(m, n, a)
p_list = np.arange(1, m+1)
p_list = 1-(E/p_list)**(1/(n-1))
p_list[:a-1] = 0
return E, p_list
E, p_list = solve(100, 10)
補足
最適化問題として捉えた時の罠
最初、この問題を
\begin{align}
\text{maximize}
& \quad \sum^M_{x=1} xp_x (1-p_x)^{n-1} \\
\text{subject to}
& \quad \sum^M_{x=1} p_x = 1 \\
& \quad p_x \geq 0
\end{align}
で表される最適化問題として考えていましたが、これは必ずしもナッシュ均衡解になるとは限らないので不適切だということに気が付きました。
ナッシュ均衡解の正しい理解
今回示した戦略の解は、全員が同じ戦略かつナッシュ均衡解という意味で面白い解だと思っていますが、「この戦略を使っていれば、長期的に見て相手より高い利益を得られる」のような解釈は必ずしも正しくないことについて言及しておきます。
例えばプレイヤーの人数が2人の場合に、相手が100しか選ばないという脳死戦略を取ってきたとしても、この戦略を使うことで得られる利得は自分も相手も変わりません。
この戦略を「最適戦略」と呼ばず「良い戦略」と呼んでいたのはこういった理由があります。あまり面白くないですね。
じゃあ結局この記事は何だったんだ、てかナッシュ均衡解って結局意味あんのかということになりますが、私は少なくとも以下の２つの意味で有意義だと思っています。
-
ナッシュ均衡解を使うことで、ゲームの期待値が分かる
ゲームの設計を行う等するときに、期待値が分かれば適切な掛け金を設定したり、利益を予想したりすることができます。 -
必勝法を考えるための基準となる
ナッシュ均衡解とは要するに、その戦略を取っていれば搾取されないような行動のことです。
これは裏をかえせば、相手の戦略がナッシュ均衡解からずれている場合、相手を搾取できる＝自分の利益をもっと増やせるチャンスであることを意味します。
つまり自分だけがナッシュ均衡解を知っている場合、相手の戦略の偏りを正しく予測できれば、それを咎める戦略をとることで自分の利得の期待値を上げることができます。