Home > Game Theory

# Game Theory

Game Theory

What is game theory (GT)?

• GT is the study of multi-agent decision problems
• GT is used to predict what will happen (equilibrium) when:
• There are more than one agent but not too many for each of them to be negligible
• Each agent��s payoff depend on what they decide to do and what others decide to do
• Examples: members of a team, oligopolies, international negotiations,

Basic Textbook:

• ��Game Theory for Applied Economists�� by Robert Gibbons
• The slides are also based in this textbook

Elements of a game��

• Players:
• agents that take actions
• ��nature�� is also a player
• Information sets: What is known by each agent at each moment that a decision must be taken
• Actions:
• In each moment of a game, what can each agent choose. Examples: q=20,30,40; High, medium or low taxes
• Outcomes: what is the result for each set of possible actions
• Payoffs: Depending on the outcome, what each agent gets( could be in terms of utility or directly money)

Static games of complete information

What is a static game of complete information?

• Static (or simulateneous-move) game:
• Players choose actions
• Each player chooses an action without knowing what the other players have choosen
• Complete information:
• Every player will know the payoff that each agent will obtain depending on what actions have been taken

The normal-form representation of a game

• Basic tool to analyze games
• Very useful for static games under complete information.
• It consists of:
• The player in the game
• The strategies available to each player
• In this type of games, strategies are actions, but they will be very different in more complicated dynamic games !!!
• The payoff received by each player for each combination of strategies the could be chosen by the players
• Usually represented by a table

The normal-form representation of a game

The Prisioners�� Dilemma

Two prisoners. They are being question by the police in different rooms. Each can confess or not

-6,-6

0,-9

Confess

-9,0

-1,-1

Not Confess

Confess

Not Confess

Prisoner B

Prisoner A

Prisoner A

Be sure that you recognize the elements of the game !!!!

Solutions concepts for static games with complete information

• Given a game, we will apply a solution concept to predict which will be the outcome (equilibrium) that will prevail in the game
• Elimination of strictly dominated strategies
• Nash equilibrium
• These solution concepts can also be applied to more complicated games�� but they are terribly useful for static games with complete information

Elimination of strictly dominated strategies

• Intuitive solution concept
• Based on the idea that a player will never play a strategy that is strictly dominated by another strategy
• An strategy si�� of player i is strictly dominated by si���� if player i��s payoff is larger for si���� than for si�� independently of what the other players play!
• In the prisoners' dilemma, the strategy ��not confess�� is strictly dominated by ��confess��

Iterative Elimination of strictly dominated strategies

• In some games, the iterative process of eliminating strictly dominated strategies lead us to a unique prediction about the result of the game (solution)
• In this case, we say that the game is solvable by iterative elimination of strictly dominated strategies
• Let��s see an example��

Iterative Elimination of strictly dominated strategies

0,1

1,2

MIDDLE

2,0

0,3

DOWN

0,1

1,0

UP

RIGHT

LEFT

If the red player is rational, it will never play ��Right�� because it is strictly dominated by ��Middle��. If the blue player knows that red is rational, then he will play as if the game were��

Iterative Elimination of strictly dominated strategies

0,1

1,2

MIDDLE

0,3

DOWN

1,0

UP

LEFT

In this case if the blue player is rational and he knows that red is rational, then the blue player will never play Down. So, the red player will play as if the game were:

Iterative Elimination of strictly dominated strategies

1,2

MIDDLE

1,0

UP

LEFT

So, if the red player is rational, and he know that blue is rational, and he knows that blue knows that he is rational, then the red player will play ��Middle��

The solution of the game is (UP, Middle)

Problems with this solution concept��

We need to assume that rationality is common knowledge

��Decisions are tough����. In many games there are no strategies that are strictly dominated�� or there are just a few and the process of deletion does not take us to a solution but only to a smaller game��

Example of a game were there are no dominated strategies

5,3

0,4

4,0

Middle

3,5

4,0

MIDDLE

6,6

3,5

Bott

5,3

0,4

UP

RIGHT

LEFT

In this game, no strategies are dominated, so the concept of iterated elimination of dominated strategies is not very useful��

Let��s study the other solution concept��

Some notation, before defining the solution concept of Nash Equilibrium,

• SA = strategies available for player A (a SA)
• SB = strategies available for player B (bSB)
• UA = utility obtained by player A when particular strategies are chosen
• UB = utility obtained by player B when particular strategies are chosen

Nash Equilibrium

