In Game Theory In the case of zero-sum games, the optimal mixing strategy can be found by linear optimization (LP) [^ 1]. Let's try using Python, using the arranged rock-paper-scissors as an example.
For linear optimization, refer to Use Combinatorial Optimization.
[^ 1]: From the seminar "OR starting with Excel solver"
Determine (transpose) the gain table as follows. If you win the Goo (G), your score will be quadrupled.
| Opponent \ myself | G | C | P |
|---|---|---|---|
| G | 0 | -1 | 1 |
| C | 4 | 0 | -1 |
| P | -1 | 1 | 0 |
――Let's assume that the ratio of your own goo, choki, and par is $ x, y, z $. (Mixed strategy) --At this time, $ x + y + z = 1 $. --The expected value is $ -y + z $ if the opponent is goo, $ 4x --z $ if the opponent is choki, and $ -x + y $ if the opponent is par. --Let's maximize the minimum value ($ w $) of these three expected values. By doing this, the expected value will be above $ w $ no matter what the opponent does.
| Objective function | $ w $ → Maximize |
|---|---|
| Constraints | $ x + y + z = 1 $ |
| $ 4x - z \ge w$ | |
| $ -x + y \ge w$ | |
python
from pulp import *
from ortoolpy import addvar, addvars
a = [[0, -1, 1], [4, 0, -1], [-1, 1, 0]]
m = LpProblem(sense=LpMaximize) #Mathematical model
xyz = addvars(3) #Variable x,y,z
w = addvar(lowBound=None) #Variable w
m += w #Objective function
m += lpSum(xyz) == 1 #Constraints
for i in range(3):
m += lpDot(a[i], xyz) >= w #Constraints
m.solve() #Solution
print(value(w), [value(v) for v in xyz])
>>>
0.16666667 [0.16666667, 0.33333333, 0.5]
If you put out goo, choki, and par at a ratio of [1/6, 1/3, 1/2], you can see that the expected value can be reduced to 1/6 no matter what the opponent does.
In non-cooperative games, the interesting result is that the expected value will be higher if the ratio of hands (goo) that is advantageous to you is reduced.
that's all
Recommended Posts