ECE 194V Game Theory and Multiagent Systems

Homework #4 Solutions

1. Dividing money: Two people have $10 to divide between themselves. They use the following
procedure. Each person names a number of dollars (a nonnegative integer), at most equal to
10. If the sum of the amounts that the people names is at most 10, then each person receives
the amount of money she named (and the remainder is destroyed). If the sum of the amounts
that the people name exceeds 10 and the amounts named are different, then the person who
named the smaller amount receives that amount and the other person receives the remaining
money. If the sum of the amounts that the people name exceeds 10 and the amounts named
are the same, then each person receives 5. Model this scenario as a strategic form game and
provide the payoff matrix.
This game has two payers N = {1, 2}, each with 11 actions:

A1 = A2 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.
The payoff matrix for this game is:

0 1 2 3 4 5 6 7 8 9 10
0 0, 0 0, 1 0, 2 0, 3 0, 4 0, 5 0, 6 0, 7 0, 8 0, 9 0, 10
1 1, 0 1, 1 1, 2 1, 3 1, 4 1, 5 2, 6 1, 7 1, 8 1, 9 1, 9
2 2, 0 2, 1 2, 2 2, 3 2, 4 2, 5 2, 6 2, 7 2, 8 2, 8 2, 8
3 3, 0 3, 1 3, 2 3, 3 3, 4 3, 5 3, 6 3, 7 3, 7 3, 7 3, 7
4 4, 0 4, 1 4, 2 4, 3 4, 4 4, 5 4, 6 4, 6 4, 6 4, 6 4, 6
5 5, 0 5, 1 5, 2 5, 3 5, 4 5, 5 5, 5 5, 5 5, 5 5, 5 5, 5
6 6, 0 6, 1 6, 2 6, 3 6, 4 5, 5 5, 5 6, 4 6, 4 6, 4 6, 4
7 7, 0 7, 1 7, 2 7, 3 6, 4 5, 5 4, 6 5, 5 7, 3 7, 3 7, 3
8 8, 0 8, 1 8, 2 7, 3 6, 4 5, 5 4, 6 3, 7 5, 5 8, 2 8, 2
9 9, 1 9, 1 8, 2 7, 3 6, 4 5, 5 4, 6 3, 7 2, 8 5, 5 9, 1
10 10, 0 9, 1 8, 2 7, 3 6, 4 5, 5 4, 6 3, 7 2, 8 1, 9 5, 5

2. Grad School Competition: Two students sign up to prepare an honors thesis with a
professor. Each can invest time in his own project: either no time, one week, or two weeks
(these are the only three options). The cost of time is 0 for no time, and each week costs 1
unit of payoff. The more time a student puts in the better his work will be, so that if one
student puts in more time than the other there will be a clear “leader.” If they put in the
same amount of time then their thesis projects will have the same quality. The professor,
however, will give out only one grade of A. If there is a clear leader, then he will get the A,
while if they are equally good then the professor will toss a fair coin to decide who gets the
A. The other student will get a B. Since both wish to continue on to graduate school, a grade
of A is worth 3 while a grade of B is worth 0. Model this scenario as a strategic form game
and provide the payoff matrix.
This game has two players (the two students) N = {1, 2}, each with 3 actions for the number
of weeks to work:
A1 = A2 = {0, 1, 2}.
In calculating the payoffs, note that if the students put in the same amount of work, they
receive and expected payoff of 1.5 minus the number of weeks they put in. The payoff matrix
for this game is:
 0 1 2
0 1.5,1.5 0,2 0,1
1 2,0 0.5,0.5 -1,1
2 1,0 1,-1 -0.5,-0.5

3. A zero-sum game has a payoff (for the row player) given by

 
1 3
4 2

(a) Compute the security strategies for both players using pure actions, and conclude that
the game does not have a value in this case.
(b) Repeat using mixed strategies, and compute the value of the game.

Pure strategies:

• For the row player, the worst case for top is 1 and for bottom is 2. Therefore,

a∗row = Bottom, v = 2

• For the column player, the worst case for left is 4 and for right is 3. Therefore,

a∗col = Right, v = 3

• Note that v < v, so the game has no value.

Mixed strategies:

• Assume the column player mixes according to (q, 1 − q) and the row player mixes ac-
cording to (p, 1 − p).
• For the row player, the plot below illustrates the consequences of mixing with p. The
horizontal axis is p. The vertical axis is payoff. The two lines correspond to column
player using left or right. The thick line represents the worst case as function of p. The
peak is the maximin.
4

3.5

2.5

1.5

1
0 0.2 0.4 0.6 0.8 1

Note that v = 2.5

• Likewise for the minimizing column player, the following is a plot of the worst case as a
function of q. The valley is the minimax.
 4

3.5

2.5

1.5

1
0 0.2 0.4 0.6 0.8 1

Note that v = 2.5

