これなに
「授業で使える 中学校数学パズル・ゲーム大全」という本のp136の問題について、3人の場合の戦略を考えてみます。
その問題(アレンジしています)
3人で変形じゃんけんをします。みんなで同時に指を0本か1本か2本出します。3人の指の合計を3で割った余りと等しい指を出した人が勝ちです。
- 0人勝ちの場合:全員の得点0
- 1人勝ちの場合:勝った人の得点2、負けた人の得点-1
- 2人勝ちの場合:勝った人の得点0.5、負けた人の得点-1
- 3人勝ちの場合:全員の得点0
考え方その1
「組合せ最適化でゲーム理論を解く」を参考にして、混合戦略を最適化で解きましょう。
私(k)の各指を出す確率をxyz = [x, y, z]
としましょう。
2人(iとj)が出す指に対する得点の最小値を最大化します。
定式化は参考先と同様に考えます。解いてみましょう。
from pulp import LpProblem, LpMaximize, LpVariable, lpSum, value
def val(i, j, k):
"""kの得点"""
h = (i + j + k) % 3
wini = i == h
winj = j == h
wink = k == h
s = wini + winj + wink
return 0 if s % 3 == 0 else (3 - s) / s if wink else -1
m = LpProblem(sense=LpMaximize)
w = LpVariable('w')
xyz = [LpVariable(c, 0, 1) for c in 'xyz']
m += w
m += lpSum(xyz) == 1
for i in range(3):
for j in range(3):
e = lpSum(val(i, j, k) * v for k, v in enumerate(xyz))
m += w <= e
m.solve()
print(value(m.objective), [value(v) for v in xyz])
出力
-0.5 [0.0, 0.5, 0.5]
出力は、目的関数値とxyz
の値です。
負け越してます。これは、2人(iとj)が私(k)を負かすために共闘している前提だからですね。
考え方その2
2人が共闘しないと仮定しましょう。一旦、1人(j)が混合戦略(pjs
)に従い、1人(i)は、私(k)を負かすために最善を尽くすとします。
とりあえず、pjs = [0.0, 0.5, 0.5]
とします。
pjs = [0.0, 0.5, 0.5]
m = LpProblem(sense=LpMaximize)
w = LpVariable('w')
xyz = [LpVariable(c, 0, 1) for c in 'xyz']
m += w
m += lpSum(xyz) == 1
for i in range(3):
e = lpSum(pj * val(i, j, k) * v
for j, pj in enumerate(pjs)
for k, v in enumerate(xyz))
m += w <= e
m.solve()
print(value(m.objective), [value(v) for v in xyz])
出力
-0.5 [0.0, 0.0, 1.0]
やっぱり負け越しています。これは、1人(i)が、私(k)を狙い撃ちしているからでしょうか。
考え方その3
2人分(iとjとします)の混合戦略を知っている場合を確認します。
pis = [0.0, 0.5, 0.5]
pjs = [0.0, 0.0, 1.0]
m = LpProblem(sense=LpMaximize)
w = LpVariable('w')
xyz = [LpVariable(c, 0, 1) for c in 'xyz']
m += w
m += lpSum(xyz) == 1
e = lpSum(pi * pj * val(i, j, k) * v
for i, pi in enumerate(pis)
for j, pj in enumerate(pjs)
for k, v in enumerate(xyz))
m += w <= e
m.solve()
print(value(m.objective), [value(v) for v in xyz])
出力
1.0 [1.0, 0.0, 0.0]
勝ち越しました。これは、2人(iとj)は、私(k)の戦略を知らず、私だけ2人の戦略を知っているからでしょう。
考え方その4
混合戦略を知られると対策を取られて不利になります。どうすればいいでしょうか?
1人(j)の混合戦略を[1 / 3, 1 / 3, 1 / 3]
として試してみましょう。
pjs = [1 / 3, 1 / 3, 1 / 3]
m = LpProblem(sense=LpMaximize)
w = LpVariable('w')
xyz = [LpVariable(c, 0, 1) for c in 'xyz']
m += w
m += lpSum(xyz) == 1
for i in range(3):
e = lpSum(pj * val(i, j, k) * v
for j, pj in enumerate(pjs)
for k, v in enumerate(xyz))
m += w <= e
m.solve()
print(value(m.objective), [value(v) for v in xyz])
出力
0.0 [0.33333333, 0.33333333, 0.33333333]
1人(j)が均等に出す場合、私(k)も均等に出せば、最悪でも引き分けにできました。
考え方その5
2人(iとj)が均等に出す場合、残りの人の最適な混合戦略を確かめてみましょう。
pis = [1 / 3, 1 / 3, 1 / 3]
pjs = [1 / 3, 1 / 3, 1 / 3]
m = LpProblem(sense=LpMaximize)
w = LpVariable('w')
xyz = [LpVariable(c, 0, 1) for c in 'xyz']
m += w
m += lpSum(xyz) == 1
e = lpSum(pi * pj * val(i, j, k) * v
for i, pi in enumerate(pis)
for j, pj in enumerate(pjs)
for k, v in enumerate(xyz))
m += w <= e
m.solve()
print(value(m.objective), [value(v) for v in xyz])
出力
0.0 [0.0, 0.0, 1.0]
2人の混合戦略を知っていても、得点の期待値は0になりました。ちなみに、xyz
をどのようにしても期待値は0です。
結局、「誰も共闘しない」という前提で、他の人に混合戦略を対策されたとしても均等に出せば、期待値は0になるようです。
均等にしないと対策されて負け越してしまうので、おそらくこれが取るべき戦略になると思われます。
以上