Game Theory - A Very Short Introduction

Game Theory - A Very Short Introduction

Summary

Here is a summary of "Game Theory: A Very Short Introduction" by Ken Binmore:

• Chapter 1: The name of the game. This chapter introduces game theory as the study of strategic interaction between rational individuals. It explains that a "game" can refer to any situation where people interact, from courtship to economics to international politics. The chapter emphasizes that game theory works best when people behave rationally, though it can also explain the behavior of mindless animals or companies eliminated by market forces if they act irrationally. It also introduces the concept of utility to measure players' preferences and discusses how Nash equilibrium, where all players make the best reply to others' strategies, is a fundamental concept.

• Chapter 2: Chance. This chapter delves into the role of chance and mixed strategies in game theory, where players randomize their choices to keep opponents guessing. It explains that even if players don't consciously randomize, their behavior can be effectively random from an opponent's perspective. The chapter discusses how mixed Nash equilibria arise when players adjust their strategies to make their opponents indifferent between choices, sometimes leading to seemingly paradoxical outcomes like in the Good Samaritan Game or voting scenarios. It also touches upon Von Neumann's minimax theorem, which applies to two-person, zero-sum games and states that players should aim to maximize their minimum possible payoff.

• Chapter 3: Time. This chapter explores games where the timing of moves is crucial, such as Chess or Poker, which can be represented in extensive form as game trees. It introduces backward induction as a method to solve finite games of perfect information by working backward from the end of the game, determining the best choices at each step. The chapter discusses concepts like subgame-perfect equilibrium, where strategies are optimal not just for the whole game but for every possible subgame, and common knowledge, where all players know something, know that everyone else knows it, and so on. It also touches upon the Chain Store paradox, highlighting complexities when a player's rationality is refuted by an unexpected move.

• Chapter 4: Conventions. This chapter discusses how conventions, or commonly accepted ways of behaving, help solve equilibrium selection problems in games with multiple Nash equilibria, like the Driving Game. It introduces Schelling's concept of focal points, which are solutions people tend to converge on based on contextual cues, even without explicit agreement. The chapter emphasizes that many societal rules, including language and money, are conventions that evolved because they coordinate behavior on an equilibrium. It also explores how inefficient conventions can arise and persist, as illustrated by Schelling's Solitaire model of segregation, and discusses social dilemmas like the Tragedy of the Commons, where individual incentives conflict with collective well-being.

• Chapter 5: Reciprocity. This chapter focuses on reciprocity as a key mechanism for sustaining cooperation in repeated interactions. It explains that in indefinitely repeated games, like the Prisoner's Dilemma, cooperative strategies such as GRIM (cooperate until the opponent defects, then defect forever) can form Nash equilibria if players value future payoffs enough. The folk theorem is introduced, suggesting that any mutually beneficial outcome can be supported as an equilibrium in a sufficiently long-term relationship with reliable monitoring and punishment for deviations. The chapter also discusses TIT-FOR-TAT, its successes and limitations, and how emotions like anger can serve as commitment devices to enforce reciprocal behavior.

• Chapter 6: Information. This chapter deals with games of imperfect information, where players do not fully know what has happened or what others know, using the concept of information sets to model this uncertainty. Poker is presented as the archetypal game of imperfect information, where bluffing and reading opponents are key. The chapter explains Harsanyi's contribution of transforming situations with incomplete information (where players may have different types, preferences, or beliefs) into games of imperfect information by introducing a "typecasting" chance move. It also explores how costly signals can be used by players to credibly convey their type or intentions, as in the Handicap Principle observed in biology.

• Chapter 7: Auctions. This chapter introduces mechanism design, the process of creating rules and incentives to align agents' behavior with a principal's goals, particularly in situations with information asymmetry. Auctions are highlighted as a successful application, designed to make bidders reveal their true valuations by putting their money where their mouths are. Various auction types are described, including English, Dutch, first-price sealed-bid, and Vickrey auctions, and the chapter explains the revenue equivalence theorem, which states that under certain conditions, these auction types yield the same average revenue for the seller. The chapter also discusses the "winner's curse" in common-value auctions, where the winner may overpay due to overly optimistic estimates.

• Chapter 8: Evolutionary biology. This chapter applies game theory to evolutionary biology, where fitness (average number of extra children carrying a trait) is analogous to utility, and behavioral traits are strategies. It explains that natural selection can lead to animals behaving as though they are rational players, with replicators (like genes) that confer higher fitness becoming more prevalent. The concept of an Evolutionarily Stable Strategy (ESS) is introduced as a strategy that, if adopted by a population, cannot be invaded by any alternative mutant strategy. The chapter discusses examples like the Hawk-Dove game (and its relation to the Prisoner's Dilemma and Chicken), kin selection (Hamilton's rule explaining cooperation among relatives), and the evolution of cooperation through reciprocal altruism in unrelated individuals.

