Yildiz M., Game Theory Lecture Notes Introduction.pdf

14.12 Game Theory Lecture Notes

Introduction

Muhamet Yildiz

(Lecture 1)

Game Theory is a misnomer for Multiperson Decision Theory, analyzing the decision-

making process when there are more than one decision-makers where each agent’s payoﬀ

possibly depends on the actions taken by the other agents. Since an agent’s preferences

on his actions depend on which actions the other parties take, his action depends on his

beliefs about what the others do. Of course, what the others do depends on their beliefs

about what each agent does. In this way, a player’s action, in principle, depends on the

actions available to each agent, each agent’s preferences on the outcomes, each player’s

beliefs about which actions are available to each player and how each player ranks the

outcomes, and further his beliefs about each player’s beliefs, ad in ﬁ nitum.

Under perfect competition, there are also more than one (in fact, in ﬁ nitely many)

decision makers. Yet, their decisions are assumed to be decentralized. A consumer tries

to choose the best consumption bundle that he can aﬀord, given the prices — without

paying attention what the other consumers do. In reality, the future prices are not

known. Consumers’ decisions depend on their expectations about the future prices. And

the future prices depend on consumers’ decisions today. Once again, even in perfectly

competitive environments, a consumer’s decisions are aﬀected by their beliefs about

what other consumers do — in an aggregate level.

When agents think through what the other players will do, taking what the other

players think about them into account, they may ﬁ ndaclearwaytoplaythegame.

Consider the following “game”:

\ 2 L m R

T (1,1) (0,2) (2,1)

M (2,2) (1,1) (0,0)

B (1,0) (0,0) ( − 1,1)

Here, Players 1 has strategies, T, M, B and Player 2 has strategies L, m, R. (They

pick their strategies simultaneously.) The payoﬀs for players 1 and 2 are indicated by

the numbers in parentheses, the ﬁ rst one for player 1 and the second one for player 2.

For instance, if Player 1 plays T and Player 2 plays R, then Player 1 gets a payoﬀ of 2

and Player 2 gets 1. Let’s assume that each player knows that these are the strategies

and the payoﬀs, each player knows that each player knows this, each player knows that

each player knows that each player knows this,... ad in ﬁ nitum.

Now, player 1 looks at his payoﬀs, and realizes that, no matter what the other player

plays, it is better for him to play M rather than B. That is, if 2 plays L, M gives 2 and

B gives 1; if 2 plays m, M gives 1, B gives 0; and if 2 plays R, M gives 0, B gives -1.

Therefore, he realizes that he should not play B. 1 NowhecomparesTandM.Herealizes

that, if Player 2 plays L or m, M is better than T, but if she plays R, T is de ﬁ nitely

better than M. Would Player 2 play R? What would she play? To ﬁ nd an answer to

these questions, Player 1 looks at the game from Player 2’s point of view. He realizes

that, for Player 2, there is no strategy that is outright better than any other strategy.

For instance, R is the best strategy if 1 plays B, but otherwise it is strictly worse than

m. Would Player 2 think that Player 1 would play B? Well, she knows that Player 1 is

trying to maximize his expected payoﬀ,givenbythe ﬁ rst entries as everyone knows. She

must then deduce that Player 1 will not play B. Therefore, Player 1 concludes, she will

not play R (as it is worse than m in this case). Ruling out the possibility that Player 2

plays R, Player 1 looks at his payoﬀs, and sees that M is now better than T, no matter

what. On the other side, Player 2 goes through similar reasoning, and concludes that 1

must play M, and therefore plays L.

This kind of reasoning does not always yield such a clear prediction. Imagine that

you want to meet with a friend in one of two places, about which you both are indiﬀerent.

Unfortunately, you cannot communicate with each other until you meet. This situation

1 After all, he cannot have any belief about what Player 2 plays that would lead him to play B when

M is available.

is formalized in the following game, which is called pure coordination game:

\ 2 L tRght

Top (1,1) (0,0)

Bottom (0,0) (1,1)

Here, Player 1 chooses between Top and Bottom rows, while Player 2 chooses between

Left and Right columns. In each box, the ﬁ rst and the second numbers denote the von

Neumann-Morgenstern utilities of players 1 and 2, respectively. Note that Player 1

prefers Top to Bottom if he knows that Player 2 plays Left; he prefers Bottom if he

knows that Player 2 plays Right. He is indiﬀerent if he thinks that the other player is

