Game Theory — Non-Cooperative Games

1. Introduction to Game Theory

Game theory is the study of strategic decision-making. It analyzes situations where the outcome for each participant (or "player") depends not only on their own actions but also on the actions of others. In essence, it's the mathematics of conflict and cooperation between rational decision-makers.

The core idea is that each player anticipates the actions of other players and chooses their own strategy accordingly. This anticipation is crucial because a player's best move often depends on what they believe their opponent will do.

Game theory has applications in a vast array of fields, including economics, political science, biology, psychology, and computer science. In economics, it's particularly useful for understanding market structures, bargaining, auctions, and strategic interactions between firms.

2. Types of Games

Games can be classified based on several criteria:

2.1. Cooperative vs. Non-Cooperative Games

This is a fundamental distinction. In cooperative games, players can form binding agreements (coalitions) and coordinate their strategies. The focus is on what groups of players can achieve together.

In non-cooperative games, players cannot form binding agreements. Each player acts independently to maximize their own payoff, assuming other players will do the same. The analysis focuses on individual strategies and outcomes. This e-book will focus exclusively on non-cooperative games.

2.2. Simultaneous vs. Sequential Games

In simultaneous games, players choose their actions at the same time, or without knowing the other player's choice. A common representation is the "normal form" or "strategic form" of a game.

In sequential games, players move in a specific order, and later players know the actions taken by earlier players. These are often represented using "extensive form" or game trees.

2.3. Perfect vs. Imperfect Information

A game has perfect information if each player, when making a decision, knows all previous moves made by all players. Chess is a classic example.

A game has imperfect information if players do not know all previous moves. For instance, in simultaneous games, players don't know the other's move. In sequential games with imperfect information, a player might not know which of several possible past moves their opponent made.

2.4. Zero-Sum vs. Non-Zero-Sum Games

In zero-sum games, the total gains of the winners minus the total losses of the losers equal zero. What one player wins, the other player loses. Poker is a common example.

In non-zero-sum games, the sum of gains and losses can be positive or negative. Players can simultaneously benefit or harm each other. Most real-world economic interactions are non-zero-sum.

3. Core Concepts in Non-Cooperative Game Theory

Understanding non-cooperative games requires grasping several key concepts:

3.1. Players

The decision-makers in the game. They are assumed to be rational, meaning they aim to maximize their own utility or payoff.

3.2. Strategies

A strategy for a player is a complete plan of action that specifies what they will do in every possible situation they might face in the game. This includes actions at every node in a sequential game or a pure choice in a simultaneous game.

3.3. Payoffs

The outcomes or rewards that players receive for each combination of strategies chosen by all players. Payoffs are typically represented numerically and reflect the players' preferences.

3.4. Information Set

In games with imperfect information, an information set for a player is a collection of nodes in the game tree where that player has to move, and they cannot distinguish between these nodes. They don't know exactly which node they are at.

3.5. Equilibrium Concept

An equilibrium is a state in a game where no player has an incentive to unilaterally change their strategy, given the strategies of the other players. It represents a stable outcome.

4. Nash Equilibrium

The most famous and widely used equilibrium concept in non-cooperative game theory is the Nash Equilibrium, named after John Nash.

Definition: A set of strategies (one for each player) is a Nash Equilibrium if no player can improve their payoff by unilaterally changing their strategy, assuming all other players keep their strategies unchanged.

4.1. Nash Equilibrium in Pure Strategies

In a pure strategy Nash Equilibrium, each player chooses a single, specific strategy. We can identify this by examining the payoff matrix of a simultaneous game.

Example: The Prisoner's Dilemma

Two suspects, Alice and Bob, are arrested for a crime. The police do not have enough evidence to convict them on the main charge but have enough to convict them on a lesser charge. They are interrogated separately and cannot communicate. Each prisoner has two choices: Confess (implicate the other) or Remain Silent.

The payoffs (in years of imprisonment) are:

