11

Question 1

Duality theorem

Answer 1

Max {c^Tx : Ax ≤ b, x ≥ 0} = Min {b^Ty : A^Ty ≥ c, y ≥ 0}

Question 2

Standard principle and dual problems

Answer 2

• standard principle: Max. c^Tx subject to Ax≤b, x≥0
• dual problem: Min. b^Ty subject to A^Ty≥c, y≥0

Question 3

The value of a game is

Answer 3

The pay-off K(x^*,y^*) of the optimal strategies is known as the value of the game.

Question 4

Payoff to player 1 when he plays p and player 2 plays q

and the payoff to player 2

Answer 4

K(p,q) = p^TAq = ΣΣa_ijp_iq_j

(first Σ from i=1 to m, second Σ from j=1 to n)

Payoff to player 2 is the negative of this in zero sum games

Question 5

Steps to find value and mixed strategies of matrix game with payoff matrix

Answer 5

1. Sketch line segment U and Region K( λ*) = {x: x ≥ λ*e}
2. The set U = {A^Tp : p ≥ 0, e^Tp=1} shown in the diagramme above is the convex hull of the rows of A, i.e. the line segment between coordinate one and coordinate two (row i = coordinate i). The maximum value of λ for which K(λ) intersects U is the value of the game, λ*. This will be at the corner (λ*,λ*) of K(λ*). We therefore need to find the value of λ such that (λ,λ) just touches line U.
3. The equation of this line is y=mx+c so we should have have λ*=mλ*+c, thus λ*= Z. The value of the game is Z.
4. We can solve the equations A^Tp*=λ*e and Aq*=μ*e = λ*e (since the optimal values are the same) to find the mixed strategies, p* and q*.
5. Solve equations
6. These results tell us that Player 1 should play row 1 with a probability of p₁ and row 2 with probability p₂, and that Player 2 should play column 1 with a probability of q₁ and column 2 with probability q₂.

Question 7

Steps to find value and optimal strategies of the matrix game with pay-off matrix when one row clearly dominates.

Answer 7

1. As row Z dominates, Player 1 has pure strategy (0 0 Z)^T. Wanting to minimise Player 1’s pay-off, Player 2 has pure strategy (0 Y 0). The value of the game is thus a_ZY.

Question 8

If A is an n x n matrix, then the following statements are equivalent

Answer 8

A^-1 exists.
Ax = b has a unique solution for any b ∈ Rⁿ.
Ax = 0 has only the trivial solution, x = 0.
The reduced echelon form of A is I.
IAI ≠ 0.

The rank of A is n.

Question 9

Inverse using determinants: If IAI ≠ 0, then A^-1 =

Answer 9

If IAI ≠ 0, then A^-1 = (1/IAI) adj(A), where adj(A) is
the transpose of the matrix of cofactors, and is known as the adjoint matrix of A or
the adjugate matrix of A

You can also find the matrix by setting up (A I I) and using row operations such that (I I A^-1)

Question 10

Cramer’s rule

Answer 10

(valid whenever the system has a unique solution)

Question 11

The general solution of Ax = b is the sum of:

Answer 11

• a particular solution v of the system Ax = b and
• a linear combination s₁u₁ + s₂u₂ + … + s_n-ru_n-r of solutions u₁, u₂, …, u_n-r of the system Ax = 0.

Question 12

Finding value and optimal mixed strategies of zero-sum game - SIMPLIFIED

Answer 12

1. Write out equation y = mx + c, substitute λ* for x and y.
2. Write out two y = mx + c equations, one substituting row one for the x and y values, the other row two for the x and y values. Solve simultaneously to find m and c values.
3. Use this result to find λ*. This is the value of the game.
4. Solve A^Tp* = λ*e to find p*

and Aq* = λ*e to find q*

5. Player 1 plays row one with probability first two of p* and row two with probability second row of p*. Player 2 should play column 1 with probabality…