• In games, a pair of strategies (a*,b*) is defined to be a Nash equilibrium if a* is player A��s best strategy when player B plays b*, and b* is player B��s best strategy when player A plays a*
• It has some resemblance with the market equilibrium where each consumer and producer were taking optimal decisions��

Nash Equilibrium in Games

• A pair of strategies (a*,b*) is defined to be a Nash equilibrium if

UA(a*,b*)  UA(a��,b*) for all a��SA

UB(a*,b*)  UB(a*,b��) for all b��SB

Intuition behind Nash Eq.

• If a fortune teller  told each player of a game that a certain (a*,b*) would be the predicted outcome of a game
• The minimum criterion that this predicted outcome would have to verify is that the prediction is such that each player is doing their best response to the predicted strategies of the other players�� that is the NE
• Otherwise, the prediction would not be internally consistent, would be unstable��

Intuition behind Nash Eq.

• If a prediction was not a NE, it would mean that at least one individual will have an incentive to deviate from the prediction
• ��The idea of convention�� if a convention is to develop about how to play a given game, then the strategies prescribed by the convention must be a NE, else at least one player will not abide by the convention

Checking whether or not a pair of strategies is a NE

• In the Prisioners Dilema:
• (No Confess, No Confess)
• Notice that it is not optimal from the ��society-of-prisoners�� point of view
• In the previous 3x3 game: BxR
• Notice that these NE also survived the iterated process of elimination of dominated strategies�� This is a general result��

Relation between NE and iterated��

• If the process of iterative deletion of dominates strategies lead to a single solution�� this solution is a NE
• The strategies that are part of a NE will survive the iterated elimination of strictly dominated strategies
• The strategies that survive the iterated elimination of strictly dominated strategies are NOT necessarily part of a NE

Finding out the NE of a game��

• The underlining trick�� let��s see it with previous games��
• One cannot use this if the strategies are continuous (ie. Production level). We will see afterwards��

Multiple Nash Equilibrium

Some games can have more than one NE�� In this case, the concept of NE is not so useful because it does not give a clear prediction��as in this game called The Battle of the Sexes

1,2

0,0

Tennis

0,0

2,1

Tennis

SEX B

Prisoner A

SEX A

Nash Equilibrium with continuous strategies

Example: Duopoly. Firm i & Firm j

Strategies: Output level, that is continuous

Prisoner A

Prisoner A

Prisoner A

One can draw the best response functions. The intersection point is the NE

Prisoner A

qi

qj

a-c

(a-c)/2

(a-c)/2

a-c

(a-c)/3

(a-c)/3