• If both confess: Each gets 5 years.
• If Alice confesses and Bob remains silent: Alice gets 0 years, Bob gets 10 years.
• If Alice remains silent and Bob confesses: Alice gets 10 years, Bob gets 0 years.
• If both remain silent: Each gets 1 year.

We can represent this in a payoff matrix (where lower numbers are better, representing fewer years in prison):

Alice \ Bob	Bob
	Confess	Silent
Alice	(5, 5)	(0, 10)
Silent	(10, 0)	(1, 1)

Analysis for Alice:

• If Bob confesses, Alice is better off confessing (5 years) than remaining silent (10 years).
• If Bob remains silent, Alice is better off confessing (0 years) than remaining silent (1 year).

Confessing is Alice's dominant strategy – it's the best choice regardless of what Bob does.

Analysis for Bob:

• If Alice confesses, Bob is better off confessing (5 years) than remaining silent (10 years).
• If Alice remains silent, Bob is better off confessing (0 years) than remaining silent (1 year).

Confessing is also Bob's dominant strategy.

Nash Equilibrium: Since both players have a dominant strategy to confess, the outcome where both confess (5, 5) is a Nash Equilibrium. Neither player can improve their situation by unilaterally changing their strategy. If Alice is confessing, Bob cannot improve by switching from confessing to silent (he'd get 10 instead of 5). If Bob is confessing, Alice cannot improve by switching from confessing to silent (she'd get 10 instead of 5).

The Dilemma: Notice that the Nash Equilibrium (Confess, Confess) results in a worse outcome for both players (5 years each) than if they had both remained silent (1 year each). This highlights the conflict between individual rationality and collective well-being.

4.2. Finding Pure Strategy Nash Equilibrium

To find a pure strategy Nash Equilibrium in a 2x2 payoff matrix:

1. For each column (player 2's strategy), find the row (player 1's strategy) that gives player 1 the highest payoff. Mark this payoff.
2. For each row (player 1's strategy), find the column (player 2's strategy) that gives player 2 the highest payoff. Mark this payoff.
3. Any cell where both payoffs are marked is a pure strategy Nash Equilibrium.

Example: Battle of the Sexes

A couple wants to go out. One prefers the opera, the other prefers a football game. They both prefer going out together over going alone. Let's say Player 1 (Wife) prefers Opera (O), Player 2 (Husband) prefers Football (F).

Wife \ Husband	Husband
	Opera (O)	Football (F)
Opera (O)	(3, 2)	(1, 1)
Football (F)	(0, 0)	(2, 3)

Analysis:

• Wife's best response: If Husband chooses Opera, Wife prefers Opera (3 > 1). If Husband chooses Football, Wife prefers Football (2 > 0).
• Husband's best response: If Wife chooses Opera, Husband prefers Opera (2 > 1). If Wife chooses Football, Husband prefers Football (3 > 0).

Let's mark the best responses:

Wife \ Husband	Husband
	Opera (O)	Football (F)
Opera (O)	(3, 2)	(1, 1)
Football (F)	(0, 0)	(2, 3)

The cells with double underlines are (Opera, Opera) and (Football, Football). These are the two pure strategy Nash Equilibria. In (O, O), Wife gets 3, Husband gets 2. Neither wants to switch. If Wife switches to F, she gets 0. If Husband switches to F, he gets 1. In (F, F), Wife gets 2, Husband gets 3. Neither wants to switch. If Wife switches to O, she gets 1. If Husband switches to O, he gets 0.

This game has two Nash Equilibria, illustrating that multiple stable outcomes are possible.

4.3. Nash Equilibrium in Mixed Strategies

A mixed strategy involves a player randomizing between two or more pure strategies with certain probabilities. This is often used when no pure strategy Nash Equilibrium exists, or to find additional equilibria.

A player uses a mixed strategy to make the other player indifferent between their own pure strategies. This indifference is key to finding the equilibrium.

Example: Matching Pennies

Two players, Alice and Bob, each choose to show a penny either Heads (H) or Tails (T). Alice wins if the pennies match (both H or both T). Bob wins if they don't match (one H, one T).