• Chapter 9: Bargaining and coalitions. This chapter distinguishes between noncooperative game theory (which explains cooperation from strategic choices) and cooperative game theory (which assumes players can make binding agreements). The Nash program aims to bridge this by modeling bargaining itself as a noncooperative game. It introduces the Nash bargaining solution, which predicts outcomes based on players' risk attitudes and the status quo, and Rubinstein's alternating-offers model, which provides a noncooperative foundation for it, emphasizing the role of patience. The chapter also explores coalition formation, discussing concepts like the core (outcomes no coalition can improve upon for all its members) and the Shapley value (an average of a player's marginal contributions to all possible coalitions).

• Chapter 10: Puzzles and paradoxes. This chapter addresses common misunderstandings and fallacies in game theory, often arising when intuition clashes with equilibrium arguments. It debunks several fallacies related to the Prisoner's Dilemma, such as the misapplication of Kant's categorical imperative or the "fallacy of the twins" which wrongly assumes players' choices are not independent. The chapter also tackles Newcomb's paradox, showing its apparent contradiction arises from flawed assumptions about the game structure, and clarifies the surprise test paradox by highlighting the importance of correctly defining the game being analyzed. Finally, it discusses the role of common knowledge and its implications for coordination, as seen in the "three old ladies" puzzle and the Email Game.

Notes

Chapter 1: The name of the game

What is a game?

• A "game" can refer to any situation where people interact, from courtship to economics to international politics
• Game theory is concerned with situations where individuals' choices are interdependent, meaning the outcome for each participant depends not only on their own actions but on the actions of others as well
• Game theory works best when people behave rationally, though it can also explain the behavior of mindless animals or companies eliminated by market forces if they act irrationally.

Essential tools and concepts:

• Payoffs represent the outcomes for players, which don't necessarily have to be monetary.
• The theory of revealed preference - basis for understanding player motivation
• Utility is a way to numerically represent preferences, derived from observing choices rather than making psychological assumptions
• Von Neumann's method for measuring utility by assessing the risks a person is willing to take
• Nash equilibrium is where all players make the best reply to others' strategies, meaning no player has an incentive to unilaterally change their strategy.

The 3 key points:

1. Definition and Scope of Game Theory
2. Rationality, Utility, and Revealed Preference
3. Nash Equilibrium as a Central Concept

Mathematical Underpinnings of Nash Equilibrium

"A Nash equilibrium occurs when all the players are simultaneously making a best reply to the strategy choices of the others." Mathematically, this is built on a few components:

1. Players, $ N = \{ 1, 2, ..., n \} $

2. Strategy sets $ S_i $ for each player $ i \in N $. A strategy $ s_i \in S_i $ is a complete plan of action for player i, specifying what they will do in every possible situation or contingency that might arise in the game.

(Note: for toy games, these are often small, discrete sets: heads/tails, slower/faster. Strategies can become a very complicated function for complex games.)

3. Strategy profile $ s = (s_1, s_2, \dots, s_n) $ is a combination of strategies, one for each player.

4. Payoff functions (utility functions): each player $ i \in N $ has a payoff/utility function $ u_i : S \rightarrow \mathbb{R} $

Now we can define Nash equilibrium more formally as a strategy profile $ s* = (s_1*, s_2*, \dots, s_n*) $ that satisfies the following condition for every player $ i \in N $ and for every strategy $ s_i \in S_i $ available to player i:

$ u_i( s_1*, \dots, s_{i-1}*, s_i*, s_{i+1}*, \dots, s_n*) \geq u_i ( s_1*, \dots, s_{i-1}*, s_i, s_{i+1}*, \dots, s_n*) $

In simple terms: No player i can improve their own payoff by unilaterally changing their strategy from si*​ to any other strategy si​, given that all other players stick to their strategies in s*.

Player i's star strategy is a "best reply" to the other players' star strategies

Complexities of Modeling with Game Theory

Game theory (esp. introductory game theory) uses several abstractions and simplifications to model the complexities of the real world:

• People:
  • Rationality - often assumed to be rational, meaning they consistently choose actions that maximize their own utility, given their beliefs about the game and other players' actions. The term "rational" is about consistency of choice, not about wisdom or lack of emotion.
  • Utility functions - individual preferences, values, risk attitudes, and motivations can be condensed into a utility function. This doesn't require knowing what is in someone's head, it requires observing consistent choices. (Risk aversion captured by response to increasing amounts of money or differing probabilities of outcomes.)
  • Player types - to deal with incomplete information (other players don't know each other's exact payoffs or private information), game theory models players as having different "types". A type encapsulates all of a player's private information (preferences, beliefs about other players' types, etc.). Game starts with chance move that assigns a type to each player. This is a way to bring uncertainty about others into a formal model.

