Game Theory and Strategic Thinking

Yuval Heller, BIU 2024

Chapter 2 in Dixit & Nalebuff

1

Presentation 2: Sequential Games (with Perfect Information)

Presentation’s Outline

• Sequential game (with perfect information): definition and description as a tree
• Strategic Rule 1: Look forward and reason backward
• Solving simple game trees
• Examples of more complex tree
• President-congress game (insight: greater freedom of action can hurt a player)
• Solving a long game by backward reasoning (22 flags game)
• Do people solve games by backward reasoning in real life?
• The ultimatum game (and the dictator game)
• Very complex trees (e.g., chess)
• Case study: The 1984 Orange Bowl (American College football final match)
• Home assignment 2
• Discussing Home Assignment 1

​

2

Sequential Game with Perfect Information

• Game in which:
• Players make choices sequentially (and not simultaneously)
• Each player knows all previous choices of all other players (as well as the payoffs of all players, and all aspects of the game)
• Key assumption: no uncertainty on past moves, nor on payoffs
• Sequential games can be graphically described as game trees
• Example:
• Poor country with weak contract enforcement
• Local businessman (Fredo) asks a foreign investor (Charlie) to invest $100,000 in a venture that will yield $500,000, and promises to equally share the profits after 1 year
• How to describe as a game tree

3

Example: Investment with Weak Enforcement

• How to solve the game? Look forward and reason backward
• In the absence of a clear & strong reason to believe Fredo’s promise, Charlie should predict that Fredo will keep all the profit for himself
• Thus, Charlie should choose not to invest
• The unique solution to the game (unique backward-induction equilibrium) is marked by the bold lines
• Observe that the equilibrium yields an inefficient outcome (both players would prefer Charlie investing and Fredo honoring contract, over not investing)

4

Charlie

Don’t

Invest

Fredo

Cheat

Honor Contract

Charlie: 0

Fredo: 0

Charlie: 150,000

Fredo: 250,000

Charlie: -100,000

Fredo: 500,000

Example of a more complex sequential game

• Simplified description of the president vs. congress 1987 game
• Two items of expenditure under consideration:
• Antiballistic missile system (M), supported by president Reagan
• Urban renewal (U), supported by the majority of congress
• Both sides prefer both expenditures over none
• Sequential game:
• Congress chooses which expenditure to approve: M, U, M+U, none
• President either approves or vetoes the entire package
• Reagan (Jan. 1987 state of the union address): “Give the president the same tool that 43 governors have—a line-item veto”
• Would adding a line-item veto help the president in this game?

​

​

5

President vs. Congress Game – Payoffs & Tree

• Payoffs (4 being best, 1 being worst)

​

• Game tree:

6

Unique backward-induction equilibrium outcome: Both U+M are implemented, payoff of 3 for each player

​

What will be the outcome if the president gets line-item veto power?

President vs. Congress Game with Line-Item Veto

• Unique backward-induction equilibrium outcome: Neither expenditure is implemented
• Pareto-worse outcome �(=worse outcome to both players)
• insight: greater freedom of action can hurt a player

​

7

Example: 21-Flags Game

• Game played in CBS �Survivor: Thailand 6^th Episode
• 2 players/groups
• Sequential play
• Each player has to remove in�her turn 1-3 flags
• The player to remove the last �flag wins
• CBS: first group removed 2 flags
• How much would you remove?

​

8

Solving the 21-flag game

• Game is too-long to describe as a tree
• Yet, one can still apply backward-induction reasoning
• How would you play if there were 1, 2, 3, 4, 5, … flags?
• In which positions (number of flags) a player can guarantee her win?

9

Do people solve games by backward reasoning in real life?�

• 21 flags In DN’s class experiments (Ivy league economics/MBA students):
• Students learn to play the backward-induction equilibrium after 3-4 plays
• Students seem to learn faster by watching others play, then by playing themselves
• A seemingly most-damaging criticism to real-life backward induction is the ultimatum game

10

Ultimatum Game

• 2 Players: proposer (A) and responder (B)
• Player A proposes how to divide a sum of money (say, $100)
• Player B decides whether to agree to A’s proposal
• If B agrees: the proposal is implemented
• If B refuses, neither player gets anything
• How would you play as a proposer?
• How would you respond as a responder?
• Experimentally played in hundreds of experiments, starting with Guth, Schmittbeger & Schwarze (1982)

11

Ultimatum Game – Backward Induction Reasoning

• Responder should accept any offer with a positive share, even 1 cent
• Thus, the proposer should offer a tiny part to the responder (say, $99.99 to the proposer, 1 cent to the responder)
• This is not how people play in the lab
• Typical experiment:
• 2 dozens of subjects are brought together and are randomly and anonymously matched in pairs
• In each pair, the game is played once
• New random matching in the next round

12

Ultimatum Game – Observed Behavior in the Lab

• Modal offer is 50%
• Median offer is about 40%
• Offers below 10% are rare
• Proposals that give responders less than 20% are often rejected (and participants often show signs of anger & disgust)
• Results are similar also when playing for large stakes �(in poor countries)
• Somewhat lower rate of rejections; similar behavior of proposers

13

Possible Explanations for Proposers’ Behavior

1. Subjects fail to do backward induction
2. Subjects maximize payoff other than their own material payoffs: either altruism or fairness (or a wish to avoid shame)
3. Subjects may (correctly) fear that responders reject low offers
1. “1.” seems unlikely given the simplicity of the game (& surveying responders)
2. How can we differ “2.” from “3.”?
• Dictator game: A player decided how to divide a sum of money with another player. Result: median partner’s allocation is 25%
• If a player gets the role of proposer due to winning a competition (e.g., solving a puzzle faster), offers are 10% lower
3. proposers’ behavior is due to a combination of correctly anticipating proposers’ responses, altruism and fairness concerns
4. Responders are happy to give up small offers in order to punish unfair proposers

