SOLUTIONS MANUAL
** All Chapters included
,Table of Contents are given below
1 - The game of chess
2 - Utility theory
3 - Extensive-form games
4 - Strategic-form games
5 - Mixed strategies
6 - Behavior strategies and Kuhn’s Theorem
7 - Equilibrium refinements
8 - Correlated equilibria
9 - Games with incomplete information and common priors
10 - Games with incomplete information: the general model
11 - The universal belief space
12 - Auctions
13 - Repeated games
14 - Repeated games with vector payoffs
15 - Stochastic games
16 - Bargaining games
17 - Coalitional games with transferable utility
18 - The core
19 - The Shapley value
20 - The bargaining set
21 - The nucleolus
22 - Social choice
23 - Stable matching
24 - Appendices
,“Game Theory” by Maschler, Solan and Zamir
Solution Manual
Chapter 1: The game of chess
1.1 No. The statement in the exercise holds for games without chance
moves, but also for games with chance moves, like backgammon.
The statement in Theorem 1.4, on the other hand, does not hold in
backgammon; in this game, if a player is extremely lucky, he can win
regardless of the strategy of the other player. In particular, the two
statements cannot be equivalent.
1.2 Tic-Tac-Toe, Four in a row, Nim.
1.3 (a) Denote by N the number of game positions in chess. If after N 2
turns neither White wins nor Black wins, then there is at least one
game position that is repeated twice so the play ends with draw.
Hence, the conditions of Theorem 1.5 are satisfied and (a) holds.
(b) Assume that one of the players has a winning strategy in finite
chess. Then he can guarantee by following this strategy that finite
chess ends with his winning- before it reaches a repeated game
position. Therefore, a strategy in which he follows his winning
strategy as long as no game position is repeated, otherwise he
chooses an arbitrary legal action is a winning strategy in chess.
Indeed, by following this strategy in chess the game ends before
it reaches a repeated game position as if it is finite chess, thus it
leads to his winning.
(c) Assume that each player has a strategy guaranteeing at least a
draw in finite chess. We show that each player has a strategy
guaranteeing at least a draw in chess. We show it for White, the
proof for Black is similar and thus it is omitted.
Denote by σW a strategy of White in finite chess that guarantees
at least a draw. Consider the following strategy b σW for White in
chess: implement the strategy σW until either the play of chess
terminates or a game position repeats itself (at which point, the
play of finite chess terminates). If the play of chess arrives to
a game position x that has previously appeared, implement the
strategy σW restricted to the subgame beginning at x until the
play arrives at a game position y that has previously appeared,
and so on.
We prove that the strategy bσW guarantees at least a draw in chess.
Assume by contradiction that b σW does not guarantee at least a
1
, draw. Let b σB be a strategy of Black that wins the game against
White playing b σW with minimal number of moves. Since σW
guarantees at least a draw in finite chess, when the player fol-
low (b σB ), White faces at least one game position, say x, that
σW , b
appears at least twice before the winning of Black. According to
σW , White selects the same move in x. Therefore, from the first
b
repetition of x onward, Black could follow the moves he takes af-
ter the second repetition of x and win the game using less moves,
which contradicts b σB wins with minimal number of moves.
Chapter 2: Utility theory
2.1 (a) Let be a strict preference.
is anti symmetric: if x y then y 6% x , therefore y 6 x.
In addition, is transitive: if x y and y z then x % y and
y % z. Hence, by the transitivity of % , one has x % z. It is left
to prove that z 6% x. Assume to the contrary that z % x, so by the
transitivity of %, one has z % y , a contradiction. In conclusion,
z 6% x and therefore x z.
(b) Let ≈ be an indifference relation.
Then ≈ is symmetric: if x ≈ y then x % y and y % x, therefore
y ≈ x.
In addition, ≈ is transitive: if x ≈ y and y ≈ z then x % y and
y % x, likewise y % z and z % y. Hence, by the transitivity of %,
one has x % z and z % x, so x ≈ z.
2.2 Let O be a set of outcomes. Let % be a complete, reflexive, and tran-
sitive relation over O. Assume that u is a utility function represent-
ing %. We prove that for every monotonically increasing function
v : R → R, the composition v ◦ u is also a utility function repre-
senting %. Indeed, let x, y ∈ O. Then, since u represents %, x % y if
and only if u (x ) ≥ u y . But the last inequality holds if and only if
v u ( x ) ≥ v u y , since v is a monotonically increasing function.
In particular, v ◦ u is also a utility function representing %, as needed.
2.3 Let O = Q , the set of the rational numbers. Define a relation over O
as follows. For every p, q ∈ O, p % q if and only if p ≥ q. We show that
there is no utility function representing % that includes only integer
values. Assume to the contrary that there is such a utility function.
Then 0, 1 ∈ O and u (0) < u (1) two integer values. But, there is an
increasing countable series of rational numbers in (0, 1), p1 < p2 < ....
2
** All Chapters included
,Table of Contents are given below
1 - The game of chess
2 - Utility theory
3 - Extensive-form games
4 - Strategic-form games
5 - Mixed strategies
6 - Behavior strategies and Kuhn’s Theorem
7 - Equilibrium refinements
8 - Correlated equilibria
9 - Games with incomplete information and common priors
10 - Games with incomplete information: the general model
11 - The universal belief space
12 - Auctions
13 - Repeated games
14 - Repeated games with vector payoffs
15 - Stochastic games
16 - Bargaining games
17 - Coalitional games with transferable utility
18 - The core
19 - The Shapley value
20 - The bargaining set
21 - The nucleolus
22 - Social choice
23 - Stable matching
24 - Appendices
,“Game Theory” by Maschler, Solan and Zamir
Solution Manual
Chapter 1: The game of chess
1.1 No. The statement in the exercise holds for games without chance
moves, but also for games with chance moves, like backgammon.
The statement in Theorem 1.4, on the other hand, does not hold in
backgammon; in this game, if a player is extremely lucky, he can win
regardless of the strategy of the other player. In particular, the two
statements cannot be equivalent.
1.2 Tic-Tac-Toe, Four in a row, Nim.
1.3 (a) Denote by N the number of game positions in chess. If after N 2
turns neither White wins nor Black wins, then there is at least one
game position that is repeated twice so the play ends with draw.
Hence, the conditions of Theorem 1.5 are satisfied and (a) holds.
(b) Assume that one of the players has a winning strategy in finite
chess. Then he can guarantee by following this strategy that finite
chess ends with his winning- before it reaches a repeated game
position. Therefore, a strategy in which he follows his winning
strategy as long as no game position is repeated, otherwise he
chooses an arbitrary legal action is a winning strategy in chess.
Indeed, by following this strategy in chess the game ends before
it reaches a repeated game position as if it is finite chess, thus it
leads to his winning.
(c) Assume that each player has a strategy guaranteeing at least a
draw in finite chess. We show that each player has a strategy
guaranteeing at least a draw in chess. We show it for White, the
proof for Black is similar and thus it is omitted.
Denote by σW a strategy of White in finite chess that guarantees
at least a draw. Consider the following strategy b σW for White in
chess: implement the strategy σW until either the play of chess
terminates or a game position repeats itself (at which point, the
play of finite chess terminates). If the play of chess arrives to
a game position x that has previously appeared, implement the
strategy σW restricted to the subgame beginning at x until the
play arrives at a game position y that has previously appeared,
and so on.
We prove that the strategy bσW guarantees at least a draw in chess.
Assume by contradiction that b σW does not guarantee at least a
1
, draw. Let b σB be a strategy of Black that wins the game against
White playing b σW with minimal number of moves. Since σW
guarantees at least a draw in finite chess, when the player fol-
low (b σB ), White faces at least one game position, say x, that
σW , b
appears at least twice before the winning of Black. According to
σW , White selects the same move in x. Therefore, from the first
b
repetition of x onward, Black could follow the moves he takes af-
ter the second repetition of x and win the game using less moves,
which contradicts b σB wins with minimal number of moves.
Chapter 2: Utility theory
2.1 (a) Let be a strict preference.
is anti symmetric: if x y then y 6% x , therefore y 6 x.
In addition, is transitive: if x y and y z then x % y and
y % z. Hence, by the transitivity of % , one has x % z. It is left
to prove that z 6% x. Assume to the contrary that z % x, so by the
transitivity of %, one has z % y , a contradiction. In conclusion,
z 6% x and therefore x z.
(b) Let ≈ be an indifference relation.
Then ≈ is symmetric: if x ≈ y then x % y and y % x, therefore
y ≈ x.
In addition, ≈ is transitive: if x ≈ y and y ≈ z then x % y and
y % x, likewise y % z and z % y. Hence, by the transitivity of %,
one has x % z and z % x, so x ≈ z.
2.2 Let O be a set of outcomes. Let % be a complete, reflexive, and tran-
sitive relation over O. Assume that u is a utility function represent-
ing %. We prove that for every monotonically increasing function
v : R → R, the composition v ◦ u is also a utility function repre-
senting %. Indeed, let x, y ∈ O. Then, since u represents %, x % y if
and only if u (x ) ≥ u y . But the last inequality holds if and only if
v u ( x ) ≥ v u y , since v is a monotonically increasing function.
In particular, v ◦ u is also a utility function representing %, as needed.
2.3 Let O = Q , the set of the rational numbers. Define a relation over O
as follows. For every p, q ∈ O, p % q if and only if p ≥ q. We show that
there is no utility function representing % that includes only integer
values. Assume to the contrary that there is such a utility function.
Then 0, 1 ∈ O and u (0) < u (1) two integer values. But, there is an
increasing countable series of rational numbers in (0, 1), p1 < p2 < ....
2
