Please enable JavaScript.
Coggle requires JavaScript to display documents.
Linear programming and game theory 1 (Zero-sum games (Strategy (2 Check…
Linear programming and game theory 1
Constrained optimisation
To translate the problem into mathematical terms, you first produce a linear programming formulation
Identify the quantities you can vary. THese are the decision variables (or control variables)
Identify the limitations on the values of the decision variables. These are the constraints
Identify the quantity to be optimised. This is the objective function
Standard linear programming solution format:
Maximise or minimise x + y
Subject to x ≤ n1
y ≤ n2
ax + by ≤ n3
x ≥ 0, y ≥ 0
The feasible region is the set of (x, y) values that satisfy all of the constraints. It is the unshaded region on the graph
The objective line is a line joining all points (x, y) for which the objective function takes a specific value
Strategy
3 Identify the objective function
4 If the problem has two variables, solve graphically
2 Express the constraints as inequalities
5 Answer the questions
1 Identify the decision variables and label them x, y, z...
Zero-sum games
In a zero-sum game, the sum of the gains made by the players on each play is zero
A play-safe strategy gives the best guarenteed outcome regardless of what the other player does
A game has a stable solution if neither player can gain by changing from their play-safe strategy
The value of a game is the payoff to the row player if both players use their best strategy
A game has a stable solution if maximum of row minima = minimum of column maxima
In a payoff matrix, row i dominates row j if, for every column, the value in row i ≥ value in row j
Similarly, column i dominates column j if, for every row, the value in column i ≤ value in column j
Strategy
2 Check whether the matrix can be reduced by using dominance
3 Find the maximum of the row minima and the minimum of the row maxima to determine each player's play-safe strategy
1 If necessary, construct the matrix of payoffs for the row player
4 Decide whethere the game has a stable solution and, if so, find its value
5 Answer the question in context
Mixed-strategy games
If payoffs x1, x2, ..., xn occur with probabilities p1, p2, ...pn, the expectation or expected payoff E(x) is given by
E(x) = x1p1 + x2p2 + ... + xnpn = Σxipi
Mixed-strategy games can be solved graphically in most cases with linear programming
B's payoffs are the negative of A's payoffs
Optimal strategies occur where the expected payouts of playing each row with probability p are equal
B1:
A1B1P+(1-P)A2B1
B2:
A1B2P+(1-P)A2B2
B1 strategy = A2 strategy
Solve for P
Substitute P back into one of the previous equations to get your optimalexpected payoff
Value for A, v = -Value for B, -v
Strategy
1 If necessary, construct a payoff matrix
2 Use dominance to reduce the matrix as much as possible
3 Find the play-safe strategies and decide whether the game has a stable solution
4 For mixed-strategies and decide whether the game has a stable solution
5 Solve the resulting linear programming problem to find the optimal strategies and the value of the game