GOV 2005: Game Theory
Section 5: Subgame-Perfect Eqm
Alexis Diamond
adiamond@
Agenda
Main ideas
Key terms
Extensive Games, Backward Induction
Subgame Perfect Nash Equilibrium
Baron and Ferejohn: Bargaining in Legislatures
The strategic setting
Two-round, 3 candidate closed rule game
Two-round, n-candidate closed rule game
Infinite-round, 3 candidate closed rule game
Open-rule games
Endogenizing the rules
Key Terms
Sequential Rationality: Players should be rational at every decision-making opportunity (information set)
Backward Induction: Process of analyzing a game from back to front, eliminating actions which are dominated given the terminal nodes that would be reached
Most useful in extensive-form games of complete information
If there are no ties in payoffs, backward induction completely solves the game, finding the single rational strategy profile
Subgame: A node x initiates a subgame if neither x nor its successors are in an information set that contains nodes that are not successors of x. A subgame is the tree structure defined by such a node x and its successors
What is a proper subgame? Let’s do an-class exercise
Incumbent
Challenger
Out
In
Fight
Acquiesce
ø
Incumbent
Challenger
Out
In
Fight
Acquiesce
ø
Slack off
Incumbent
Incumbent
Challenger
Out
In
Fight
Acquiesce
Challenger
ø
Back out
Hit Back
1
Out
In
ø
2
Fight
Acquiesce
Spend
Save
Save
Spend
How Many Subgames Do You See?
1
1
Extensive Games w/ Perfect Info
Players
Terminal History: a set of sequences (chronologically ordered actions, histories), describing a complete game
Player Function: the function that assigns a player to every sequence
Preferences for the Players: preferences over the set of terminal histories
Any preference over terminal histories may be translated directly into preferences over outcomes, (and vice-versa?*)
for example: the “Entry” Game...
An Extensive Form Game is Defined by Four Components
*See Osborne, p. 155
Example: The Entry Game
Players: an incumbent and a challenger
Terminal History: (In, Acquiesce), (In, Fight), and (Out)
Player Function: P(ø) = challenger , P(In) = incumbent
Preferences for the Players:
Challenger’s preferences represented by payoff function u1
u1(In, Acquiesce) = 2, u1(Out) = 1, u1(In, Fight) = 0
Incumbent’s preferences represented by payoff function u2
u2(In, Acquiesce) = 1, u2(Out) = 2, u2(In, Fight) = 0
An Extensive Form Game is Defined by Four Components
Incumbent
Challenger
Out
In
Fight
Acquiesce
(1, 2)
(0, 0)
(2, 1)
The Entry Game
Payoff is defined as
(Challenger, Incumbent)
ø
What’s the solution?
(use backward induction)
When Backward Induction Fails
Players: an incumbent and a challenger
Terminal History: (In, Acquiesce), (In, Fight), and (Out)
Player Function: P(ø) = challenger , P(In) = incumbent
Preferences for the Players:
Challenger’s preferences represented by payoff function u1
u1(In, Acquiesce) = 2, u1(Out) = 1, u1(In, Fight) = 0
Incumbent’s preferences represented by payoff function u2
u2(In, Acquiesce) = 1, u2(Out) = 2, u2(In, Fight) = 1
A Variant of the Entry Game (Empty Threat Game)
Incumbent
Challenger
Out
In
Fight
Acquiesce
(1, 2)
(0, 1)
(2, 1)
The Entry Game
Payoff is defined as
(Challenger, Incumbent)
ø
What’s the solution?
(just try to use backward induction...)
Subgame Perfect Nash Eqm
Subgame Perfect Nash Equilibrium: A strategy profile is called a SPNE if it specifies a Nash equilibrium in every subgame of the original game
Equilibrium concept incorporating idea of sequential rationality
If any particular subgame is reached, then we can expect the players to follow through with the prescription of the strategy
In this sense, SPE is a robust solution concept (robust to errors)
Procedure
Examine the matrices corresponding to all of the subgames
Locate Nash equilibria
For infinite games, examine subgames toward the end of the extensive form (hoping that these subgames have unique Nash equilibria
Go backwards, embedding the equilibrium outcomes in larger subgames
To be a SPNE, the Strategy Must Be Credible Along the Eqm Path
SPNE: Robusto!
In a strategic game, NE rationale is that in steady state, each player’s experience playing the game leads her belief about the other players’ actions to be correct.
In a sequential game, this rationale does not apply, because (for example) a challenger who always chooses Out never observes the incumbent’s action after the history In.
Nash Equilibrium of an extensive game: a slightly perturned steady state in which, on rare occasions, non-equilibrium actions are taken and the perturbations allow each player eventually to observe every other player’s action after every history. Given such perturbations, every player eventually learns the others entire strategies.
Interpreting (Out, Fight) as such a perturbed steady state: On rare occasions when the challenger enters, the subsequent behavior of the incumbent to fight is not a steady state in the remainder of the game; if the challenger enters, the incumbent is better of acquiescing than fighting. The NE is not a robust steady state of the extensive game.
Incumbent
Challenger
Out
In
Fight
Acquiesce
(1, 2)
(0, 0)
(2, 1)
To be a SPNE, the Strategy Must Be Credible Along the Eqm Path
Nash Equlibria
(Out, Fight), (In, Acquiesce)
ø
Still confused about SPNE?
Subgame Perfect Nash Equilibrium
Each player’s strategy must be optimal for every history after which it is the player’s turn to move, not only at the start of the game, as in the definition of Nash Equilibrium
NE may not be optimal in some subgames, but a NE is optimal in any subgame reached when players follow their strategies (by definition)
A subgame perfect NE generates a NE in every subgame
So every player’s strategy is optimal, given other players strategies, throughout the entire game
Significance of SPNE versus NE:
Requirement of SPNE is that each player’s strategy be optimal after histories that do not occur if players follow their strategies,
Like the history In when the challenger’s action is Out at the start of the entry game.
More ways of saying the same thing yet again, slightly differently
When Backward Induction Fails
The incumbent is indifferent
If challenger is In, incumbent is indifferent
If challenger is Out, incumbent is indifferent
Challenger prefers In when incumbent chooses Acquiesce
Challenger prefers Out when incumbent chooses Fight
Two SPNE: (In, Acquiesce), (Out, Fight)
Both correspond to a steady-state outcome
The SPE (In, Acquiesce) is a perfectly reasonabe (risky?) steady state
If you had played the game 100s of times against opponents drawn from the same population, and your opponent had always chosen Acquiesce, you could reasonably expect your next opponent to choose Acquiesce, and thus you could optimally choose In
And SPNE is There to Pick up the Pieces
Incumbent
Challenger
Out
In
Fight
Acquiesce
(1, 2)
(0, 1)
(2, 1)
The Entry Game
Payoff is defined as
(Challenger, Incumbent)
ø
What’s the solution?
(use SPNE, not backward induction...)
SPNE is an extension of backward induction
Corresponds to backward induction in finite games of perfect information when there is a single best action for the player who moves at the start of each subgame
What happens in a game in which at the start of some subgames more than one action is optimal?
We trace back separately the implications for behavior in the longer subgames of every combination of optimal actions in the shorter subgames
Don’t always have perfect info; sometimes it’s simultaneous...
Ok--So What is SPNE Again?
2
1
Left
Right
Forward
ø
(2, 2)
Down
(3, 1)
2
2
1
A
B
C
D
C
D
(2, -2)
(2, -2)
(-2, 2)
(-2, 2)
2
1
Left
Right
(2, 2)
Forward
(3, 1)
(0, 0)
Down
ø
Model: legislature dividing up a budget, with legislatures trying to serve their own districts
Lots of structure imposed on this model
Procedures and rules of order are specified in detail
Equilibria: stable, self-enforcing terminal history
Legislative outcomes reflect the institutional structure of agenda formation and voting mechanism, as well as time-preference
Issues under investigation
Does equilibrium reflect majoritarian nature of the voting rule?
Does equilibrium allow benefits to distributed universally?
When the choice of institutions (open versus closed rules) is made endogenous, what determines which institution is selected?
How does time-preference affect the rules and distributive outcome?
Baron & Ferejohn: Bargaining in Legislatures
Key Concepts
Discounting and Time-Preference: 0 1
Discount factor : the cost of the passage of time
When = 1, time has no cost
$100 today (time t = 1) is equal to $100 tomorrow (t = 2), from the perspective of someone today.
When = 0, time is as costly as it can be: “do or die”
When = , the value of an agreement tomorrow is worth half the value of the same agreement today
This is a way of getting at impatience, or the notion that “time is money”
In this paper, they attribute it to reelection concerns to distribute benefits sooner, as well as the probability that lawmaker will be in office in the next period.
R
ø
V
Fail
2
1
3
1
3
Fail
Pass
Fail
Pass
Fail
Pass
V
V
V
Pass
Fail
Pass
Fail
Pass
V
V
V
Fail
Pass
Fail
Pass
Fail
Pass
V
V
V
Fail
2
1
3
2
1
3
Fail
Pass
2
V
V
R
R
R
Pass
Pass
X 2
X 1
X 3
Fail
X 2
X 3
X 1
X 2
X 3
X 1
X 2
X 3
X 1
Baron & Ferejohn
Closed-Rule Game
3 Lawmakers, 2 Rounds
Members can’t make binding commitments. An equilibrium strategy must be self-enforcing in the sense that the member would wish to execute it at each point at which action can be taken.
Therefore, the equilibrium is required to be subgame perfect.
Equilibrium Given 3 Lawmakers, 2 Rounds
Begin backward induction (n = 3 lawmakers)
Final (2nd) round, each has a 1/3 (or 1/n) chance
Proposer must offer rivals more than BATNA* (0)
Proposer offers rivals 0, takes it all
1/3 chance of getting it all, 2/3 chance of getting 0
Expected value is (1/3)*(1) + (2/3)*(zero) = 1/3 or (1/n)
1st round, each has 1/3 chance of being proposer
Must offer 1/2 the others more than their BATNAs
From perspective of round 1, BATNA is *(1/3) or ( /n)
Offers /3 to one lawmaker, and proposes 1 - (/3) for himself
This is better than the expected value of round two ( /3)
Motion carries, because majority is no worse off than BATNA
*Best Alternative to a Negotiated Agreement
Equilibrium With n Lawmakers, 2 Rounds
Same as Before…
1/3 chance to get it all, 2/3 chance of getting 0
Expected value is (1/n)*(1) + (2/3)*(0) = (1/n)
1st round, each has 1/n chance of being proposer
Must offer 1/2 the others more their BATNAs
From perspective of round 1, BATNA is /n
Offers /n to *(n-1) lawmakers
Proposes that he should get to keep 1 - [(1/2)(n-1)*( /n)]
Motion carries, because majority prefers this to BATNAs
As n → ∞: the proposer gets to keep 1- [(1/2)* )
Recall that when n = 3, proposer kept 1- [(1/3)* )
Depending on n, proposer keeps between 1/2 and 1/3 the benefits
R
ø
V
Fail
2
1
3
1
3
Fail
Pass
Fail
Pass
Fail
Pass
V
V
V
Pass
Fail
Pass
Fail
Pass
V
V
V
Fail
Pass
Fail
Pass
Fail
Pass
V
V
V
Fail
2
1
3
2
1
3
Fail
Pass
2
V
V
R
R
R
Pass
Pass
X 2
X 1
X 3
Fail
X 2
X 3
X 1
X 2
X 3
X 1
X 2
X 3
X 1
Baron & Ferejohn
Infinite Round Closed-Rule Game
3 Lawmakers
R
R
R
R
R
R
R
R
R
Given a minimum level of impatience, there are infinite subgame perfect equilibria sustainable by the threat
of future punishment.
All equilibria punish those who
would deviate by giving them
a payoff of zero. Members
expect the punishment
to be enforced, since
those who fail to punish
are themselves punished.
If people are really impatient,
this is equivalent to saying
they care very little for what
will happen in the future;
impatient people can’t be
threatened by future punishment.
Even so, there is an argument that these equilibria are unconvincing & not robust. Ex-post, people may be indifferent about punishing; or, ignorant of the history.
Closed Rule and Stationary Equilibria
What are stationary equilibria?
Formally: An equilibria is stationary if the continuation values for each structurally-equivalent subgame are the same
Continuation value: value of going to next subgame (vj)
Structurally-equivalent subgame: When subgames are identical in every way but their prior history
Member recognized in round 1 chooses (x21, x31)
Feasible allocation set (A): x21 + x31 1 and x21, x31 0.
Member 1 maximizes: 1 - (x21 + x31) . A and the requirement that the proposal passes by a majority
To pass, xj1 vj, for lawmaker j in the majority
Collapsing infinite-sessions into a one-shot game
Closed Rule and Stationary Equilibria
Member 1 maximizes: 1 - (x21 + x31) . A and the requirement that proposal passes by a majority
To pass, xj1 vj, for lawmaker j in the majority
Recall that prob (being in majority) = (n-1)/n
Continuation values vj are:
vj = payoff (i is proposer)*(probability i is chosen) + payoff (i is in majority)*(prob i is in majority) +
payoff (i gets zero)*(probability i gets zero).
vj = [1 - ( v(n-1)/2)])*(1/n) + [(vj)**(n-1)/n] + 0.
vj* = 1/n.
Proposer claims all that would go to excluded lawmakers. With discounting, the proposer also benefits from the impatience of members in his winning coalition:
(see p. 1193 on the bottom)
Solution to the Infinite Round Game
Open Rule Bargaining
(1) Chance selects a proposer
(2) M1 makes offers xi1 to one or more others (i)
(3) Chance recognizes another member, M2
(4) M2 moves the question to a vote, or amends
If M2 amends, and the next round begins at step 3
If M2 moves, there’s a vote. If x1 is defeated, return to step 1.
If M2 moves and x1 passes, payoffs are received.
So… is there a (universalistic) equilibrium where all other members receive an offer?
xi1 = [1-(n-1) x1], xi1 = /(1 + 2), (proposer) = 1- (n -1)* xi1
How does this game differ?
Open Rule Bargaining
What are the Distributive Comparative Statics?
Proposer must buy off a majority/supermajority) of others.
The more lawmakers he buys, the higher the likelihood that his offer will be approved.
All else equal, the more lawmakers there are, the fewer the proposer will chose to buy off
Low discount factors mean that lawmakers deeply discount the future, and are relatively unwilling to risk the chance someone will propose an amendment and take up extra time
Legislature is certain to complete its task in round 1 if and only if the offer in round 1 is universalistic
This will happen only if discount factors are low enough
Distribution is more equal under an open rule than under a closed rule
Open rule reduces the power of the recognition, relative to a closed rule
Yet, the one recognized member will never do worse than anyone else
And, recognition advantage increasing in membership impatience
Endogenizing the Rules
What are the Distributive Comparative Statics?
Unless there is no impatience, ex-ante*, legislature prefers a closed rule to a simple open rule
The sum of the values of a closed-rule game is always at least as much as that of an open-rule game
This is because the closed rule finishes the game in one round, and most of the open-rule equilibria involve the chance of multiple rounds
Every time it goes to the next round, value is lost forever via discounting
Nevertheless, an open rule does have its benefits
More equal ex-post distribution
More compatible with democratic theory, int hat it allows greater opportunity to members than does a closed rule
By ex-ante here I mean prior to the very first round, before any one legislator is selected as proposer.