• All Possible Choices:
  • Set of all possible choices for a player is exactly their strategy set $ S_i $
  • This requires a modeler to carefully define the boundaries and rules of the game.
  • Think of it like, if you had to tell a machine how to play for you while you go to the restroom, what rules would you give it? What about corner cases? (Runaway trading algorithms)
  • Toy games can simplify complex real-world choices into more manageable discrete outcomes and strategies, to make analysis tractable.
  • A strategy is a complete plan of action. (Chess has astronomical number of moves, but concept allows for formal definition.)

• The universe of information that affects the game
  • Rules - the fundamental structure, including who the players are, what actions they can take, and when they can take them, and what the outcomes are, is assumed to be defined, and often common, knowledge
  • Common knowledge - crucial assumption, often implicit, is that the rules of the game and the rationality of the players is common knowledge. Everyone knows it, everyone knows that everyone knows it, etc. Avoids infinite they think i think they think...
  • Information sets - imperfect information happens when players don't know previous moves of other players (simultaneous-move games, or hidden action). This info is modeled with information sets.
  • An information set groups decision nodes for a player when they cannot distinguish which node they are actually at. A strategy specifies one action per information set, not per node.
  • Example: Matching Pennies
  • Incomplete information and types - Harsanyi's framework converts games of incomplete information (where players are uncertain about some fundamental aspect of the game, like others' payoffs) into games of imperfect information by introducing player types and prior probability distributions over these types.

Matching Pennies

Matching Pennies is a classic, simple game used in game theory to illustrate fundamental concepts of conflict, strategy, and equilibrium.

Basic Setup:

• The game involves two players, typically named Alice and Bob. Each player has a coin and simultaneously chooses to show either "heads" (H) or "tails" (T).

• Alice wins if both coins show the same face (both heads or both tails).

• Bob wins if the coins show different faces (one heads and one tails).

• Payoffs: The outcomes are directly opposed. If Alice wins, Bob loses, and vice versa. This makes it a game of pure conflict.

• The book often represents payoffs with icons (thumbs-up for winning, thumbs-down for losing) or with numerical utilities, such as +1 for winning and -1 for losing.

• If we assign +1 to the winner and -1 to the loser, the payoff table looks like this (Alice's payoff is listed first, then Bob's):

|              | Bob: Heads | Bob: Tails |
| :----------- | :--------- | :--------- |
| Alice: Heads | (+1, -1)   | (-1, +1)   |
| Alice: Tails | (-1, +1)   | (+1, -1)   |

Zero-Sum Game:

• Because the players' interests are diametrically opposed (one's gain is exactly the other's loss), the sum of their payoffs in any outcome is zero (e.g., +1 + (-1) = 0). This is why it's called a zero-sum game.

Strategies and equilibrium: Pure strategies:

• Pure strategies (where each player chooses a single action and sticks to it) - each player has two pure strategies: choose Heads or choose Tails.
• No pure strategy Nash equilibrium - you cannot find a Nash equilibrium in Matching Pennies using only pure strategies
• Binmore explains by noting that if you circle the best outcomes in the payoff table for each player, no cell will have both payoffs circled for both players.
• Continuous cycle of best responses, with no stable outcome when both players are simultaneously playing their best reply to the other.

Strategies and equilibrium: Mixed strategies:

• The resolution to this problem, and the way to find a Nash equilibrium, is through "mixed strategies." A mixed strategy involves players randomizing their choice of pure strategy.
• In Matching Pennies, the intuitive solution, and indeed the Nash equilibrium, is for each player to choose Heads with 50% probability and Tails with 50% probability, independently and unpredictably.
• If both players adopt this 50/50 mixed strategy, each player will win, on average, half the time. Given that the opponent is randomizing 50/50, a player cannot improve their own outcome by choosing any other strategy (pure or mixed). For example, if Bob plays Heads 50% of the time and Tails 50% of the time, Alice gets an expected payoff of 0 whether she plays Heads, Tails, or any mix of her own.
• This randomization keeps the opponent guessing, which is the core of the strategy in such a game.

Role in Illustrating Game Theory Concepts:

• Conflict vs. Cooperation: It's presented as a game of pure conflict, contrasting with games of pure coordination like the Driving Game (where both players want to coordinate on the same action, e.g., driving on the same side of the road).

