Game Theory: Comprehensive Notes & Interactive Quiz

What is Game Theory?

Game theory is a branch of mathematics that studies strategic interactions among rational decision-makers. It provides a framework for analyzing situations where the outcome for each participant depends on the choices made by all participants.

Key Concepts in Game Theory

Players: The decision-makers in the game.
Actions/Strategies: The choices available to players.
Payoffs: The rewards or penalties players receive based on the combination of strategies chosen.
Information: What players know when making decisions.
Equilibrium: A state where no player has an incentive to unilaterally change their strategy.

History of Game Theory

While strategic thinking has ancient roots, modern game theory began with mathematician John von Neumann's work in the 1920s. The field expanded significantly when John Nash introduced the concept of Nash equilibrium in the 1950s. Game theory has since been applied to economics, political science, biology, psychology, computer science, and many other fields.

Example: The Prisoner's Dilemma

Two suspects are arrested and separated. Each is given the choice to either cooperate with their accomplice by remaining silent or defect by testifying against the other.

	Prisoner B: Cooperate	Prisoner B: Defect
Prisoner A: Cooperate	-1 -1	-3 0
Prisoner A: Defect	0 -3	-2 -2

In this famous example, each prisoner has a dominant strategy to defect, leading to a worse outcome for both than if they had both cooperated. This illustrates the tension between individual rationality and collective optimality.

Types of Games in Game Theory

1. Cooperative vs. Non-cooperative Games

Cooperative games allow players to form binding commitments and coalitions. The focus is on how groups of players might cooperate to achieve mutual benefits.

Non-cooperative games focus on predicting individual players' strategies and payoffs, assuming players cannot form enforceable agreements outside the rules of the game.

Example: Cooperative Game - Market Coalition

Several small vendors agree to form a coalition to jointly purchase inventory at wholesale prices, reducing costs for all members. The game focuses on how benefits are distributed among coalition members.

Example: Non-cooperative Game - Cournot Competition

Firms in an oligopoly independently and simultaneously decide on production quantities. Each firm's profit depends on the total market supply, which is determined by all firms' production decisions.

2. Zero-sum vs. Non-zero-sum Games

Zero-sum games represent situations where one player's gain equals another player's loss, so the sum of all payoffs is always zero.

Non-zero-sum games represent situations where the sum of payoffs can be positive (win-win) or negative (lose-lose).

Example: Zero-sum Game - Matching Pennies

Two players each choose heads or tails. If choices match, Player 1 wins; if they differ, Player 2 wins.

	Player B: Heads	Player B: Tails
Player A: Heads	1 -1	-1 1
Player A: Tails	-1 1	1 -1

Example: Non-zero-sum Game - Stag Hunt

Two hunters can choose to hunt a stag or a hare. Catching a stag requires cooperation, while each can catch a hare individually.

	Player B: Stag	Player B: Hare
Player A: Stag	4 4	0 3
Player A: Hare	3 0	2 2

3. Simultaneous vs. Sequential Games

Simultaneous games (or static games) are those where players make decisions at the same time, without knowing the choices of other players.

Sequential games (or dynamic games) are those where players make decisions in a specific order, with later players having some information about earlier players' choices.

Example: Sequential Game - Entry Deterrence

An incumbent firm decides whether to invest in excess capacity to deter entry. A potential entrant observes this decision and then decides whether to enter the market.

4. Perfect vs. Imperfect Information Games

Perfect information games are those where all players know the complete history of all moves made so far when making any decision (e.g., chess).

Imperfect information games are those where players may not know all previous moves when making decisions (e.g., poker).

5. Complete vs. Incomplete Information Games

Complete information games are those where all players know the strategies and payoffs available to other players.

Incomplete information games are those where players may not know other players' payoffs or available strategies.

Example: Incomplete Information - Auction

In a first-price sealed-bid auction, each bidder values the item differently (private value) and must submit a bid without knowing others' valuations. The highest bidder wins and pays their bid amount.

6. Finite vs. Infinite Games

Finite games have a fixed, known number of players, strategies, and outcomes.

Infinite games can have infinite players, strategies, or possible outcomes.

7. Symmetric vs. Asymmetric Games

Symmetric games are those where all players have identical strategy sets and the payoffs depend only on the strategies employed, not on which player chooses which strategy.

Asymmetric games are those where different players have different strategy sets or payoffs.

Game Theory Solution Methods

1. Dominant Strategy Solution

A dominant strategy is one that provides a higher payoff than any other strategy, regardless of what strategies other players choose.

To find a dominant strategy solution:

For each player, examine whether any strategy yields a strictly better payoff against all possible strategy combinations of other players.
If both players have dominant strategies, the combination of these strategies is the dominant strategy equilibrium.

Example: Dominant Strategy in Prisoner's Dilemma

In the Prisoner's Dilemma, "Defect" is a dominant strategy for both players:

For Prisoner A:

If B cooperates: Defect yields 0 vs. Cooperate yields -1
If B defects: Defect yields -2 vs. Cooperate yields -3

For Prisoner B:

If A cooperates: Defect yields 0 vs. Cooperate yields -1
If A defects: Defect yields -2 vs. Cooperate yields -3

Since "Defect" always yields a better payoff regardless of the other player's choice, it's the dominant strategy for both players, leading to the equilibrium (Defect, Defect).

2. Nash Equilibrium

A Nash equilibrium is a set of strategies, one for each player, such that no player can benefit by unilaterally changing their strategy while others keep theirs unchanged.