Alice \ Bob	Bob
	Heads (H)	Tails (T)
Heads (H)	(1, -1)	(-1, 1)
Tails (T)	(-1, 1)	(1, -1)

Analysis for Pure Strategies:

• If Alice plays H, Bob prefers T (payoff 1 vs -1).
• If Alice plays T, Bob prefers H (payoff 1 vs -1).
• If Bob plays H, Alice prefers T (payoff -1 vs 1).
• If Bob plays T, Alice prefers H (payoff -1 vs 1).

There is no cell where both players are playing their best response simultaneously. Therefore, no pure strategy Nash Equilibrium exists.

Finding Mixed Strategy Nash Equilibrium:

Let Alice play H with probability $p$ and T with probability $(1-p)$.

Let Bob play H with probability $q$ and T with probability $(1-q)$.

For Alice to be willing to mix, she must be indifferent between playing H and T. This means her expected payoff from playing H must equal her expected payoff from playing T, given Bob's strategy $q$.

Expected Payoff for Alice playing H: $E_A(H) = q(1) + (1-q)(-1) = q - (1-q) = 2q - 1$.

Expected Payoff for Alice playing T: $E_A(T) = q(-1) + (1-q)(1) = -q + 1 - q = 1 - 2q$.

Setting $E_A(H) = E_A(T)$: $2q - 1 = 1 - 2q \implies 4q = 2 \implies q = 1/2$.

So, Bob must play H with probability 1/2 and T with probability 1/2 to make Alice indifferent.

For Bob to be willing to mix, he must be indifferent between playing H and T. This means his expected payoff from playing H must equal his expected payoff from playing T, given Alice's strategy $p$.

Expected Payoff for Bob playing H: $E_B(H) = p(-1) + (1-p)(1) = -p + 1 - p = 1 - 2p$.

Expected Payoff for Bob playing T: $E_B(T) = p(1) + (1-p)(-1) = p - (1-p) = 2p - 1$.

Setting $E_B(H) = E_B(T)$: $1 - 2p = 2p - 1 \implies 4p = 2 \implies p = 1/2$.

So, Alice must play H with probability 1/2 and T with probability 1/2 to make Bob indifferent.

The unique Nash Equilibrium in Matching Pennies is that both players play Heads with probability 1/2 and Tails with probability 1/2.

5. Sequential Games and Subgame Perfect Nash Equilibrium (SPNE)

Sequential games involve players moving in turn. These are often represented by game trees (extensive form). A key concept for sequential games is the Subgame Perfect Nash Equilibrium (SPNE).

5.1. Game Trees (Extensive Form)

A game tree consists of:

• Nodes: Decision points for players or chance events.
• Branches: Represent the actions players can take or the outcomes of chance.
• Terminal Nodes: End points of the game, associated with payoffs for each player.
• Information Sets: Groups of nodes where a player doesn't know which node they are at.

5.2. Subgames

A subgame is a part of the larger game that starts at a single decision node and includes all subsequent nodes and branches, with the condition that if a node is in the subgame, all other nodes in the same information set must also be in the subgame.

5.3. Subgame Perfect Nash Equilibrium (SPNE)

Definition: A strategy profile is a Subgame Perfect Nash Equilibrium if it constitutes a Nash Equilibrium in every subgame of the original game.

SPNE is a refinement of the Nash Equilibrium concept. It requires strategies to be optimal not just for the overall game but also for every possible continuation of the game (i.e., every subgame).

5.4. Backward Induction

SPNE is typically found using the method of backward induction, especially in games of perfect information.

Process:

1. Start at the terminal nodes of the game tree (the end).
2. At the last decision nodes (those just before the terminal nodes), determine the optimal action for the player whose turn it is, assuming they will receive the payoffs at the end.
3. Replace these last decision nodes and their subsequent branches with the payoffs resulting from the optimal choice.
4. Move backward to the preceding decision nodes. The player whose turn it is now chooses the action that maximizes their payoff, anticipating the optimal choices that will be made later in the game (as determined in the previous steps).
5. Continue this process until you reach the beginning of the game.

