Peres Y., Game Theory Instructor Lctn.pdf

Stat 155, Yuval Peres

Fall 2004

Game theory

Contents

1 Introduction

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

Game theory

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

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.

Another class of games are congestion games. Imagine two drivers, I

and II, who aim to travel from cities B to D, and from A to C, respectively:

Game theory

(1,2)

(3,5)

(2,4)

(3,4)

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

(6,8) (5,4)

(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

0.8 1

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.

Game theory

Such two person zero-sum games have been applied in a lot of con-

texts: in sports, like this example, in military contexts, in economic appli-

cations, 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 geom-

etry. 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 ap-

plication of game theory to evolutionary biology. In economic applications,

it is often assumed that the agents are acting `rationally', and a neat theo-

rem should not distract us from remembering that this can be a hazardous

assumption. In some biological applications, we can however see Nash equi-

libria 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.

R d is closed,

bounded and convex, and T : K!K is continuous, then T has a ¯xed

point. That is, there exists x2K for which T(x) = x.

R 2 : 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¡yjfor each pair of points x;y2C. Certainly then, T

is continuous, but it has no ¯xed point.

Theorem 1 (Brouwer's ¯xed point theorem) : If Kµ

The assumption of convexity can be weakened, but not discarded entirely.

To see this, consider the example of the annulus C =fx2

Game theory

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 = 10 6 . We who hold the secret

at the start produce a random integer x, whose distribution is uniform on

the intervalf0;:::;M¡1g(uniform means that each of the M possible

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: