Mathematics 340 Homework 8 Due March 31st
• You will not be able to use a calculator or computer for either the midterm or the final exam, so please do not use one for this assignment. You may use one to check your answer, but please do not use one to solve the problem.
• Only part of the problems may be graded. But, you have to submit all the problems.
• Submit only pdf files.
1. Use the Jupyter notebook and PULP package to solve the following problem: [Vanderbei, Exercise 11.2] Players A and B each pick an integer number among the 100 numbers 1, 2, 3, · · · , 100. The game is a draw if both players pick the same number. Otherwise, the player who picks the smaller number wins unless that smaller number is one less than the opponents’ number, in which case the opponent wins. The winner wins $1 from the opponent. Find the optimal strategy of Player A for this game.
Your solution should be given in the following way:
(a) First, download your Jupyter notebook as a pdf file and submit the pdf file.
(b) Clearly write down the optimal strategy for Player A, with the optimal expected payoff.
(c) Clearly write down the optimal strategy for Player B.
Solution:
• Let 1 ≤ j, i ≤ 100 denote the choice of Player A and Player B. The payoff for Player A (the column player) is (in dollars) is given by the matrix P = (aij) given by
aij= −1
−1
1
0
ifi=j,
if i = j − 1 , ifi
1
This is a matrix whose diagonal entries are all zero, and the entries right above the diagonal are −1 and other entries above the diagonal are 1, and similarly the entries right below the diagonal are 1, and other entries below the diagonal are −1.
Page 1 of 7
Mathematics 340 Homework 8 Due March 31st
• Player A’s strategy is given by the probability xj , for choosing j, j = 1, …, 100. The optimization problem for Player A is given by the following LP:
maximise z = v
subjectto
v −100aijxj ≤ 0, i=1,…,100 j=1
100xj = 1 j=1
xj ≥ 0 j=1,…,100
• (a) See the Jupyter notebook file.
• (b) We found that the optimal strategy for Player A is x1 = 1/3, x2 = 1/3,x3 = 1/3 and xj = 0 for j = 4,…,100.
• (c) Note that for Player B, her problem is exactly the same as Player A because the rule of the game is symmetric with respect to both players. Therefore, the optimal strategy is y1 = 1/3, y2 = 1/3, y3 = 1/3 and yi = 0 for i = 4,…,100.
Page 2 of 7
Mathematics 340 Homework 8 Due March 31st
2.
[Hillier-Lieberman, 14.1-1] The labor union and management of a particular company have been negotiating a new labor contract. However, negotiations have now come to an impasse, with management making a “final” offer of a wage increase of $1.10 per hour and the union making a “final” demand of a $1.60 per hour increase. Therefore, both sides have agreed to let an impartial arbitrator set the wage increase somewhere between $1.10 and $1.60 per hour (inclusively). The arbitrator has asked each side to submit to her a confidential proposal for a fair and economically reasonable wage increase (rounded to the nearest dime). From past experience, both sides know that this arbitrator normally accepts the proposal of the side that gives the most from its final figure. If neither side changes its final figure, or if they both give in the same amount, then the arbitrator normally compromises halfway between ($1.35 in this case). Each side now needs to determine what wage increase to propose for its own maximum advantage.
(a) Formulate this problem as a two-person, zero-sum game.
(b) If the union knows what management will submit, what is their best strategy for each choice?
(c) Is there a pure strategy Nash equilibrium for this problem?
Solution:
(a) Each player has 6 choices, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6. We let the union choose the column to maximize the wage increase and the management choose the row. We can express the payoff matrix by
1.1
1.1
1.2 1.3 1.4 1.5 1.35 1.2 1.3 1.4 1.35 1.2 1.2 1.3 1.35 1.3 1.3
1.1
A=1.1 1.2 1.35 1.4 1.4 1.4. 1.1 1.35 1.5 1.5 1.5 1.5
1.35 1.6 1.6 1.6 1.6 1.6
The rows could also be ordered descending corresponding to the manager giving
in 0, .10, .20, etc.
(b) For each of the rows the maximum column value is
1.5 1.4
1.35 . 1.4
1.5 1.6
Page 3 of 7
Mathematics 340 Homework 8 Due March 31st
(c) If the management submits 1.3 it is best for the union to submit 1.4, yielding a 1.35 wage increase. This is the Nash equilibrium, as when the union submits 1.4 it is still best for the management to submit 1.3.
Page 4 of 7
Mathematics 340 Homework 8 Due March 31st
3. (Vanderbei, Exercise 11.3 points) We say that row r dominates row s if arj ≥ asj for all j = 1, 2, …, n. Similarly, column r is said to dominate column s if air ≥ ais for all i = 1, 2, …, m. Show that
(a) If a row (say, r) dominates another row, then the row player has an optimal strategy y∗ in which yr∗ = 0.
(b) If a column (say, s) is dominated by another column, then the column player has an optimal strategy x∗ in which x∗s = 0.
(c) Use these results to reduce the following payoff matrix to a 2 by 2 matrix:
−6 2 −4 −7 −5 0 4 −2 −9 −1 −7 3 −3 −8 −2 2 −3 6 0 3
Solution:
(a) Suppose that row r dominates row s. There is always an optimal strategy. This follows from the linear programming formulation and that there is a feasible solution for both the LP and it’s dual. Let us call the optimal strategy ⃗y. We define⃗y∗ byyr∗ =0,ys∗ =yr +ys,andyi∗ =yi fori∈{1,…,m}withi̸=r,s. Then ⃗y∗ ∈ ∆m since it is nonnegtive and the entries sum to the same as ⃗y, which is one. For any ⃗x ∈ ∆n,
n
⃗y ∗ · A ⃗x = ⃗y · A ⃗x + y A − A x . r sj rj j
j=1
SinceAsj ≤Arj andyr ≥0andxj ≥0foreachj,wehave
⃗y∗ ·A⃗x≤⃗y·A⃗x. Thus ⃗y∗ is an optimal solution with yr∗ = 0.
(b) Suppose that column r dominates column s. Similar to above, let ⃗x be optimal andwedefine⃗x∗ byx∗s =0,x∗r =xr+xs,andx∗j =xj forj∈{1,…,n}with j ̸= r, s. Then ⃗x∗ ∈ ∆n since it is nonnegtive and the entries sum to the same as ⃗x, which is one. For any ⃗y ∈ ∆m,
m
⃗y·A⃗x∗ =⃗y·A⃗x+yA −A x. i ir is s
i=1
SinceAir ≥Ais andyi ≥0foreachiandxs ≥0,wehave
⃗y·A⃗x∗ ≥⃗y·A⃗x.
Thus ⃗x∗ is an optimal solution with x∗s = 0. player has an optimal strategy x∗ in which x∗s = 0.
Page 5 of 7
Mathematics 340 Homework 8 Due March 31st
(c) We can first eliminate column 4, which is dominated by column 3:
−6 2 −4 −5 0 4 −2 −1. −7 3 −3 −2
2 −3 6 3 We can elimate row 2, which dominates row 1:
−6 2 −4 −5 −7 3 −3 −2.
2 −3 6 3
We can elimate column 1, which is dominated by column 4 above:
2 −4 −5 3 −3 −2.
−3 6 3
We can elimninate row 2, which dominates row 1:
2 −4 −5 −3 6 3 .
Finally, we can eliminate column 3, which is dominated by column 2:
2 −4 −3 6
4. LetA=(aij)beanm×npayoffmatrixofatwopersonzerosumgame.
a) Assume that the average entry in row i of A is at least 5 for each i = 1,2,…,m. Show that the assured (expected) winnings for the column player (player 1) is at least 5.
Solution:
• Assume that the average entry in column i of A is at least 5 for each i = 1,2,…,m.
• If we consider the (mixed) strategy for player 1 ⃗x = (1/n, 1/n, . . . , 1/n), then each i’s entry of A⃗x is
nn aijxj = 1/naij
j=1 j=1
Page 6 of 7
Mathematics 340 Homework 8 Due March 31st
but, note that 1/n nj=1 aij is exactly the average entry of the i’th row of A so itis≥5. Forany⃗y∈∆m,itmustbethat
mnm
⃗y · A ⃗x = y a x ≥ 5 y = 5 . iijj i
i=1 j=1 i=1
b) (This question is independent of (a).) Find an example such that the average entry in column j of A is at least 5 for each j = 1,2,..,n and yet the game is fair.
Solution:
• A simple example is
10 10 A=00
where the average entry of each column is 5. As the entries of A are all nonnegative, the payoff for the column player is always ≥ 0. On the other hand, the row player can always choose the second row, ⃗y = (0, 1), to gaurantee that the game value is no more than 0. Therefore, this is a fair game.
Page 7 of 7