これなに
ゲーム理論において、零和ゲームの場合、最適混合戦略は線形最適化(LP)で求めることができるそうです1。
アレンジしたじゃんけんを例にして、Pythonでやってみます。
線形最適化については、組合せ最適化を使おうを参考にしてください。
じゃんけんの利得表
利得表(の転置)を次のように決めます。自分がグー(G)で勝つと、得点が4倍になります。
| 相手＼自分 | G | C | P |
|---|---|---|---|
| G | 0 | -1 | 1 |
| C | 4 | 0 | -1 |
| P | -1 | 1 | 0 |
定式化
- 自分がグー、チョキ、パーを出す割合を$x, y, z$ とします。(混合戦略)
- このとき、$x+y+z = 1$ です。
- 期待値は、相手がグーの場合 $-y + z$、相手がチョキの場合 $4x - z$、相手がパーの場合 $-x + y$ になります。
- この3つの期待値の最小値($w$)を最大化しましょう。こうすることによって、相手がどんな手を出そうが、期待値は $w$ 以上になります。
| 目的関数 | $w$ → 最大化 |
|---|---|
| 制約条件 | $x+y+z = 1$ |
| $-y + z \ge w$ | |
| $ 4x - z \ge w$ | |
| $ -x + y \ge w$ | |
| $x,y,z \ge 0, ~~~ w: free$ |
Pythonで解く
python
from pulp import *
from ortoolpy import addvar, addvars
a = [[0, -1, 1], [4, 0, -1], [-1, 1, 0]]
m = LpProblem(sense=LpMaximize) # 数理モデル
xyz = addvars(3) # 変数 x,y,z
w = addvar(lowBound=None) # 変数 w
m += w # 目的関数
m += lpSum(xyz) == 1 # 制約条件
for i in range(3):
m += lpDot(a[i], xyz) >= w # 制約条件
m.solve() # 求解
print(value(w), [value(v) for v in xyz])
>>>
0.16666667 [0.16666667, 0.33333333, 0.5]
自分がグー、チョキ、パーを[1/6, 1/3, 1/2] の割合で出すと、相手がどんな手を出してきても、期待値を1/6にできることがわかります。
非協力ゲームでは、自分に有利な手(グー)の割合を小さくした方が、期待値が高くなるという面白い結果になります。
以上
-
セミナー『ExcelソルバーではじめるOR』より ↩