To find Nash equilibria:

For each strategy combination, check if any player could improve their payoff by unilaterally switching to a different strategy.
If no player can improve by switching, that combination is a Nash equilibrium.

Example: Nash Equilibrium in Battle of the Sexes

A couple wants to spend the evening together, but one prefers the opera while the other prefers a football game.

	Player B: Opera	Player B: Football
Player A: Opera	2 1	0 0
Player A: Football	0 0	1 2

This game has two pure strategy Nash equilibria: (Opera, Opera) and (Football, Football). At (Opera, Opera), neither player wants to unilaterally switch, as this would result in a payoff of 0 instead of 2 for Player A or 1 for Player B.

3. Mixed Strategy Equilibrium

A mixed strategy is a probability distribution over a player's pure strategies.

To find a mixed strategy equilibrium:

Set up equations where each player is indifferent between their pure strategies, given the mixed strategy of the other player.
Solve these equations to find the probability distributions that constitute the equilibrium.

Example: Mixed Strategy in Matching Pennies

Recall the matching pennies game where Player 1 wants to match, and Player 2 wants to mismatch:

Let p be the probability that Player 1 plays Heads, and q be the probability that Player 2 plays Heads.

For Player 2 to be indifferent:

Expected utility from Heads = Expected utility from Tails
p(-1) + (1-p)(1) = p(1) + (1-p)(-1)
-p + (1-p) = p - (1-p)
-p + 1 - p = p - 1 + p
1 - 2p = 2p - 1
2 = 4p
p = 1/2

For Player 1 to be indifferent:

Expected utility from Heads = Expected utility from Tails
q(1) + (1-q)(-1) = q(-1) + (1-q)(1)
q - (1-q) = -q + (1-q)
q - 1 + q = -q + 1 - q
2q - 1 = 1 - 2q
4q = 2
q = 1/2

So the mixed strategy Nash equilibrium is for both players to play Heads with probability 1/2 and Tails with probability 1/2.

4. Backward Induction

Backward induction is a method used to solve sequential games, working backwards from the end of the game to determine optimal strategies.

To apply backward induction:

Start at the final decision nodes and determine the optimal action for the player making the last move.
Move back to the previous decision nodes, assuming that later players will take their optimal actions.
Continue until reaching the initial node.

Example: Backward Induction in Entry Game

Revisiting the entry deterrence game:

Using backward induction:

If Incumbent invests, Entrant's best response is to stay out (-1 < 0).
If Incumbent doesn't invest, Entrant's best response is to enter (2 > 0).
Moving back to Incumbent's decision: If it invests, it gets a payoff of 2; if it doesn't invest, it gets a payoff of 1.
Therefore, Incumbent's optimal strategy is to invest, and the Entrant's response is to stay out.

5. Subgame Perfect Equilibrium

A subgame perfect equilibrium is a refinement of Nash equilibrium that requires the strategy profile to constitute a Nash equilibrium in every subgame of the original game.

Backward induction finds subgame perfect equilibria in finite games of perfect information.

6. Evolutionary Stable Strategy

An evolutionarily stable strategy (ESS) is a strategy which, if adopted by a population, cannot be invaded by any alternative strategy.

For a strategy S* to be an ESS:

It must be a Nash equilibrium strategy.
If there's an alternative best response S to S*, then E(S*,S*) > E(S,S), where E denotes expected payoff.

7. Bayesian Equilibrium

A Bayesian equilibrium is a Nash equilibrium in a game with incomplete information, where players have beliefs about the types of other players.

8. The Core and Shapley Value (Cooperative Game Theory)

The core is the set of allocations that cannot be improved upon by any coalition of players.

The Shapley value allocates payoffs to players based on their marginal contributions to all possible coalitions.

Shapley value for player i:
φᵢ = Σ [|S|! × (n-|S|-1)! / n!] × [v(S∪{i}) - v(S)]

where S ranges over all coalitions not containing player i, |S| is the number of players in S, n is the total number of players, and v is the characteristic function of the game.

Applications of Game Theory

1. Economics

Game theory has revolutionized economics by providing tools to analyze strategic interactions in markets, auctions, bargaining, and more.

Example: Oligopoly Pricing

Consider two firms (A and B) deciding whether to charge a high or low price:

	Firm B: High Price	Firm B: Low Price
Firm A: High Price	50 50	10 70
Firm A: Low Price	70 10	30 30

This is a Prisoner's Dilemma scenario applied to pricing. Despite the mutual benefit of both charging high prices, the Nash equilibrium is for both to charge low prices.

2. Political Science

Game theory models voting behavior, international relations, arms races, and political negotiations.

Example: Nuclear Deterrence

Two superpowers must decide whether to build nuclear weapons or remain non-nuclear. This can be modeled as a game where the Nash equilibrium often involves mutual armament, though mutual disarmament would be preferable.

3. Biology

Evolutionary game theory explains behaviors in animal populations, including territorial disputes, mating strategies, and cooperation.

Example: Hawk-Dove Game

Animals competing for resources can adopt aggressive (Hawk) or passive (Dove) strategies. The equilibrium often involves a mixed population of hawks and doves.

4. Computer Science

Game theory principles are used in network design, security, artificial intelligence, and algorithm development.

Example: Security Games

Defenders must allocate limited resources to protect multiple targets, while attackers choose which targets to attack. Game theory helps identify optimal mixed strategies for resource allocation.