Rj(qi

Ri(qj)

Nash Equilibrium in Mixed Strategies

• So far, we have used the word strategy. To be more explicit, we were referring to pure strategies
• We will also use the concept of mixed strategy
• In a static game with complete information, a mixed strategy is a vector that tell us with what probability the player will play each action that is available to him

Nash Equilibrium in Mixed Strategies

Consider the following game: matching pennies

-1,1

1,-1

Tails

1,-1

-1,1

Tails

Player 2

Prisoner A

Player 1

An example of a mixed strategy for player 1 would be: (1/3,2/3) meaning that player 1 will play Heads with probability 1/3 and Tails with probability 2/3

We can obviously say that a mixed strategy is (q,1-q) where q is the probability of Heads

Nash Equilibrium in Mixed Strategies

• Why are Mixed Strategies useful?
• Because in certain games, players might find optimal to have a random component in their behavior
• For instance, if it was the case that the Inland Revenue would never inspect individuals taller than 190 cms, these individuals will have lots of incentives not to declare their income truthfully!

Nash Equilibrium in Mixed Strategies

Notice that the matching pennies game does not have an equilibrium in pure strategies

-1,1

1,-1

Tails

1,-1

-1,1

Tails

Player 2

Prisoner A

Player 1

Does this game have an equilibrium in mixed strategies?

-1,1

1,-1

Tails

1,-1

-1,1

Tails

Player 2

Prisoner A

Player 1

Prisoner A

Prisoner A

Drawing the best responses

1/2

1/2

q*(r); player 2 br

r*(q); player 1 br

Notice the vertical and horizontal lines are because of the ��any between [0,1]��

The Nash eq. in mixed strategies is the intersection of the best response��in this case

(1/2,1/2) for player 1 and (1/2,1/2) for player 2

Existence of Nash Equilibrium

• A game could have more than one Nash Equilibrium
• The same game could have equilibria in both pure and mixed strategies or only pure or only mixed
• Notice that this is a bit artificial�� any pure strategy is a mixed strategy where one action has probability 1
• Any game has at least one NE, but this one could be in mixed strategies

Dynamic games of complete information

Extensive-form representation

-In dynamic games, the normal form representation is not that useful. The extensive-form representation will be a very useful tool in this setting. It consists of:

-players

-when each player has the move

-what each player can do at each of his opportunities  to move

-what each player knows  at each of his opportunities  to move

-the payoff received by each player for each  combination of moves that could be chosen by the  players

-Usually represented by a tree��

Example of Extensive form representation

A

L

S

The dormitory game:

A chooses loud (L) or soft (S). B hears the noise and chooses

(L) Or (S).

B

B

L

S

L

S

7,5

5,4

6,4

6,3

Strategies for dynamic games

-In dynamic games, we have to be much more careful defining strategies.

A strategy is a complete plan of action – it specifies a feasible action for the player in every contingency in which the player might be called on to act

In the previous example, a strategy for player A is (L). Another possible strategy for player A is (H)

An example of a strategy for player B is  (L,S) that means that player B will play L if he gets to his first node and will play S if he get to the second node.

Other strategies would be (L,L); (S,S); and (S,L)

Extensive-form representation

-It could be that when a player moves, he cannot distinguish between several nodes�� he does not know in what node he is!

-For instance, it could be that when player B moves, he has not heard the noise from player A

-We reflect this ignorance by putting these two nodes together in the same circle�� as in the following slide��

A Dormitory Game

A

L

S

A chooses loud (L) or soft (S).

B makes a similar choice without knowing A��s choice

B

B

L

S

L

S

7,5

5,4

6,4

6,3

Notice that this game will actually be static !!!!!!

Information set

-This take us to the notion of an information set!!

An information set for a player is a collection of decision nodes satisfying:

1. The player has the move at every node in the information set
2. When the play of the game reaches a node in the information set, the player with the move does not know which node in the information set has (or has not) been reached

As a consequence, the nodes surrounded by the same circle are part of the same information set

Strategies

-We can be more precise defining what a strategy is.

A player��s strategy is an action for each information set that the player has !!!

Dynamic games with complete information

Can be divided in:

Perfect information: at each move in the game, the player with the move knows the full history of the play of the game so far��

Imperfect information: at some move the player with the move does not know the history of the game

Notice, in complete games with perfect information each information set must have one and only one node (the information set is singleton). If info is complete but there is an information set with more than one node, it must be an imperfect information game.

Dynamic games with complete information

Another classification:

Non-repeated games: The game is just played once

Finitely repeated games: The game is repeated a finite number of times

Infinitely repeated games: The game is repeated an infinite amount of times

Non-repeated dynamic games with perfect information

Two main issues:

-Is the Nash Equilibrium an appropriate solution concept?

-If not�� Define a better solution concept��

A Two-Period Dormitory Game

A

L

S

A chooses loud (L) or soft (S

B

B

L

S

L

S

B makes a similar

choice knowing

A��s choice

7,5

5,4

6,4

6,3

Thus, we should

put B��s strategies

in a form that takes

the information on

A��s choice into

account

A Two-Period Dormitory Game

6,3

6,4

6,3

6,4

S

5,4

5,4

7,5

7,5

L

A��s Strategies

S,S

S,L

L,S

L,L

B��s Strategies

• Each strategy is stated as a pair of actions showing what B will do depending on A��s actions

A Two-Period Dormitory Game

6,3

6,4

6,3

6,4

S

5,4

5,4

7,5

7,5

L

A��s Strategies

S,S

S,L

L,S

L,L

B��s Strategies

• There are 3 Nash equilibria in this game
• A:L, B:(L,L)
• A:L, B:(L,S)
• A:S, B:(S,L)

A Two-Period Dormitory Game

6,3

6,4

6,3

6,4

S

5,4

5,4

7,5

7,5

L

A��s Strategies

S,S

S,L

L,S

L,L

B��s Strategies

• B (a,b) =
• a =strategy that B plays if A plays L
• b= strategy that B plays if A plays S
• A:L, B:(L,S) and A:S, B:(S,L) do not seem appropiate
• each incorporates a non-credible threat on the part of B (out of the equilibrium path)
• For instance regarding A:L, B:(L,S),  If A chose S –out of equilibrium- it is not credible that B chose S as (L,S) indicates

• In games with more than one period, there might be strategies that are Nash Eq but they involve no credible threats
• We need a concept of equilibrium for games with more than one period
• The concept will be called Subgame Perfect Nash Equilibrium (SPNE)

• We will define SPNE more formally later on. For the time being, let��s say that
• A SPNE is a Nash equilibrium in which the strategy choices of each player do not involve no-credible threats
• A strategy involves no-credible threats if they require a player to carry out an action that would not be in its interest at the time the choice must be made

• A simple way to obtain the SPNE in dynamic games with perfect information is  to solve the game backwards, called ��backwards induction��
• Whiteboard with the dormitory example��
• Algorithm:
• Find the optimal action at each of the predecessors of the terminal nodes
• Associate these nodes with the payoffs of the anticipated terminal node
• Start again the process with this reduced game��
• (see another description of the algorithm in the distributed handout��)

• Example in distributed handout��
• Another example, Pg. 60 of the book
• The (c,s) example��
• Of the three NE that we had in the Dormitory game, only B:(L,L), A: L is a SPNE
• In the backward induction procedure, we are asking each individual to do whatever is best whenever they move�� (independently whether they are or not in the equilibrium path) so it is not possible to have non-credible threats

• Backwards Induction with continuous strategies
• Example: Stackelberg model of duopoly
• Firm 1 produces q1
• Firm 2, observes q1 and produces q2
• Compute R(q1) = Firm 2��s optimal response to an arbitrary level of production by Firm 1.
• R(q1) is Firm 2��s best response.
• Compute what is the optimal q1 for Firm 1 if she know that Firm 2 will produce R(q1)
• P=a-b(q1+R(q1))

• Backwards Induction with continuous strategies
• Example: Stackelberg model of duopoly
• Firm 1 produces q1
• Firm 2, observes q1 and produces q2
• Compute R(q1) = Firm 2��s optimal response to an arbitrary level of production by Firm 1.
• R(q1) is Firm 2��s best response.
• Compute what is the optimal q1 for Firm 1 if she know that Firm 2 will produce R(q1)
• P=a-b(q1+R(q1))

• Non-repeated dynamic games complete but imperfect information
• At some point of the game, a player does not know exactly in which node he or she is (��does not completely know the history of moves)
• See example��
• We cannot apply Backwards Induction because a player might not know what is best to play as she might not know in what node she is
• In order to understand the solution concept, we must define a SPNE more formally.
• To do that, we must understand what a subgame is

• Non-repeated dynamic games complete but imperfect information
• A subgame in an extensive form game:
• Begins at a decision node n that is a singleton (but is not the game��s first decision node)
• Includes all the decision and terminal nodes following n in the game tree (but no nodes that do not follow n)
• Does not cut any information sets, that is, if a decision node n�� follows n in the game tree, then all other nodes in the information set containing n�� must also follow n, and so must be included in the subgame
• See example in paper
• See pg 121 in the book

• Non-repeated dynamic games complete but imperfect information
• A strategy profile is SPNE:
• If it is a Nash Equilibrium of the game and of every subgame of the game
• Two ways to find the SPNE of a game:
• Obtain the NE and then see which of them imply that that they are NE of the different subgames of the game
• Finding the NE of the last information sets and substitute backwards��
• See example in the handout

Repeated Games

• Many economic situations can be modeled as games that are played repeatedly
• consumers�� regular purchases from a particular retailer
• firms�� day-to-day competition for customers
• workers�� attempts to outwit their supervisors

Repeated Games

• An important aspect of a repeated game is the expanded strategy sets that become available to the players
• opens the way for credible threats and subgame perfection
• It is important whehter or not the game is repeated a finite or infinite number of times

Prisoners�� Dilemma Finite Game

2,2

0,3

H

3,0

1,1

L

A��s Strategies

H

L

B��s Strategies

• Firms A and B. Low or High price. In a one shot game, (L,L) –no cooperating- is the NE

Prisoners�� Dilemma Finite Game

2,2

0,3

H

3,0

1,1

L

A��s Strategies

H

L

B��s Strategies

• The NE is inferior to (H,H) the cooperating strategy

Prisoners�� Dilemma Finite Game

• Suppose this game is to be repeatedly played for a finite number of periods (T)
• Any expanded strategy in which A promises to play H in the final period is not credible
• when T arrives, A will choose strategy L
• The same logic applies to player B

Prisoners�� Dilemma Finite Game

• Any SPNE for this game can only consist of the Nash equilibrium strategies in the final round
• A:L; B:L
• The logic that applies to period T also applies to period T-1
• Do ��backward induction�� in the whiteboard��
• The only SPNE in this finite game is to require the Nash equilibrium in every round -> No cooperation

Eq. in a Finite Repeated Game

• If the one-shot game that is repeated a finite number of times has a unique NE then the game repeated game has a unique outcome: the NE of the one-shot game

Game with Infinite Repetitions

• We cannot use backward induction because there is no a terminal node��
• In Infinite games, each player can announce a ��trigger strategy��
• promise to play the cooperative strategy as long as the other player does
• when one player deviates from the pattern, the other player will play no cooperation in the subsequent periods�� and hence the game will revert to the single period NE

Game with Infinite Repetitions

• Let��s think of a player��s decision in any arbitrary node of the game��
• If B decides to play cooperatively, payoffs of 2 can be expected to continue indefinitely
• If B decides to cheat, the payoff in period K will be 3, but will fall to 1 in all future periods

• Let��s think of a player��s decision in any arbitrary node of the game��
• If  is player B��s discount rate, the present value of continued cooperation is

2 + 2 + 22 + �� = 2/(1-)

• The payoff from cheating is

3 + 1 + 21 + ��= 3 + 1/(1-)

• Continued cooperation will be credible (will be a NE of the subgame that starts in the node where the player is choosing) if:

2/(1-) > 3 + 1/(1-)

• > ½

• If players value the future enough, they will prefer to cooperate�� in the case of firms this is called Tacit Collusion

Game with Infinite Repetitions

•  can also be interpreted as the probability that the game will continue one more period
• (Folk theorem) Let G be a finite, static game of complete information. Let (e1,e2,��,en) denote the payoffs from a NE of G, and let (x1,x2,��,xn) denote any other feasible payoffs from G. If xi>ei foor every player i and if  is sufficiently close to one, then there exists a SPNE of the infinitely repeated game that achieves (x1,x2��,xn) as the average payoff
• In other words, if cooperation is better than the NE for every player and players value the future enough then cooperation is a SPNE of the game repeated a infinite number of times

Games of Incomplete Information

• There is at least one player that does not know the payoff of at least one player

Games of Incomplete Information

• Each player in a game may be one of a number of possible types (tA and tB)
• player types can vary along several dimensions
• We will assume that our player types have differing potential payoff functions
• each player knows his own payoff but does not know his opponent��s payoff with certainty

Games of Incomplete Information

• Each player��s conjectures about the opponent��s player type are represented by belief functions [fA(tB)]
• consist of the player��s probability estimates of the likelihood that his opponent is of various types
• Games of incomplete information are sometimes referred to as Bayesian games

Games of Incomplete Information

• The payoffs to A and B depend on the strategies chosen (a SA, b SB) and the player types
• For one-period games, it is fairly easy to generalize the Nash equilibrium concept to reflect incomplete information
• we must use expected utility because each player��s payoffs depend on the unknown player type of the opponent

Games of Incomplete Information

• A strategy pair (a*,b*) will be a Bayesian-Nash equilibrium if a* maximizes A��s expected utility when B plays b* and vice versa

A Bayesian-Cournot Equilibrium

• Suppose duopolists compete in a market for which demand is given by

P = 100 – qAqB

• Suppose that MCA = MCB = 10
• the Nash (Cournot) equilibrium is qA = qB = 30 and payoffs are A = B = 900

A Bayesian-Cournot Equilibrium

• Suppose that MCA = 10, but MCB may be either high (= 16) or low (= 4)
• Suppose that A assigns equal probabilities to these two ��types�� for B so that the expected MCB = 10
• B does not have to consider expectations because it knows there is only a single A type

A Bayesian-Cournot Equilibrium

• B chooses qB to maximize

B = (P – MCB)(qB) = (100 – MCBqA – qB)(qB)

• The first-order condition for a maximum is

qB* = (100 – MCB – qA)/2

• Depending on MCB, this is either

qBH* = (84 – qA)/2   or

qBL* = (96 – qA)/2

A Bayesian-Cournot Equilibrium

• Firm A must take into account that B could face either high or low marginal costs so its expected profit is

A = 0.5(100 – MCAqA – qBH)(qA)                       + 0.5(100 – MCAqA – qBL)(qA)

A = (90 qA0.5qBH – 0.5qBL)(qA)

A Bayesian-Cournot Equilibrium

• The first-order condition for a maximum is

qA* = (90 0.5qBH – 0.5qBL)/2

• The Bayesian-Nash equilibrium is:

qA* = 30

qBH* = 27

qBL* = 33

• These choices represent an ex ante equilibrium

Dynamic Games with Incomplete Information

• In multiperiod and repeated games, it is necessary for players to update beliefs       by incorporating new information provided by each round of play
• Each player is aware that his opponent will be doing such updating
• must take this into account when deciding on a strategy
• We will not study them in this course
Search more related documents:Game Theory 