likely to play either strategy with equal probabilities. Similarly, Player 2 prefers Left if

she knows that player 1 plays Top. There is no clear prediction about the outcome of

this game.

One may look for the stable outcomes (strategy pro ﬁ les) in the sense that no player

has incentive to deviate if he knows that the other players play the prescribed strategies.

Here, Top-Left and Bottom-Right are such outcomes. But Bottom-Left and Top-Right

are not stable in this sense. For instance, if Bottom-Left is known to be played, each

player would like to deviate — as it is shown in the following ﬁ gure:

\ 2 t Ri t

Top (1,1) ⇐⇓ (0,0)

Bottom (0,0) ⇑ = ⇒ (1,1)

(Here, ⇑ means player 1 deviates to Top, etc.)

Unlike in this game, mostly players have diﬀerent preferences on the outcomes, in-

ducing con ﬂ ict. In the following game, which is known as the Battle of Sexes,con ﬂ ict

and the need for coordination are present together.

\ 2 L tRight

Top (2,1) (0,0)

Bottom (0,0) (1,2)

Here, once again players would like to coordinate on Top-Left or Bottom-Right, but

now Player 1 prefers to coordinate on Top-Left, while Player 2 prefers to coordinate on

Bottom-Right. The stable outcomes are again Top-Left and Bottom- Right.

(2,1)

(0,0)

(1,2)

Figure 1:

Now, in the Battle of Sexes, imagine that Player 2 knows what Player 1 does when

she takes her action. This can be formalized via the following tree:

Here, Player 1 chooses between Top and Bottom, then (knowing what Player 1 has

chosen) Player 2 chooses between Left and Right. Clearly, now Player 2 would choose

Left if Player 1 plays Top, and choose Right if Player 1 plays Bottom. Knowing this,

Player 1 would play Top. Therefore, one can argue that the only reasonable outcome of

this game is Top-Left. (This kind of reasoning is called backward induction.)

When Player 2 is to check what the other player does, he gets only 1, while Player 1

gets 2. (In the previous game, two outcomes were stable, in which Player 2 would get 1

or 2.) That is, Player 2 prefers that Player 1 has information about what Player 2 does,

rather than she herself has information about what player 1 does. When it is common

knowledgethataplayerhassomeinformationornot,theplayermayprefernottohave

that information — a robust fact that we will see in various contexts.

Exercise 1 Clearly, this is generated by the fact that Player 1 knows that Player 2

will know what Player 1 does when she moves. Consider the situation that Player 1

thinks that Player 2 will know what Player 1 does only with probability π<1,andthis

probability does not depend on what Player 1 does. What will happen in a “reasonable”

equilibrium? [By the end of this course, hopefully, you will be able to formalize this

situation, and compute the equilibria.]

Another interpretation is that Player 1 can communicate to Player 2, who cannot

communicate to player 1. This enables player 1 to commit to his actions, providing a

strong position in the relation.

Exercise 2 Consider the following version of the last game: after knowing what Player

2 does, Player 1 gets a chance to change his action; then, the game ends. In other words,

Player 1 chooses between Top and Bottom; knowing Player 1’s choice, Player 2 chooses

between Left and Right; knowing 2’s choice, Player 1 decides whether to stay where he

is or to change his position. What is the “reasonable” outcome? What would happen if

changing his action would cost player 1 c utiles?

Imagine that, before playing the Battle of Sexes, Player 1 has the option of exiting,

in which case each player will get 3/2, or playing the Battle of Sexes. When asked to

play, Player 2 will know that Player 1 chose to play the Battle of Sexes.

There are two “reasonable” equilibria (or stable outcomes). One is that Player 1

exits, thinking that, if he plays the Battle of Sexes, they will play the Bottom-Right

equilibrium of the Battle of Sexes, yielding only 1 for player 1. The second one is

that Player 1 chooses to Play the Battle of Sexes, and in the Battle of Sexes they play

Top-Left equilibrium.

Play

Exit

Left

Right

Top

(2,1)

(0,0)

Bottom

(0,0)

(1,2)

(3/2,3/2)

Some would argue that the ﬁ rst outcome is not really reasonable? Because, when

askedtoplay,Player2willknowthatPlayer1haschosentoplaytheBattleofSexes,

forgoing the payoﬀ of 3/2. She must therefore realize that Player 1 cannot possibly be

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: