Solving game theory with combinatorial optimization

what is this

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"

Rock-paper-scissors gain table

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

Formulation

――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 $
-y + z \ge w
$ 4x - z \ge w$
$ -x + y \ge w$
x,y,z \ge 0, ~~~ w: free

Solve with Python

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

Solving game theory with combinatorial optimization
Solving 4-color problems with combinatorial optimization
Solving school district organization problems with combinatorial optimization
Solving the N Queen problem with combinatorial optimization
Solving the N Queens problem with combinatorial optimization
Grouping games with combinatorial optimization
Solving "cubes in cubes" by combinatorial optimization
Maximize restaurant sales with combinatorial optimization
Go see whales with combinatorial optimization
Pave the road with combinatorial optimization
Solving Knapsack Problems with Google's OR-Tools-Practicing the Basics of Combinatorial Optimization Problems
Let's stack books flat with combinatorial optimization
Use combinatorial optimization
Create an academic society program with combinatorial optimization
Road installation with optimization
Grouping by combinatorial optimization
Getting Started with Optimization
Solving Mathematical Optimization Model Exercises with Google's OR-Tools (3) Production Optimization Problems
Try function optimization with Optuna
Solving Sudoku with Python (Incomplete)
Combinatorial optimization to investigate stars
Programming education game with SenseHAT
Restore disjointed photos with optimization!
Solving Sudoku with Python (Part 2)
Simple typing game with DragonRuby
Adjust hyperparameters with Bayesian optimization
Solving the nurse scheduling problem (shift optimization) with a genetic algorithm