• Minimax Theorem: Von Neumann's minimax theorem, which applies to two-person, zero-sum games, finds its solution in Matching Pennies where players use their maximin strategy (maximizing their minimum guaranteed payoff), which corresponds to the 50/50 randomization.

• Learning to Play an Equilibrium: The book discusses how boundedly rational players (robots in an example) might learn to play the mixed strategy equilibrium in Matching Pennies over time by adjusting their play based on past frequencies of the opponent's moves. The frequencies of playing heads or tails converge towards the 50/50 equilibrium.

• Information Sets: When discussing games in extensive form (tree form), Matching Pennies is used to illustrate "information sets." If one player moves first but the second player doesn't know the first player's move, the second player's decision nodes are grouped in an information set, signifying their lack of knowledge. This makes the sequential game strategically equivalent to a simultaneous-move game.

• Surprise Test Paradox: In a variation, the surprise test paradox is compared to a version of Matching Pennies where a teacher (Alice) chooses a day for a test, and a pupil (Bob) predicts the day. The optimal strategy involves both randomizing.

• In essence, Matching Pennies is a foundational "toy game" in game theory. Its simplicity allows for a clear illustration of why mixed strategies are necessary, the nature of zero-sum conflict, and how rational (or even evolving) players might approach situations where unpredictability is key to not being exploited.

Mixed Pennies - A Few Examples

A few examples given in the book of an analogous Matching Pennies game:

• Sherlock Holmes and Professor Moriarty: Binmore mentions that Holmes and Moriarty played a version of Matching Pennies on the way to their confrontation at the Reichenbach Falls. Holmes had to decide at which train station to disembark, while Moriarty had to decide at which station to lie in wait.

• Accountants and Auditors: A real-life counterpart is seen with dishonest accountants deciding when to cheat and their auditors deciding when to inspect the books.

• Edgar Allan Poe's "The Purloined Letter": Poe describes a boy who consistently wins at Matching Pennies by supposedly intuiting his opponent's thoughts through imitation. Binmore points out the flaw: both players can't successfully use this trick simultaneously.

Why Bother with Toy Games?

In addition to the need for brevity, sometimes game theory gets a math-light treatment or authors skip details because a high level of abstraction is needed to create generalizable models.

Game theory doesn't aim to perfectly replicate every nuance of a specific real-world situation with all its psychological and informational complexities. Instead, it:

• Identifies key strategic elements.
• Models these elements formally, often simplifying other aspects.
• Analyzes the logical consequences of these modeled interactions under assumptions of rationality.

The power of game theory comes from this ability to strip down complex situations to their strategic core. While "toy games" might seem overly simplistic, they illuminate fundamental strategic principles that can then be applied to understand more complex scenarios.

More advanced mathematical game theory does build significantly more complex models, but the foundational ideas of players, strategies, payoffs, and equilibrium concepts remain central.

Chapter 2: Chance

Chapter 1 introduced Matching Pennies, a game where if Alice knew Bob's move (or vice versa), the predictable player would always lose. This highlighted a problem: in such games of pure conflict, there's no stable outcome if players stick to a single, predictable ("pure") strategy.

Chapter 2 delves into the crucial concept of mixed strategies, where players introduce randomness into decision-making to find equilibria (stable solutions) in cases where pure strategies fail to provide one.

Side note on real-world parallels: random strategies in games may look like a roll of the die, but in real life they look like "keeping others guessing" or "throwing everything at the wall and seeing what sticks". In a simple game like Matching Pennies, the optimal random strategy may seem obvious, but in more complex games, it won't be.

Mixed Strategies and Mixed Nash Equilibrium

A key concept of the mixed strategy Nash equilibria function is the principle of maying the other player indifferent. Binmore puts it this way:

A player will only be willing to randomize between two or more pure strategies if they are indifferent between them... Therefore, in a mixed Nash equilibrium, each players' mixed strategy is chosen precisely to make the OTHER player(s) indifferent between the pure strategies they are randomizing over.

To put this in a more rigorous way, consider a game with N players, $ i \in \{1, 2, \dots, N\} $

Each player i has a finite set of pure strategies $ S_i = \{ s_{i1}, s_{i2}, \dots, s_{i k_i} \} $

A mixed strategy $ \sigma_i $ for player i is a probability distribution over their pure strategies $ S_i $. The set of all mixed strategies for player i is denoted $ \Sigma_i $

If $ p_{ij} $ is the probability that player i plays strategy $ s_{ij} $, then $ \sigma_i = (p_{i1}, p_{i2}, \dots, p_{i k_i}) $

(note that each probability is nonzero $ p_{ij} \geq 0 $ and all probabilities for a given player add up to 1, $ \sum_{j=1}^{k_i} p_{ij} = 1 $)