​

​

​

14

Very complex Trees (Chess)

• Chess is a very long perfect information sequential game
• Players (human and AI) can’t apply backward-induction for the whole tree
• Players combine a limited backward induction for a couple moves with heuristics to evaluate chess positions (non-terminal nodes in the tree)
• Success in such games combine both the general game theory principal of backward induction and the game-specific experience-induced heuristics
• It is beneficial to put yourself in the opponent’s shoes, understand opponent’s incentives, and trying to predict the opponent’s moves

15

Case study: 1984 US College Football Orange Bowl

• 4^th quarter, Nebraska was behind 31-17
• Tie-breaking rule is in favor of Nebraska (but this is a less satisfactory win)
• College football: scoring a touchdown yields 6 points + a choice between trying to obtain :
• 1 point by the easier option of kicking a goalpost (play it safe), or
• 2 points by passing the ball into the end zone (risky option)
• Nebraska's coach chose:
• 1^st touchdown: 1 point by the easier goalpost (outcome becomes 31-24)
• 2^nd touchdown: risky option, which failed (game ending 31-30)

​

​

16

Case Discussion: 1984 Orange Bowl

• Nebraska’s coach should have taken the risk in the 1^st touchdown (and, if succeeding, playing it safe in the 2^nd touchdown):
• If Nebraska succeeds in both attempts, or only succeeds in the two-point attempt, then the order doesn’t matter
• If Nebraska fails the two-point attempt:
• Looses in the original order
• Can still try another two-point attempt in the 2^nd touchdown
• General insight: If you have to take some risk, it is often better to do so as quickly as possible
• E.g., in Tennis, take more risk in the 1^st serve, and playing it safe in the 2^nd serve

​

17

Home Assignment 2

Submission till Wednesday late evening

1. How to play a variant of 21-flags with the player taking the last flag losing (instead of winning)
2. Translate a verbal description of an entree game into a tree, and find the backward-induction equilibrium
3. Find the unique backward-induction� equilibrium in the following “centipede”� game (first number in each bracket�is the payoff to P1=Player 1, �second number is the payoff to �P2=Player 2)

18

Discussing Home Assignment 1: Questions 1-3

• Solutions to home assignment 1 in my web site (below the slides).
• Winning by losing/waiting in the 3 shooters puzzle
• Mimicking opponent tactic in the coins in round table puzzle
• Rock-Paper-Scissors Challenge:
• Randomizing in your head is difficult
• So is fooling the AI
• Many excellent answers, it was difficult to choose a single one for the 1 point bonus
• Bonus: Esther (using US Constitution’s length of words for effective pseudo randomization)

​

​

19

The 2/3 Competition: Results (27 Bids)

1 bonus point to the final grade : Esther: winning bid (16).

Bonuses for subjectively best arguments + almost winning: Elena N., Peter L.

20

Subjectively Best Argument (1)

Esther (16):

• Identifies Game as Keynesian beauty contest
• Ask 2 AI bots for recommendation (18-24)
• Hetrogenous model of class:
• 50% - rely on AI (21)
• 25% - choose Nash equilibrium (1)
• 25%- choose randomly (50)
• Average is 24, 2/3 of this is 16

​

​

21

Subjectively Best Argument (2)

Yelena N. (15):

• Lecture 1 was attended by 29 of 39
• Hetrogenous model of class:
• 10 people (those who didn’t attend) - Level 1 (33)
• 14 people - Level 2 (22)
• 14 people - Best reply to 2/3 Level-2 and 1/3 level 1 (17)
• Average is 23, 2/3 of this is 15

​

​

22

Subjectively Best Argument (3)

Peter (15)

• Hetrogenous model of class
• 25 other students in WhatsApp group
• 10 smart-ish students: average 23 (15-32, levels 1-3)
• 5 overthinkers: average 10 (levels >3, 5-14)
• 6 randoms/vibes: average 48 (35-67)
• 4 Tryhards (close to Nash equilibrium: average 2
• Average of class: 23
• 2/3 of average: 15

​

​

​

23

The 2/3 Competition: Analysis

• It’s often called (Keynesian) beauty contest in the academic game theory literature
• We will discuss the reasons for this in presentation 4
• The following paper presents an excellent analysis of the game and how different populations play it:

One, Two, (Three), Infinity, ... : Newspaper and Lab Beauty-Contest Experiments, BOSCH –DOME, MONTALVO, NAGEL & SATORRA

• https://www.upf.edu/documents/8394861/8967210/boschetalAER2002.pdf/bd0a2012-563c-7db9-b36a-eff29cf50897

24

Sample Exam Questions (1)

25

Sample Exam Questions (2)

26

Sample Exam Questions (3)

27

Conclusion

• Various strategic interactions can be modeled by sequential games with perfect information
• Such games can be described as trees, and solved by backward induction
• Typically, a unique backward-induction equilibrium
• People can learn to apply backward induction, at-least in relatively simple games
• Deviations from backward-induction behavior in the ultimatum game are due to a combination of anticipating the responders’ behavior (rejecting low offers due to disgust/anger) and altruism/fairness
• Insights:
• Look forward and reason backward
• In long/complex games, combine backward reasoning with game-specific heuristics
• If you have to take some risk, it is often better to do so as quickly as possible

​

​

​

​

​

​

28