• The value of the game is 2.5. The security strategies are
p∗ = 1/2 & q ∗ = 1/4
4. A zero-sum game has a payoff (for the row player) given by
 
0 3 1
4 1 2
(a) Compute the security strategies for both players using pure actions, and conclude that
the game does not have a value in this case.
(b) Repeat using mixed strategies for the row player.
(c) Compute the value of the game.
Pure strategies:
• For the row player, the worst case for top is 0 and for bottom is 1. Therefore,
a∗row = Bottom, v = 1
• For the column player, the worst case for left is 4, center is 3 and for right is 2. Therefore,
a∗col = Right, v = 2
• Note that v < v, so the game has no value.
Mixed strategies:
• Assume the row player mixes according to (p, 1 − p).
• For the row player, the plot below illustrates the consequences of mixing with p. The
horizontal axis is p. The vertical axis is payoff. The three lines correspond to column
player using left, center, or right. The thick line represents the worst case as function of
p. The peak is the maximin.
 • The peak occurs at p∗ = 1/3 and the value of the game is 5/3.

5. Consider the following resource allocation problem known as a Colonel Blotto game

Colonel 1 Colonel 1

v1
<latexit sha1_base64="yvbwXYS+8s427c1T0pWQT/aFexQ=">AAAB6nicbZBNS8NAEIYn9avWr6pHL4tF8FQSEfRY9OKxov2ANpbNdtIu3WzC7qZQQn+CFw+KePUXefPfuG1z0NYXFh7emWFn3iARXBvX/XYKa+sbm1vF7dLO7t7+QfnwqKnjVDFssFjEqh1QjYJLbBhuBLYThTQKBLaC0e2s3hqj0jyWj2aSoB/RgeQhZ9RY62H85PXKFbfqzkVWwcuhArnqvfJXtx+zNEJpmKBadzw3MX5GleFM4LTUTTUmlI3oADsWJY1Q+9l81Sk5s06fhLGyTxoyd39PZDTSehIFtjOiZqiXazPzv1onNeG1n3GZpAYlW3wUpoKYmMzuJn2ukBkxsUCZ4nZXwoZUUWZsOiUbgrd88io0L6qe5fvLSu0mj6MIJ3AK5+DBFdTgDurQAAYDeIZXeHOE8+K8Ox+L1oKTzxzDHzmfPwchjZ0=</latexit>
v2
<latexit sha1_base64="FG2gWdgINTC3AsiSGTLmOtGSYIA=">AAAB6nicbZBNSwMxEIZn61etX1WPXoJF8FR2i6DHohePFW0ttGvJprNtaDa7JNlCWfoTvHhQxKu/yJv/xrTdg7a+EHh4Z4bMvEEiuDau++0U1tY3NreK26Wd3b39g/LhUUvHqWLYZLGIVTugGgWX2DTcCGwnCmkUCHwMRjez+uMYleaxfDCTBP2IDiQPOaPGWvfjp1qvXHGr7lxkFbwcKpCr0St/dfsxSyOUhgmqdcdzE+NnVBnOBE5L3VRjQtmIDrBjUdIItZ/NV52SM+v0SRgr+6Qhc/f3REYjrSdRYDsjaoZ6uTYz/6t1UhNe+RmXSWpQssVHYSqIicnsbtLnCpkREwuUKW53JWxIFWXGplOyIXjLJ69Cq1b1LN9dVOrXeRxFOIFTOAcPLqEOt9CAJjAYwDO8wpsjnBfn3flYtBacfOYY/sj5/AEIpY2e</latexit>
v1
<latexit sha1_base64="yvbwXYS+8s427c1T0pWQT/aFexQ=">AAAB6nicbZBNS8NAEIYn9avWr6pHL4tF8FQSEfRY9OKxov2ANpbNdtIu3WzC7qZQQn+CFw+KePUXefPfuG1z0NYXFh7emWFn3iARXBvX/XYKa+sbm1vF7dLO7t7+QfnwqKnjVDFssFjEqh1QjYJLbBhuBLYThTQKBLaC0e2s3hqj0jyWj2aSoB/RgeQhZ9RY62H85PXKFbfqzkVWwcuhArnqvfJXtx+zNEJpmKBadzw3MX5GleFM4LTUTTUmlI3oADsWJY1Q+9l81Sk5s06fhLGyTxoyd39PZDTSehIFtjOiZqiXazPzv1onNeG1n3GZpAYlW3wUpoKYmMzuJn2ukBkxsUCZ4nZXwoZUUWZsOiUbgrd88io0L6qe5fvLSu0mj6MIJ3AK5+DBFdTgDurQAAYDeIZXeHOE8+K8Ox+L1oKTzxzDHzmfPwchjZ0=</latexit>
v2
<latexit sha1_base64="FG2gWdgINTC3AsiSGTLmOtGSYIA=">AAAB6nicbZBNSwMxEIZn61etX1WPXoJF8FR2i6DHohePFW0ttGvJprNtaDa7JNlCWfoTvHhQxKu/yJv/xrTdg7a+EHh4Z4bMvEEiuDau++0U1tY3NreK26Wd3b39g/LhUUvHqWLYZLGIVTugGgWX2DTcCGwnCmkUCHwMRjez+uMYleaxfDCTBP2IDiQPOaPGWvfjp1qvXHGr7lxkFbwcKpCr0St/dfsxSyOUhgmqdcdzE+NnVBnOBE5L3VRjQtmIDrBjUdIItZ/NV52SM+v0SRgr+6Qhc/f3REYjrSdRYDsjaoZ6uTYz/6t1UhNe+RmXSWpQssVHYSqIicnsbtLnCpkREwuUKW53JWxIFWXGplOyIXjLJ69Cq1b1LN9dVOrXeRxFOIFTOAcPLqEOt9CAJjAYwDO8wpsjnBfn3flYtBacfOYY/sj5/AEIpY2e</latexit>