Example: Entry Deterrence Game

An incumbent firm (Incumbent) is in a market. A potential entrant (Entrant) decides whether to Enter or Stay Out. If the Entrant stays out, the payoffs are (Incumbent: 10, Entrant: 0).

If the Entrant enters, the Incumbent faces a choice: Accommodate (share the market) or Fight (engage in a price war).

• If Incumbent Accommodates: Payoffs are (Incumbent: 5, Entrant: 5).
• If Incumbent Fights: Payoffs are (Incumbent: 2, Entrant: 2).

This is a sequential game. The Entrant moves first.

Game Tree Representation:

(Start) -- Entrant --> [Enter] -- Incumbent --> [Accommodate] (5, 5)

--> [Fight] (2, 2)

-- Stay Out --> (10, 0)

Backward Induction:

1. Incumbent's Decision (if Entrant enters): The Incumbent compares payoffs: Accommodate (5) vs. Fight (2). The Incumbent prefers to Accommodate (5 > 2).
2. Entrant's Decision: The Entrant knows that if they enter, the Incumbent will accommodate, resulting in a payoff of 5 for the Entrant. The Entrant compares this to the payoff of staying out (0). Since 5 > 0, the Entrant chooses to Enter.

SPNE Strategy Profile:

• Entrant: Enter
• Incumbent: Accommodate (if Entrant enters)

The SPNE outcome is (Enter, Accommodate), with payoffs (5, 5).

6. Applications and Extensions

6.1. Oligopoly Models

Game theory provides the foundation for analyzing oligopolistic markets where a few firms interact strategically. Models like Cournot (quantity competition), Bertrand (price competition), and Stackelberg (sequential quantity competition) are all rooted in game-theoretic principles.

For instance, the Stackelberg model is a sequential game where one firm (the leader) chooses its output first, and the other firm (the follower) observes this and then chooses its output. Backward induction is used to solve this.

6.2. Bargaining

Models of bargaining, such as the Rubinstein bargaining model, use game theory to analyze how two players divide a surplus when they make alternating offers over time. This involves considering discounting and the threat of breakdown.

6.3. Auctions

Auction theory heavily relies on game theory. Different auction formats (e.g., first-price sealed-bid, second-price sealed-bid, English, Dutch) are analyzed as games where bidders choose their bids strategically based on their private valuations and beliefs about others' valuations.

6.4. Repeated Games

In repeated games, the same stage game is played multiple times. This can lead to different outcomes than in a one-shot game. For example, cooperation can be sustained in a repeated Prisoner's Dilemma through strategies like the "Tit-for-Tat" strategy, where players reward cooperation and punish defection.

The Folk Theorem states that in infinitely repeated games with a sufficiently patient set of players, any feasible and individually rational payoff profile can be sustained as a Nash Equilibrium.

6.5. Evolutionary Game Theory

This branch applies game theory concepts to biological evolution. It studies how strategies evolve within a population based on their fitness (payoffs). Concepts like Evolutionary Stable Strategy (ESS) are central.

7. Limitations of Game Theory

While powerful, game theory has limitations:

• Rationality Assumption: It assumes players are perfectly rational and have complete information about the game structure and payoffs. Real people may deviate due to cognitive biases or emotions.
• Computational Complexity: Finding equilibria in complex games can be computationally intractable.
• Multiple Equilibria: Many games have multiple Nash Equilibria, making it difficult to predict a unique outcome (as seen in Battle of the Sexes).
• Predictive Power: While it describes equilibrium behavior, it doesn't always perfectly predict actual behavior, especially in novel or complex situations.

8. Conclusion

Non-cooperative game theory provides a rigorous framework for analyzing strategic interactions where binding agreements are not possible. Concepts like Nash Equilibrium and Subgame Perfect Nash Equilibrium, along with solution methods like backward induction, are essential tools for understanding decision-making in economics, politics, and beyond. While assumptions about rationality and computational challenges exist, game theory remains a cornerstone of modern microeconomic analysis.