Module 2 - Games with Perfect Information

Syllabus
Strategic games – prisoner’s dilemma, matching pennies - Nash equilibria – theory and illustrations –
Cournot’s and Bertrand models of oligopoly – auctions – mixed strategy equilibrium – zero-sum games –
Extensive Games with Perfect Information – repeated games (prisoner’s dilemma) – subgame perfect
Nash equilibrium; computational issues.

--------------------------------------------------------------------------------------------------------------

Strategic Games

A strategic game models the interaction between multiple decision-makers, referred to as players. In
such games, each player has a set of possible actions, and their preferences are influenced by the actions
of all players, not just their own. This makes strategic games crucial for analyzing situations where
individuals’ decisions impact one another. Strategic games are often used to model real-world situations
involving competition, conflict, or cooperation, and are foundational in game theory.

Definition of Strategic Games

A strategic game, particularly one with ordinal preferences, consists of three main elements:

●​ A set of players.
●​ A set of possible actions for each player.
●​ Preferences for each player over the set of action profiles (the combination of all players' actions).

An action profile is a list of actions, one for each player. In practice, we often work with payoff
functions to represent preferences, instead of working directly with the preferences themselves.

An important feature of these games is that the players make their choices simultaneously, meaning no
player knows the choice of the others when deciding their own actions. This is why strategic games are
also referred to as simultaneous move games. In such models, time is abstracted; actions are chosen
once and for all, and any dynamic changes that might occur are not considered.
In this answer, we will explore two classic examples of strategic games: The Prisoner's Dilemma and
Matching Pennies.

1. The Prisoner’s Dilemma

●​ Read example from chapter 1

Real-world Examples:

The Prisoner’s Dilemma can model various real-world situations where individuals or entities face incentives
to act selfishly, despite knowing that cooperation would lead to a better collective outcome. For example:

●​ In environmental regulation, companies may prefer to pollute (betray) if they assume other companies
will cooperate (stay quiet), leading to environmental damage even though cooperation would benefit
society.
●​ In arms races, countries may continue building weapons (confess), despite knowing that mutual
disarmament (cooperation) would lead to better security.

2. Matching Pennies

Unlike the Prisoner’s Dilemma, Matching Pennies is a zero-sum game, meaning one player’s gain is equal to
the other player’s loss. This makes it a purely competitive game, with no room for cooperation.

Scenario:

Two players simultaneously choose whether to display the heads or tails side of a coin. The game is as
follows:

●​ If both players show the same side (both heads or both tails), Player 1 wins, and Player 2 loses.
●​ If the players show different sides, Player 2 wins, and Player 1 loses.

Payoff Matrix Representation:

●​ ​
​
The payoffs represent the amount of money won or lost. A positive number means the player wins
that amount, while a negative number means they lose it.
●​ Player 1 wants both players to choose the same side, while Player 2 wants them to choose different
sides.
Nash Equilibrium in Matching Pennies:

In pure strategies, there is no Nash Equilibrium in Matching Pennies, because each player can always benefit
by changing their choice to outsmart the other. However, in mixed strategies, where each player chooses
heads or tails randomly with a probability of 50%, we achieve a mixed strategy Nash Equilibrium:

●​ Neither player can predict the other's move, and no player has an advantage over the other. This
ensures fairness in the long run, with each player having an equal chance of winning.

Real-world Applications:

Matching Pennies can model situations where two entities have directly opposing goals. For example:

●​ In marketing, an established firm may want to differentiate its product from a competitor’s, while a
new entrant may want to mimic the established firm’s product to attract customers.​

Nash Equilibria- Theory and Illustrations

Nash Equilibrium is a situation in a game where no player can improve their outcome by changing their
strategy unilaterally, given that all other players keep their strategies unchanged.

In a game where players make choices, a big question is: What will each player do? The idea is that each
player will choose the best action based on what they think the other players will do. This means they need to
think about the other players' choices when deciding what to do.

Players learn about how others act in the game from previous experiences. They get better at guessing what
others will do without knowing exactly who they are playing against each time. It’s like in a market where
buyers and sellers don’t know each other, but they still make decisions based on what they’ve seen in the past.

The Nash equilibrium is a special situation in a game that has two important points:

1.​ Each player makes their choice based on what they think is the best move, considering the other
players.
2.​ Each player's guess about what the others will do is correct.

A Nash equilibrium happens when no player can get a better result by changing their choice while the others
stick to their choices. If everyone keeps their decisions, nobody wants to change because it wouldn’t help
them.

Strict and Nonstrict Equilibria

In many games we've studied, when players reach a Nash equilibrium, if one player decides to change their
action, it will result in a worse outcome for them compared to sticking with the equilibrium. This is a common
situation in Nash equilibria.
For a general game, an equilibrium is strict if each player’s equilibrium action is better than all her other
actions, given the other players’ actions. Precisely, an action profile a* is a strict Nash equilibrium if for
every player i we have ui(a*) > ui(ai , a*−i)for every action ai ≠ ai* of player i.

Example Game

Consider the following game matrix:

In this game, the unique Nash equilibrium is when Player 1 chooses T (the top row) and Player 2 chooses L
(the left column).

●​ At this point, if Player 2 chooses L, Player 1 is happy with either T or B. This means that if Player 1
switches from T to B, they won't do any worse; their payoff would still be 1.
●​ Because Player 1 can change their action without getting a worse result, we say that the Nash
equilibrium (T, L) is not a strict equilibrium.

Strict vs. Nonstrict Equilibria

A Nash equilibrium is strict if every player's action in that equilibrium gives them a better outcome than any
other action they could choose, given what the other players are doing.

In other words:

●​ In a strict Nash equilibrium, if a player sticks with their equilibrium action, they will do better than
if they choose any other action.
●​ In contrast, in a nonstrict Nash equilibrium, a player can switch to another action without doing
worse; they might even be indifferent between two actions.

This distinction helps us understand the stability and outcomes of different game situations.

Classic Games and their Nash Equilibrium covered in Book

1. Battle of the Sexes (BOS)

●​ Short Definition: A game where two players prefer different outcomes but want to coordinate on one.
●​ Players: Player 1 and Player 2 (e.g., a couple).
●​ Actions: Choose between two events (e.g., A or B).
 ●​ Payoff Matrix:

​
Payoff Interpretation:
○​ (2, 1): Player 1 chooses A and Player 2 chooses A (both are happy, but Player 1 is happier).
○​ (0, 0): Both choose different events, leading to no payoff.
○​ (1, 2): Player 1 chooses B and Player 2 chooses B (Player 2 is happier).
●​ Nash Equilibrium: (A, A) and (B, B) — both players coordinate on either event A or event B. In
these equilibria, neither player can improve their payoff by changing their choice unilaterally if the
other player's choice remains the same.

2. Chicken and Dove (or Hawk and Dove)

●​ Short Definition: A game representing conflict and cooperation where one player must yield to avoid
disaster.
●​ Players: Player 1 and Player 2.
●​ Actions: Choose between "Chicken" (aggressive) and "Dove" (passive).
●​ Payoff Matrix:

​
Payoff Interpretation:
○​ (-1, -1): Both players choose Chicken, leading to mutual destruction (worst outcome).
○​ (0, 1): Player 1 chooses Chicken, Player 2 chooses Dove; Player 2 benefits.
○​ (1, 0): Player 1 chooses Dove, Player 2 chooses Chicken; Player 1 benefits.
○​ (0, 0): Both choose Dove, leading to a neutral outcome.
●​ Nash Equilibrium: (Chicken, Dove) and (Dove, Chicken) — one player is aggressive, and the other
is passive. In these equilibria, if one player changes their action, they would not increase their payoff
given the other player's choice.

3. Stag Hunt

●​ Short Definition: A game that describes a conflict between safety and social cooperation.
●​ Players: Player 1 and Player 2.
●​ Actions: Choose between "Stag" (cooperate) and "Hare" (defect).
 ●​ Payoff Matrix:

​
Payoff Interpretation:
○​ (2, 2): Both players cooperate (best outcome).
○​ (0, 1): Player 1 chooses Stag, Player 2 chooses Hare; Player 1 gains nothing while Player 2
gains.
○​ (1, 0): Player 1 chooses Hare, Player 2 chooses Stag; Player 2 gains nothing while Player 1
gains.
○​ (1, 1): Both choose Hare; a safe but lower payoff for both.
●​ Nash Equilibrium: (Stag, Stag) — both players cooperate for the best outcome. Alternatively, (Hare,
Hare) is another equilibrium where both play it safe, resulting in lower payoffs. In both cases, no
player can improve their outcome by changing their choice unilaterally if the other player's choice
remains the same.

4. Matching Pennies

●​ Short Definition: A zero-sum game where two players try to match or mismatch their choices.
●​ Players: Player 1 and Player 2.
●​ Actions: Choose "Heads" or "Tails."
●​ Payoff Matrix:

​
Payoff Interpretation:
○​ (1, -1): Player 1 chooses Heads, Player 2 chooses Heads; Player 1 wins.
○​ (-1, 1): Player 1 chooses Heads, Player 2 chooses Tails; Player 2 wins.
○​ (-1, 1): Player 1 chooses Tails, Player 2 chooses Heads; Player 2 wins.
○​ (1, -1): Player 1 chooses Tails, Player 2 chooses Tails; Player 1 wins.
●​ Nash Equilibrium: No pure strategy equilibrium; players use mixed strategies. Each player
randomizes their choices between Heads and Tails to keep the other player guessing, ensuring that no
player can gain a consistent advantage by changing their strategy alone.

5. Prisoner's Dilemma (Arms Race, Duopoly, Common Property)

●​ Read example from chapter 1

●​ Add content on how this is connected with Arms Race, Duopoly, common property
The Prisoner's Dilemma offers a framework to analyze real-world situations where individual rationality
leads to collectively suboptimal outcomes. These scenarios are prevalent in various domains, including arms
races, duopoly markets, and the management of common property resources. Here's how the dilemma
applies in each context:

1. Arms Race

Scenario:

Two rival nations face a decision: Arm or Disarm. The choices reflect their focus on security and mutual
trust.

Payoff Structure:

●​ If both arm: Each faces high costs and risks but avoids vulnerability (low payoff).
●​ If both disarm: Both enjoy peace and save costs (high payoff).
●​ If one arms while the other disarms: The armed nation gains strategic dominance, while the
disarmed one becomes vulnerable (asymmetric payoffs).

Connection to the Prisoner’s Dilemma:

●​ Defect (Arm): Pursuing self-interest by building weapons.

●​ Cooperate (Disarm): Trusting the other nation to do the same.
●​ Rational behavior leads both to arm, even though mutual disarmament would yield a better collective
outcome.

Real-World Example:

The Cold War nuclear arms race exemplifies this dilemma, where both the USA and USSR invested heavily
in weapons despite the mutual benefit of disarmament.

2. Duopoly

Scenario:

Two competing firms in a duopoly must decide on strategies like setting low prices or maintaining high
prices.

Payoff Structure:
 ●​ If both maintain high prices: They maximize profits by avoiding price wars (high payoff).
●​ If both lower prices: A price war ensues, reducing profits for both (low payoff).
●​ If one firm lowers prices while the other maintains high prices: The firm with lower prices gains
market share, and the other suffers (asymmetric payoffs).

Connection to the Prisoner’s Dilemma:

●​ Defect (Lower Prices): Acting to maximize individual profit, causing a price war.
●​ Cooperate (Maintain High Prices): Acting to preserve collective profit.

Real-World Example:

The airline industry, where companies often face pressure to lower prices to attract customers, despite the
collective benefit of maintaining higher prices.

3. Common Property Resources

Scenario:

Multiple individuals or entities exploit a shared resource (e.g., a fishery, forest, or water supply). Each must
decide how much to use.

Payoff Structure:

●​ If everyone limits usage: The resource is preserved, benefiting all (high payoff).
●​ If everyone overuses: The resource depletes, leading to long-term losses (low payoff).
●​ If one overuses while others limit usage: The overuser benefits immediately, but the resource
deteriorates for others (asymmetric payoffs).

Connection to the Prisoner’s Dilemma:

●​ Defect (Overuse): Acting selfishly to maximize short-term gain.

●​ Cooperate (Limit Use): Acting collectively to sustain the resource.

Real-World Example:
The tragedy of the commons, such as overfishing in international waters, where individual fishermen aim to
maximize their catch, leading to the collapse of fish populations.

Insights from the Prisoner’s Dilemma in These Contexts

1.​ Rationality vs. Collectivity: Each player acting rationally leads to worse outcomes for all.
2.​ Need for Cooperation: The dilemma highlights the importance of mechanisms like treaties,
agreements, or regulations to achieve cooperation.
3.​ Incentive Design: Effective solutions involve altering payoffs to make cooperation more attractive,
such as:
○​ Mutual disarmament agreements (arms race).
○​ Antitrust regulations or collusion (duopoly).
○​ Quotas or licenses (common property).

The Prisoner’s Dilemma provides a powerful framework to understand and potentially resolve these
collective action problems.

Best Response Function

Definition

A best response function identifies the optimal actions for a player given the actions of all other players.
Formally, for player i, the set of best actions Bᵢ(a₋ᵢ) corresponds to:

Bᵢ(a₋ᵢ) is the set of Player i’s best actions when the other players’ actions are a₋ᵢ ​.

Bᵢ(a₋ᵢ) = {aᵢ ∈ Aᵢ : uᵢ(aᵢ, a₋ᵢ) ≥ uᵢ(a'ᵢ, a₋ᵢ) for all a'ᵢ ∈ Aᵢ }

- a₋ᵢ: The list of actions chosen by players other than i.​

- uᵢ: The payoff function for player i.​
- Aᵢ: The set of all possible actions for player i.

Every action in Bᵢ(a₋ᵢ) ensures that player i achieves the highest possible payoff given the actions of others.

Key Characteristics

1. Single vs. Multiple Best Actions:

●​ A player may have one best action or multiple best actions depending on the game.
●​ Example:
○​ In some games, like Battle of the Sexes (BoS), each best response set contains a single
action.
○​ In other games, there may be multiple actions that yield the same payoff.

2. Why Use Best Response Functions?

 ●​ They help us find Nash Equilibria more easily by showing the optimal strategies for each player.

· If every player adheres to their best responses, no one can improve their payoff by unilaterally deviating.

Using Best Response Functions to Define Nash Equilibrium

A Nash Equilibrium is an action profile in which every player’s action is a best response to the actions of
others.

Mathematically:​
a*ᵢ ∈ Bᵢ(a*₋ᵢ) for every player i.

If each Bᵢ(a₋ᵢ) contains a single action, this reduces to:​

a*ᵢ = bᵢ(a*₋ᵢ),

where bᵢ(a₋ᵢ) denotes the unique best response of player i.

Two-Player Example:

In a two-player game:​
a*₁ = b₁(a*₂), a*₂ = b₂(a*₁).​
- a*₁ is player 1’s best response to a*₂.​
- a*₂ is player 2’s best response to a*₁.

Using Best Response Functions to Find Nash Equilibria

Method:

1. Identify each player’s best response to every possible action profile of the other players.

2. Locate the action profiles where all players’ actions are best responses to one another.

Example

Consider the following game:

L C R

T 1, 2* 2*, 1 1*, 0

M 2*, 1* 0, 1* 0, 0

B 0, 1 0, 0 1*, 2*

Steps:
Step 1: Find Player 1’s Best Responses

●​ If Player 2 chooses L: The best action for Player 1 is M (payoff = 2).

●​ If Player 2 chooses C: The best action for Player 1 is T (payoff = 2).
●​ If Player 2 chooses R: The best actions for Player 1 are T and B (both give payoff = 1).

Step 2: Find Player 2’s Best Responses

●​ If Player 1 chooses T: The best action for Player 2 is C (payoff = 1).

●​ If Player 1 chooses M: The best action for Player 2 is L (payoff = 1).
●​ If Player 1 chooses B: The best action for Player 2 is R (payoff = 2).

Step 3: Identify Nash Equilibria

●​ Look for boxes where both players are playing their best responses simultaneously:
○​ (M, L): Player 1’s best response to L is M, and Player 2’s best response to M is L.
○​ (B, R): Player 1’s best response to R is B, and Player 2’s best response to B is R.

Result: The Nash Equilibria are (M, L) and (B, R).

Oligopoly: Introduction

Oligopoly is a market structure where a few firms dominate an industry, and their decisions directly impact
one another. Firms in an oligopoly are interconnected because they are competing for the same customers.
Their behavior is influenced by three key factors:

1.​ Demand for Products: How much consumers want the products and how sensitive they are to price
changes.
2.​ Costs of Production: The cost incurred by firms to produce goods, which can vary between
companies.
3.​ Number of Firms: Fewer firms generally result in less competition, potentially leading to higher
prices.

Economists use models to understand how firms in an oligopoly compete. Two important models we'll study
are:

●​ Cournot Model: This model focuses on firms competing by choosing the quantity of output they
produce. The firms decide how much to produce, and the market price is determined by the total
quantity produced by all firms. Each firm's strategy is its output level, and they assume that their
competitors' production levels are fixed. The market price is then a result of the total output in the
market. The Cournot model is often referred to as quantity competition.
●​ Bertrand Model: In contrast, the Bertrand model focuses on firms competing by setting prices rather
than quantities. Firms simultaneously choose the price at which they sell their goods, and consumers
buy from the firm offering the lowest price (assuming identical products). In this model, each firm's
 strategy is its price, and it assumes competitors' prices are fixed. The Bertrand model is typically
referred to as price competition.

To summarize:

●​ Cournot competition is about quantity.

●​ Bertrand competition is about price.

These models help explain strategic interactions between firms and the outcomes for consumers in an
oligopolistic market.

3.1.2 General Model of Cournot Oligopoly

In this model, multiple firms (n firms) produce a single good, and each firm decides how much output to
produce. The cost for firm i to produce qi units of the good is represented by a cost function Ci(qi), where
producing more units is more expensive (the cost increases with output).

The price of the good is determined by the total output of all the firms, and this price is described by the
inverse demand function P(Q), where Q is the total quantity produced by all firms. The price P(Q) decreases
as the total output increases, meaning more goods in the market lead to lower prices. The firm's revenue
depends on its output and the market price.

Thus, the profit of firm i, πi(q1,...,qn), is the revenue (price times quantity) minus the cost of production,
expressed as:

πi(q1,...,qn) = qi * P(q1 + ... + qn) - Ci(qi)

3.1.3 Example: Duopoly with Constant Unit Cost and Linear Demand

Let’s look at a specific case where there are two firms, and the situation is simpler because both firms have the
same cost structure and face a linear demand.

Cost Function: Each firm has a constant cost per unit of output, represented as Ci(qi) = cqi, where c is the cost
of producing one unit of the good.

Demand Function: The inverse demand function is linear and given by:

P(Q) = α - Q, if Q ≤ α

P(Q) = 0, if Q > α
Where:

P(Q) is the price when the total quantity produced by both firms Q = q1 + q2.

α is a constant representing the highest price consumers are willing to pay when no goods are produced.

Firm 1's Profit:

If the outputs of firms 1 and 2 are q1 and q2, the market price is P(q1 + q2) = α − q1 − q2 when total
production is less than or equal to α. Therefore, firm 1’s profit is:

π1(q1, q2) = q1 * (P(q1 + q2) − c) = q1 * (α − c − q1 − q2)

This function tells us that firm 1’s profit depends on its own output, firm 2’s output, the market demand, and
its production cost.

Firm 1's Best Response:

To maximize its profit, firm 1 will adjust its output based on firm 2’s output. When firm 2 produces zero
output (q2 = 0), firm 1 maximizes profit by producing:

q1 = 1/2 * (α − c)

When firm 2 produces more, firm 1's optimal output decreases because the total supply increases, lowering the
market price. If firm 2 produces q2, then firm 1’s best response is:
q1 = 1/2 * (α − c − q2)​
​

Nash Equilibrium in a Duopoly:

In Cournot competition, a Nash equilibrium occurs when each firm is producing an output level that is the best
response to the other firm’s output. Both firms will simultaneously adjust their outputs until neither can
increase their profit by changing their output.

For this specific duopoly, the best response functions of both firms are symmetric. Solving the system of
equations:

q1 = 1/2 * (α − c − q2)

q2 = 1/2 * (α − c − q1)

We find that the unique Nash equilibrium is:

q1* = q2* = 1/3 * (α − c)

In this equilibrium, both firms produce the same amount, and the total output in the market is Q = 2/3 * (α −
c). The price in the market at this equilibrium is:

P(Q) = 1/3 * (α + 2c)

Summary:

Higher α (more willingness to pay) results in more production and a higher market price.

Higher c (production cost) decreases production and increases the price of the good.

3.2 Bertrand’s Model of Oligopoly

In the Cournot model, firms compete by choosing how much to produce (quantity). The market price is then
determined by total production and consumer demand. However, in the Bertrand model, firms compete by
choosing prices instead of quantities.

Key aspects of Bertrand's model:

1. Single product: Multiple firms (n firms) produce the same product.

2. Cost of production: Each firm has its own cost function, represented by Ci(qi), where qi is the number of
units produced by firm i.

3. Demand: The total demand at a given price p is represented by the demand function D(p). This means that
consumers buy the good from the firm with the lowest price.

4. Price competition: If firms set different prices, all customers will buy from the firm with the lowest price. If
multiple firms set the same price, they share the market equally. If a firm’s price is higher than the lowest
price, it receives no demand and produces no output.

3.2.2 Example: Duopoly with Constant Unit Cost and Linear Demand
Summary of Bertrand’s Model:

1. Firms compete by setting prices, not quantities.

2. Consumers always buy from the firm with the lowest price.

3. The Nash equilibrium occurs when both firms set the price equal to the marginal cost, leading to no profit.
AUCTIONS

Auctions in Game Theory

In game theory, an auction is a competitive mechanism where multiple players (bidders) compete to buy an
item or service by submitting bids. Auctions are used to allocate resources efficiently when the value of the
item is not known by the seller, and the goal is to maximize the seller's revenue or achieve a fair market
price.

Each type of auction can be analyzed as a strategic game where the bidders are players, their bids are their
actions, and their payoffs depend on the auction's rules and the strategies of the other players.

First-Price Sealed-Bid Auctions

Overview:

●​ In a First-Price Sealed-Bid Auction, each bidder submits a bid without knowing the bids of others.
●​ The highest bidder wins the auction and pays the amount they bid.

Players:

●​ There are n bidders, each with a private valuation of the item, denoted by vᵢ for bidder i.

Actions:

●​ Each bidder submits a sealed bid bᵢ without knowing the bids of others.
●​ The bid bᵢ can range from 0 to their valuation vᵢ.

Preferences:

●​ Each bidder wants to maximize their utility, which is the difference between their valuation of the
item and the amount they pay if they win.
●​ If bidder i wins with bid bᵢ, their utility is vᵢ − bᵢ.
●​ If they lose, their utility is 0.

Nash Equilibrium:

●​ In a First-Price Auction, the Nash Equilibrium occurs when each bidder bids less than their true
valuation.
●​ Bidders shade their bids because paying their true valuation gives zero surplus.
●​ This strategy balances the probability of winning with the profit if they win.

Second-Price Sealed-Bid Auctions (Vickrey Auction)

Overview:

●​ In a Second-Price Sealed-Bid Auction, each bidder submits a bid without knowing the bids of others.
●​ The highest bidder wins but pays the amount of the second-highest bid.

Players:

●​ There are n bidders, each with a private valuation of the item, denoted by vᵢ for bidder i.
Actions:

●​ Each bidder submits a sealed bid bᵢ.

●​ The bids are independent and private, not revealed to other bidders.

Preferences:

●​ Bidders aim to win the auction and pay less than their true valuation.
●​ The utility for the winning bidder i is vᵢ − b₂ 𝒹, where b₂ 𝒹 is the second-highest bid.
●​ For losing bidders, the utility is 0.

Nash Equilibrium:

●​ In a Second-Price Auction, the dominant strategy and Nash Equilibrium for each bidder is to bid their
true valuation, bᵢ = vᵢ.
●​ Bidding the true value is optimal because:
○​ If you bid higher than your value, you risk winning and paying more than your value,
resulting in negative utility.
○​ If you bid lower than your value, you risk losing the auction when you could have won by
bidding your true value.
○​ The price paid is not affected by your bid if you win, so there is no advantage to shading your
bid.

●​ The second-price rule means the winner pays the second-highest bid, so there's no incentive to bid
above or below your valuation; you gain nothing by misrepresenting your value.

Comparison of First-Price and Second-Price Auctions

Aspect First-Price Auction Second-Price Auction

Bidding Bid below true value Bid true value

Strategy

Winner Pays Their own bid Second-highest bid

Equilibrium Nash Equilibrium with bid Dominant strategy of bidding

Concept shading true value

Risk Strategic guessing; risk of Lower risk; true value bidding

overbidding is safe

These auction formats provide different strategic challenges and opportunities, with second-price auctions
promoting honest bidding and first-price auctions requiring careful strategic adjustments.

Bid shading is a strategy used in auctions, particularly in First-Price Sealed-Bid Auctions, where bidders
deliberately bid less than their true valuation of the item. The primary goal of bid shading is to increase the
surplus or profit if the bidder wins, by paying less than what they value the item.
Why Bid Shading Occurs:
●​ In first-price auctions, the winner pays the amount of their bid. Therefore, if a bidder bids their true
valuation, they will not gain any surplus or profit (i.e., their utility would be zero).
●​ By bidding lower than their true value, bidders aim to balance the probability of winning with the
desire to pay less, thus maximizing their utility.

Factors Influencing Bid Shading:

●​ Number of Competitors: With more competitors, bidders may shade less to increase their winning
chances.
●​ Risk Attitude: Risk-averse bidders might shade less to ensure a win, while risk-neutral or risk-seeking
bidders might shade more.
●​ Information on Others: If bidders have an idea of others' valuations or bidding tendencies, they can
adjust their shading strategy.
Mixed Strategy Equilibrium

Mixed Strategies
In many strategic games, players face situations where playing a single, deterministic strategy (called a
pure strategy) might not lead to the best outcome, especially if the game has no Nash equilibrium in
pure strategies. A mixed strategy equilibrium is a probability distribution over all possible pure
strategies, allowing the player to randomize their actions. Instead of committing to a single action, a
player selects from their available actions based on pre-determined probabilities.

Why Mixed Strategy Equilibrium?

1.​ No Pure Strategy Equilibrium: Some games, such as "Matching Pennies" or certain forms of
"Rock, Paper, Scissors," do not have an equilibrium where players consistently benefit from
playing one pure strategy (an action chosen with certainty). In such cases, players can use mixed
strategies to reach an equilibrium.
2.​ Unpredictability Advantage: By using mixed strategies, players can make their actions less
predictable, preventing opponents from taking advantage of a deterministic pattern. In a mixed
strategy equilibrium, each player randomizes their actions in such a way that the opponents are
indifferent to the player's choice; that is, every action yields the same expected payoff.

The main steps to find a mixed strategy equilibrium are:

1.​ Determine the best responses: For each player, calculate the expected payoffs for all possible
actions based on the probabilities of the opponent's actions.
2.​ Make opponents indifferent: Set the probabilities in such a way that every action the player
takes results in the same expected payoff. This ensures that no single action is strictly better than
any other, and thus the player is indifferent among their possible actions.
3.​ Solve the equilibrium conditions: The mixed strategy equilibrium is reached when each player's
mixed strategy is the best response to the other players' mixed strategies.

Example of Mixed Strategy Equilibrium

Consider the game of "Matching Pennies." The players, A and B, each simultaneously choose either
heads or tails. If their choices match, Player A wins a dollar from Player B. If their choices differ, Player
B wins a dollar from Player A. The payoff matrix is as follows:
 ●​ If Player A chooses heads 100% of the time, then Player B can choose heads 100% of the time to
always win.
●​ If Player A chooses tails 100% of the time, then Player B can choose tails 100% of the time to
always win.

Neither pure strategy is stable, and the optimal approach is for both players to randomize.

Finding the Mixed Strategy Equilibrium:

●​ Let’s say Player A chooses heads with probability p and tails with probability (1 - p).
●​ Player B chooses heads with probability q and tails with probability (1 - q).

Player A will be indifferent between choosing heads and tails if the expected payoffs for both actions are
the same. Similarly, Player B will be indifferent if their expected payoffs are also balanced.

For Player A:

●​ The expected payoff of choosing heads is: q × (1) + (1 - q) × (-1) = 2q - 1.

●​ The expected payoff of choosing tails is: q × (-1) + (1 - q) × (1) = 1 - 2q.

Set these equal to make A indifferent: 2q−1=1−2q Solving gives: q=0.5

For Player B:

●​ The expected payoff of choosing heads is: p × (-1) + (1 - p) × (1) = 1 - 2p.

●​ The expected payoff of choosing tails is: p × (1) + (1 - p) × (-1) = 2p - 1.

Set these equal to make B indifferent: 1−2p=2p−1 Solving gives: p=0.5

So, in the mixed strategy equilibrium, both Player A and Player B will choose heads and tails each with a
probability of 0.5. This randomization ensures that no player has an incentive to change their strategy, as
each action yields the same expected payoff.
Zero-Sum Games
Zero-Sum Games: A zero-sum game is a type of game where one player's gain is exactly offset by
another player's loss. In these games, the sum of the payoffs for all players equals zero, which means that
the interests of the players are strictly opposed. Zero-sum games are often used to model highly
competitive situations like sports, war, poker, and certain market behaviors.

The core characteristics of zero-sum games include:

1.​ Pure Competition: Any advantage gained by one player comes at a direct cost to another. This
type of game structure emphasizes conflict, with no room for mutual gains or cooperation.
2.​ Outcome Representation: If a player receives a payoff of +1, another must receive a payoff of
-1, making the total sum of payoffs zero. For example, in "Rock, Paper, Scissors," if Player A
wins, they get a payoff of +1 and Player B gets -1. If they tie, both receive a payoff of 0, resulting
in a sum of 0 for any outcome.
3.​ Maximizing Minimum Gains (Minimax Theorem): The strategy for players in zero-sum games
often revolves around minimizing their maximum possible loss, known as the minimax strategy.
This approach helps players protect themselves against their worst-case scenarios.

For example, consider a zero-sum game like a competitive bidding scenario in an auction for a fixed
contract. If one bidder wins by offering a lower price, the other bidder loses out on that opportunity. The
net benefit or loss between the two bidders is zero since one player's gain corresponds to the other's loss.

Mixed Strategies in Zero-Sum Games: In zero-sum games, mixed strategies play a crucial role. Since
the players’ interests are completely opposed, each player tries to maximize their gain while minimizing
the opponent's gain. As a result, they often resort to mixed strategies to ensure they are not predictable.
The minimax theorem shows that in a zero-sum game, there always exists a mixed strategy equilibrium
where both players use mixed strategies to maximize their respective minimum payoffs.

Application of Mixed Strategies and Zero-Sum Games:

1.​ Sports Competitions: In tennis or boxing, one player’s win is the other's loss; every point or
round gained by one player directly decreases the chance of victory for their opponent.
2.​ Military Tactics: Zero-sum games are used to model military conflicts or scenarios where one
side's gain is directly another's loss. Strategies often include deception and randomization to
minimize predictability.
3.​ Poker and Bluffing: In poker, players use mixed strategies to bluff, bet, or fold in unpredictable
ways to maximize their chances of winning while minimizing losses.
Extensive Games with Perfect Information

-Extensive games with perfect information are a type of game in game theory where players make
decisions sequentially, and every player is fully aware of all the actions that have occurred up to the
point of their decision.
-In these games, there is a specific order in which players move, and at each point, the player
making the decision has complete knowledge of all prior decisions made in the game.

An extensive game with perfect information and simultaneous moves is formally defined by:

1.​ Players: The individuals participating in the game.

2.​ Terminal Histories: The sequences of actions leading to an outcome, ensuring no
sequence is a proper sub-history (subset) of any other.
3.​ Player Function: A function that assigns a set of players to each non-terminal history,
indicating who is to make decisions after each sequence.
4.​ Actions: For each player, the set of actions available after any given history.
5.​ Preferences: Each player’s preferences over the set of terminal histories, which determine
how outcomes are valued.

The set of terminal histories, the player function, and the actions must be consistent, meaning that
each action in a terminal history corresponds to a decision made by the appropriate player or
players.

E.g. Chess, Tic-Tac-Toe, Go etc.

Entry game example

An incumbent faces the possibility of entry by a challenger. (The challenger may, for example, be a
firm considering entry into an industry currently occupied by a monopolist, a politician competing for
the leadership of a party.) The challenger may enter or not. If it enters, the incumbent may either
acquiesce or fight.​

This situation is modeled as an extensive game with perfect information.

Terminal Histories: (In, Acquiesce), (In, Fight), and Out.

Player Function: Challenger starts the game, incumbent moves after "In."
Actions Available:

●​ Challenger: {In, Out}.

●​ Incumbent: {Acquiesce, Fight}.

A valid terminal history cannot have any of its subhistories also as terminal histories. For example, if
(In, Fight) is terminal, "In" alone cannot be terminal.

Entry Game Payoffs:​

​
The challenger prefers the incumbent to acquiesce if they enter and dislikes fighting. The incumbent
prefers the challenger to stay out and dislikes fighting as well.
Key elements:

●​ Players: Challenger and incumbent.

●​ Preferences (Payoffs):
○​ Challenger: u1(In,Acquiesce)= 2, u1(Out)= 1, u1(In,Fight)= 0.
○​ Incumbent: u2(Out)= 2, u2(In,Acquiesce)= 1,u2(In,Fight)= 0.

Where, u1 is the payoff function for the challenger and u2​is the payoff function for the
incumbent.

●​ Challenger moves first: {In, Out}.

●​ If "In" is chosen, incumbent moves: {Acquiesce, Fight}.
●​ Payoffs are listed as (Challenger, Incumbent).

Extensions and Simultaneous Moves

In a basic extensive game with perfect information, decisions are made one after another, with each
player knowing all the moves that have come before. However, this model can be extended to allow
for situations where some decisions are made simultaneously by multiple players. In such cases,
each player knows all the actions taken up until that point but does not know the actions being taken
by the other players at that exact moment. This is called an "extensive game with perfect
information and simultaneous moves."

For example, consider a scenario where:

1.​ Player 1 makes a decision between two actions, C or D.

2.​ After Player 1’s decision, Players 2 and 3 make simultaneous choices, each deciding
between actions E and F without knowing what the other player is choosing at that time.

In this case, a terminal history (a complete sequence of actions leading to an outcome) might look
like:

●​ (C, (E, E)): Player 1 chooses C, and then Players 2 and 3 both choose E simultaneously.

Strategies and Nash Equilibrium

A strategy in these games specifies the action a player will choose for every possible history
(sequence of prior actions) after which it is their turn to move. This strategy must cover all
contingencies, including those where the player would not naturally reach because of their earlier
choices.

A Nash equilibrium is a profile of strategies (one for each player) such that no player can improve
their outcome by unilaterally changing their strategy, given the strategies of the other players. In the
context of extensive games with simultaneous moves, a strategy profile is a Nash equilibrium if it is
the best response for all players given what others are doing.

Example: Battle of the Sexes (BoS) Variant

Consider the following game:

●​ Player 1 (Person 1) decides either to "Stay Home" or "Attend Concert."

●​ If "Attend Concert" is chosen, then both Player 1 and Player 2 simultaneously decide
between attending either a Bach concert (B) or a Stravinsky concert (S).

The preferences of the players are as follows:

●​ Player 1 prefers both attending Bach together over staying home, which is preferred over
attending Stravinsky together.
●​ Player 2 prefers both attending Stravinsky together over staying home, which is preferred
over attending Bach together.
●​ Both players' least preferred outcome is going to different concerts.

The payoff matrix for this game would look like this:

The game has three pure strategy Nash Equilibria:

1.​ (B, B): Both attend the Bach concert.

2.​ (S, S): Both attend the Stravinsky concert.
3.​ (SH, SH): Both choose to stay home.

Repeated Games: The Prisoner’s Dilemma

1. Overview of the Prisoner's Dilemma

The Prisoner's Dilemma is a fundamental example in game theory that illustrates the conflict
between individual interests and collective benefit.
Scenario:

Two suspects are arrested and interrogated separately. Each has two choices:

●​ Cooperate (C): Remain silent.

●​ Defect (D): Betray the other.

Payoff Matrix:

The outcomes can be represented in a payoff matrix:

(C, C): Both players cooperate, yielding moderate rewards (2 each).

●​ (C, D): Player 1 cooperates, Player 2 defects. Player 1 gets 0, Player 2 gets 3.
●​ (D, C): Player 1 defects, Player 2 cooperates. Player 1 gets 3, Player 2 gets 0.
●​ (D, D): Both defect, resulting in a lower payoff (1 each).

2. Repeated Games

In a repeated game, the same game (Prisoner’s Dilemma) is played multiple times, allowing
players to adapt their strategies based on the history of past interactions.

Key Features of Repeated Games:

1.​ Strategy Development: Players can develop strategies that condition their actions based on
the history of play.
2.​ Potential for Cooperation: Over time, players can establish cooperative norms, knowing
that future interactions may be influenced by current choices.

Types of Repeated Games:

●​ Finitely Repeated Games: The game is played a specific number of times (e.g., T times).
●​ Infinitely Repeated Games: The game continues indefinitely, with players unsure of the
endpoint.

3. Subgame Perfect Nash Equilibrium (SPNE)

Definition:

A Subgame Perfect Nash Equilibrium (SPNE) is a refinement of Nash Equilibrium applicable in

dynamic games. It ensures that players make optimal decisions at every stage of the game.

Finding SPNE through Backward Induction:

 1.​ Last Round Analysis: In the last round (round T), both players will defect (D) because
cooperating (C) has no future benefits.
○​ Players realize that any cooperation in the last round cannot yield future rewards.
2.​ Second to Last Round: Knowing that both will defect in the last round, players will also
defect in the second-to-last round since their actions do not affect the last round's outcome.
○​ If one player considers cooperating, they will receive a lower payoff due to the
defection in the last round.
3.​ Induction Step: This reasoning continues backward through all previous rounds, leading to
the conclusion that in every SPNE, both players will defect (D) in every period.
○​ The realization that cooperation in previous rounds cannot change the outcome in
the last round leads to consistent defection.

Conclusion on SPNE:

In a finitely repeated Prisoner’s Dilemma, players will always choose to defect (D) due to backward
induction, resulting in a collectively worse outcome compared to cooperation.

Example: Cake Division Game

Two players, Player 1 and Player 2, decide how to split a cake.

Game Description:

1.​ Player 1 proposes how to divide the cake: a fraction xxx (for themselves) and 1−x1-x1−x (for
Player 2), where 0≤x≤10 \leq x \leq 10≤x≤1.
2.​ Player 2 decides to either Accept or Reject the proposal:
○​ If Player 2 Accepts, the cake is split as proposed.
○​ If Player 2 Rejects, neither player gets any cake, and both get a payoff of 0.

Payoffs:

●​ If Player 2 Accepts, the payoffs are:

○​ Player 1: x
○​ Player 2: 1−x
●​ If Player 2 Rejects, the payoffs are:
○​ Player 1: 0
○​ Player 2: 0
SPNE:

Explanation:

The SPNE ensures that Player 1 offers the smallest amount necessary to ensure Player 2’s
acceptance, maximizing Player 1’s payoff while still being rational for Player 2.

Extra

4. Strategies in Infinitely Repeated Prisoner’s Dilemma

4.1 Grim Trigger Strategy:

●​ Mechanism: Players cooperate until one defects. If one player defects, the other will defect
forever.
●​ Payoff Calculation: If both players use this strategy, they each receive a consistent payoff x
for every period. If a player defects, their short-term payoff might be higher (e.g., y), but they
lose future cooperation.

4.2 Tit-for-Tat Strategy:

●​ Mechanism: Players start with cooperation and then replicate the opponent's last move in
subsequent rounds.

5. Nash Equilibria in Infinitely Repeated Prisoner’s Dilemma

5.1 Player Behavior:

When players adhere to a cooperative strategy, they can achieve a beneficial average payoff.
However, players can always increase their payoff by defecting for one round, complicating the
equilibrium.

5.2 Equilibrium Conditions:

The Nash equilibrium in infinitely repeated games depends on players' payoffs and discount factor
δ\deltaδ. Various inequalities determine if the strategy pair constitutes a Nash equilibrium.

5.3 Example Calculation:

For a player who cooperates consistently (achieving a payoff of 2) versus defecting:

●​ Stream of payoffs for defecting once might be (3, 2, 2, ...).

Computational Issues
In the context of repeated games, especially the Prisoner's Dilemma, computational issues arise
from the complexities of strategy formulation, equilibrium determination, and player interactions.
Here are the key computational issues detailed:

Complexity of Strategy Spaces

 1.​ Exponential Growth of Strategies:​
​

2.​ History-Dependent Strategies:

○​ Players may use history-dependent strategies, meaning that their current choices
depend on the actions taken in previous rounds. This adds a layer of complexity as
players must consider all past interactions when deciding their next action.
○​ Strategies like Tit-for-Tat rely on the history of moves, where a player's next action is
determined by their opponent's last action. This means that analyzing player behavior
becomes significantly more complicated as each round influences future rounds.
3.​ Dynamic Strategy Adjustment:
○​ In repeated games, players can adjust their strategies based on the actions of others.
This dynamic nature complicates predictions about future behavior, as players may
choose to deviate from established strategies in response to their opponents' actions.
○​ The necessity for ongoing adaptation creates a complex strategic environment where
calculating optimal strategies becomes computationally demanding.

Limitations of Backward Induction

1.​ Challenges in Application:

○​ Backward induction is a standard method for solving finite games by analyzing the
final moves and determining optimal strategies in reverse order. However, this
method struggles in infinite repeated games, where players do not have a definitive
endpoint for the game.
○​ The lack of a clear termination point makes it difficult to apply backward induction
effectively, as players may not know how their current decisions will affect future
outcomes.
2.​ Indefinite Nature of Future Actions:
○​ In infinitely repeated games, the potential for continuous interaction creates
uncertainty for players. They must consider not only their immediate payoffs but also
the long-term implications of their current actions.
○​ The reasoning required to predict future behavior becomes significantly more
complex, complicating the analysis of player strategies and outcomes.
3.​ Equilibrium Determination:
○​ Finding Subgame Perfect Nash Equilibria (SPNE) requires assessing all possible
deviations by players and their impacts on future payoffs. As the strategy space
grows, the computational burden increases, making it more difficult to derive clear
conclusions about player behavior.
Algorithmic and Computational Techniques

1.​ Simulation and Algorithmic Approaches:

○​ Researchers often rely on simulation techniques and algorithmic approaches to
explore the vast strategy spaces and identify potential equilibria in repeated games.
○​ Techniques such as evolutionary game theory models, genetic algorithms, and
agent-based simulations are commonly used to analyze player interactions over
multiple rounds.
2.​ Resource Demands:
○​ The computational resources needed for simulating numerous rounds with diverse
strategies can be substantial. This may lead to limitations in processing power and
memory, especially in more complex games.
○​ As the complexity of the game increases, the time required to compute outcomes can
grow significantly, posing challenges for real-time decision-making.
3.​ Use of Approximation Techniques:
○​ To manage computational challenges, approximation techniques can be employed to
simplify the model or focus on specific strategy subsets. These methods help reduce
the complexity of the analysis while still providing valuable insights into player
behavior.