Colonel 2 Colonel 2-a Colonel 2-b

There are two Colonels, denoted by N = {1, 2}, and the number of assets (or soldiers) available
to each Colonel is B1 = 5 and B2 = 3. In this problem, each Colonel must simultaneously
decide how to allocate its assets over two distinct battlefields that have valuations v 1 ≥ 0 and
v 2 ≥ 0. A Colonel wins a battlefield when it allocates strictly more assets to that battlefield
than its opponent, and consequently the other Colonel loses. The payoff to a Colonel is the
total value of the battlefields it won minus the total value of the battlefields it lost (ties give
zero payoff to either side). For example, if Colonel 1 allocates 4 assets to battlefield 1 and 1
asset to battlefield 2, which we denote by x1 = (4, 1), and Colonel 2’s allocation is x2 = (1, 2),
the valuation to Colonel 1 is v 1 − v 2 and the valuation to Colonel 2 is v 2 − v 1 .

(a) What are the set of actions available to each Colonel?

(b) What is the payoff matrix of the Colonel Blotto game?
(c) Suppose v 1 = v 2 = 1. What are the security levels of each Colonel under pure strategies?
(d) Extra Credit: What are the security levels of each Colonel under mixed strategies?

As each colonel must split his forces of the two battlefields, the actions available to each are

A1 = {(0, 5), (1, 4), (2, 3), (3, 2), (4, 1), (5, 0)}, A2 = {(0, 3), (1, 2), (2, 1), (3, 0)}.

The payoff matrix for this game, where the row player is Colonel 1 and the column player is
Colonel 2, is

(0, 3) (1, 2) (2, 1) (3, 0)

(0, 5) v 2 , −v 2 −v 1 + v 2 , v 1 − v 2 −v 1 + v 2 , v 1 − v 2 −v 1 + v 2 , v 1 − v 2
(1, 4) v 1 + v 2 , −v 1 − v 2 v 2 , −v 2 −v 1 + v 2 , v 1 − v 2 −v 1 + v 2 , v 1 − v 2
(2, 3) v 1 , −v 1 v 1 + v 2 , −v 1 − v 2 v 2 , −v 2 −v 1 + v 2 , v 1 − v 2
(3, 2) v − v 2 , −v 1 + v 2
1 v 1 , −v 1 v + v 2 , −v 1 − v 2
1 v 2 , −v 2
(4, 1) v 1 − v 2 , −v 1 + v 2 v − v 2 , −v 1 + v 2
1 v 1 , −v 1 v + v 2 , −v 1 − v 2
1

(5, 0) v 1 − v 2 , −v 1 + v 2 v 1 − v 2 , −v 1 + v 2 v 1 − v 2 , −v 1 + v 2 v 1 , −v 1

In the case where v 1 = v 2 = 1, the payoff matrix when the row player is the maximizer will
be,
 (0, 3) (1, 2) (2, 1) (3, 0)
(0, 5) 1 0 0 0
(1, 4) 2 1 0 0
(2, 3) 1 2 1 0
(3, 2) 0 1 2 1
(4, 1) 0 0 1 2
(5, 0) 0 0 0 1

For Colonel 1, actions (0, 5) and (5, 0) are weakly dominated by actions (1, 4) and (4, 1)
respectively. Therefore, these actions will not have support in the security strategy for Colonel
1. After removing these actions, the security strategies for Colonel 1 can be determined by
solving for a mixed strategy which will give equal expected payoff for each opponent action,
and the same can be done for Colonel 2. These two strategies are

p = (1/3, 1/6, 1/6, 1/3),

over {(1, 4), (2, 3), (3, 2), (4, 1)} for Colonel 1 and over {(0, 3), (1, 2), (2, 1), (3, 0)} for Colonel
2. The value of the game is v = v = 5/6.