Sách Game theory - Stat 155, Yuval Peres Fall 2004 -

Game theory - Stat 155, Yuval Peres Fall 2004 -

1 Introduction 2
2 Combinatorial games 7
2.1 Some de¯nitions . 7
2.2 The game of nim, and Bouton's solution 10
2.3 The sum of combinatorial games 14
2.4 Staircase nim and other examples 18
2.5 The game of Green Hackenbush . 20
2.6 Wytho®'s nim 21
3 Two-person zero-sum games 23
3.1 Some examples 23
3.2 The technique of domination 25
3.3 The use of symmetry . 27
3.4 von Neumann's minimax theorem 28
3.5 Resistor networks and troll games 31
3.6 Hide-and-seek games . 33
3.7 General hide-and-seek games 34
3.8 The bomber and submarine game 37
3.9 A further example 38
4 General sum games 39
4.1 Some examples 39
4.2 Nash equilibrium . 40
4.3 General sum games with k ¸ 2 players . 44
4.4 The proof of Nash's theorem 45
4.4.1 Some more ¯xed point theorems 47
4.4.2 Sperner's lemma . 49
4.4.3 Proof of Brouwer's ¯xed point theorem 51
4.5 Some further examples 51
4.6 Potential games 52
1
Game theory 2
5 Coalitions and Shapley value 55
5.1 The Shapley value and the glove market 55
5.2 Probabilistic interpretation of Shapley value 57
5.3 Two more examples . 59
6 Mechanism design 61






1 Introduction
In this course on game theory, we will be studying a range of mathematical
models of con°ict and cooperation between two or more agents. The course
will attempt an overview of a broad range of models that are studied in
game theory, and that have found application in, for example, economics
and evolutionary biology. In this Introduction, we outline the content of
this course, often giving examples.
One class of games that we begin studying are combinatorial games.
An example of a combinatorial game is that of hex, which is played on an
hexagonal grid shaped as a rhombus: think of a large rhombus-shaped region
that is tiled by a grid of small hexagons. Two players, R and G, alternately
color in hexagons of their choice either red or green, the red player aiming
to produce a red crossing from left to right in the rhombus and the green
player aiming to form a green one from top to bottom. As we will see, the
¯rst player has a winning strategy; however, ¯nding this strategy remains
an unsolved problem, except when the size of the board is small (9 £ 9, at
most). An interesting variant of the game is that in which, instead of taking
turns to play, a coin is tossed at each turn, so that each player plays the
next turn with probability one half. In this variant, the optimal strategy for
either player is known.
A second example which is simpler to analyse is the game of nim. There
are two players, and several piles of sticks at the start of the game. The
players take turns, and at each turn, must remove at least one stick from
one pile. The player can remove any number of sticks that he pleases, but
these must be drawn from a single pile. The aim of the game is to force
the opponent to take the last stick remaining in the game. We will ¯nd the
solution to nim: it is not one of the harder examples.


The costs incurred to the drivers depend on whether they travel the
roads alone or together with the other driver (not necessarily at the very
same time). The vectors (a; b) attached to each road mean that the cost
paid by either driver for the use of the road is a if he travels the road alone,
and b if he shares its use with the other driver. For example, if I and II
use the road AB | which means that I chooses the route via A and II
chooses that via B | then each pays 5 units for doing so, whereas if only
one of them uses that road, the cost is 3 units to that driver. We write a
cost matrix to describe the game:
II B D
I
A (6,8) (5,4)
C (6,7) (7,5)
The vector notation (¢; ¢) denotes the costs to players I and II of their
joint choice.
A fourth example is that of penalty kicks, in which there are two
participants, the penalty-taker and the goalkeeper. The notion of left and
right will be from the perspective of the goalkeeper, not the penalty-taker.
The penalty-taker chooses to hit the ball either to the left or the right, and
the goalkeeper dives in one of these directions. We display the probabilities
that the penalty is scored in the following table:
GK L R
PT
L 0.8 1
R 1 0.5
That is, if the goalie makes the wrong choice, he has no chance of saving
the goal. The penalty-taker has a strong `left' foot, and has a better chance
if he plays left. The goalkeeper aims to minimize the probability of the
penalty being scored, and the penalty-taker aims to maximize it. We could
write a payo® matrix for the game, as we did in the previous example, but,
since it is zero-sum, with the interests of the players being diametrically
opposed, doing so is redundant. We will determine the optimal strategy for
the players for a class of games that include this one. This strategy will
often turn out to be a randomized choice among the available options.
Such two person zero-sum games have been applied in a lot of contexts:
in sports, like this example, in military contexts, in economic applications,
and in evolutionary biology. These games have a quite complete
theory, so that it has been tempting to try to apply them. However, real
life is often more complicated, with the possibility of cooperation between
players to realize a mutual advantage. The theory of games that model such
an e®ect is much less complete.
The mathematics associated to zero-sum games is that of convex geometry.
A convex set is one where, for any two points in the set, the straight
line segment connecting the two points is itself contained in the set.
The relevant geometric fact for this aspect of game theory is that, given
any closed convex set in the plane and a point lying outside of it, we can
¯nd a line that separates the set from the point. There is an analogous
statement in higher dimensions. von Neumann exploited this fact to solve
zero sum games using a minimax variational principle. We will prove this
result.
In general-sum games, we do not have a pair of optimal strategies any
more, but a concept related to the von Neumann minimax is that of Nash
equilibrium: is there a `rational' choice for the two players, and if so, what
could it be? The meaning of `rational' here and in many contexts is a valid
subject for discussion. There are anyway often many Nash equilibria and
further criteria are required to pick out relevant ones.
A development of the last twenty years that we will discuss is the application
of game theory to evolutionary biology. In economic applications,
it is often assumed that the agents are acting `rationally', and a neat theorem
should not distract us from remembering that this can be a hazardous
assumption. In some biological applications, we can however see Nash equilibria
arising as stable points of evolutionary systems composed of agents
who are `just doing their own thing', without needing to be `rational'.
Let us introduce another geometrical tool. Although from its statement,
it is not evident what the connection of this result to game theory might be,
we will see that the theorem is of central importance in proving the existence
of Nash equilibria.
Theorem 1 (Brouwer's ¯xed point theorem) : If K µ Rd is closed,
bounded and convex, and T : K ! K is continuous, then T has a ¯xed
point. That is, there exists x 2 K for which T(x) = x.
The assumption of convexity can be weakened, but not discarded entirely.
To see this, consider the example of the annulus C = fx 2 R2 : 1 · jxj · 2g,
and the mapping T : C ! C that sends each point to its rotation by
90 degrees anticlockwise about the origin. Then T is isometric, that is,
jT(x) ¡ T(y)j = jx ¡ yj for each pair of points x; y 2 C. Certainly then, T
is continuous, but it has no ¯xed point.
Game theory 5
Another interesting topic is that of signalling. If one player has some
information that another does not, that may be to his advantage. But if he
plays di®erently, might he give away what he knows, thereby removing this
advantage?
A quick mention of other topics, related to mechanism design. Firstly,
voting. Arrow's impossibility theorem states roughly that if there is an
election with more than two candidates, then no matter which system one
chooses to use for voting, there is trouble ahead: at least one desirable
property that we might wish for the election will be violated. A recent topic
is that of eliciting truth. In an ordinary auction, there is a temptation to
underbid. For example, if a bidder values an item at 100 dollars, then he has
no motive to bid any more or even that much, because by exchanging 100
dollars for the object at stake, he has gained an item only of the same value
to him as his money. The second-price auction is an attempt to overcome
this °aw: in this scheme, the lot goes to the highest bidder, but at the
price o®ered by the second-highest bidder. This problem and its solutions
are relevant to bandwidth auctions made by governments to cellular phone
companies.
Example: Pie cutting. As another example, consider the problem of a
pie, di®erent parts of whose interior are composed of di®erent ingredients.
The game has two or more players, who each have their own preferences
regarding which parts of the pie they would most like to have. If there are
just two players, there is a well-known method for dividing the pie: one splits
it into two halves, and the other chooses which he would like. Each obtains
at least one-half of the pie, as measured according to each own preferences.
But what if there are three or more players? We will study this question,
and a variant where we also require that the pie be cut in such a way that
each player judges that he gets at least as much as anyone else, according
to his own criterion.
Example: Secret sharing. Suppose that we plan to give a secret to two
people. We do not trust either of them entirely, but want the secret to
be known to each of them provided that they co-operate. If we look for a
physical solution to this problem, we might just put the secret in a room,
put two locks on the door, and give each of the players the key to one of
the locks. In a computing context, we might take a password and split it in
two, giving each half to one of the players. However, this would force the
length of the password to be high, if one or other half is not to be guessed
by repeated tries. A more ambitious goal is to split the secret in two in such
a way that neither person has any useful information on his own. And here
is how to do it: suppose that the secret s is an integer that lies between 0
and some large value M, for example, M = 106. We who hold the secret
at the start produce a random integer x, whose distribution is uniform on
the interval f0; : : : ;M ¡ 1g (uniform means that each of the M possible
outcomes is equally likely, having probability 1=M). We tell the number x
to the ¯rst person, and the number y = (s¡x) mod M to the second person
(mod M means adding the right multiple of M so that the value lies on the
interval f0; : : : ;M ¡ 1g). The ¯rst person has no useful information. What
about the second? Note that
P(y = j) = P((s ¡ x) modM = j) = 1=M;
where the last equality holds because (s ¡ x) mod M equals y if and only
if the uniform random variable x happens to hit one particular value on
f0; : : : ;M ¡ 1g. So the second person himself only has a uniform random
variable, and, thus, no useful information. Together, however, the players
can add the values they have been given, reduce the answer mod M, and
get the secret s back. A variant of this scheme can work with any number
of players. We can have ten of them, and arrange a way that any nine of
them have no useful information even if they pool their resources, but the
ten together can unlock the secret.
Example: Cooperative games. These games deal with the formation of
coalitions, and their mathematical solution involves the notion of Shapley
value. As an example, suppose that three people, I,II and III, sit in
a store, the ¯rst two bearing a left-handed glove, while the third has a
right-handed one. A wealthy tourist, ignorant of the bitter local climatic
conditions, enters the store in dire need of a pair of gloves. She refuses to
deal with the glove-bearers individually, so that it becomes their job to form
coalitions to make a sale of a left and right-handed glove to her. The third
player has an advantage, because his commodity is in scarcer supply. This
means that he should be able to obtain a higher fraction of the payment that
the tourist makes than either of the other players. However, if he holds out
for too high a fraction of the earnings, the other players may agree between
them to refuse to deal with him at all, blocking any sale, and thereby risking
his earnings. We will prove results in terms of the concept of the Shapley
value that provide a solution to this type of problem.