Power Round April 8, 2023

Preliminaries
Time Limit: 80 minutes.
Maximum Score: 166 points.
Instructions: Problems that use the words “show”, “prove”, or “justify” require explanation or proof. Unless otherwise
stated, full credit will be given for just the final answer. However, partial credit will be given for close attempts, so
teams may find it in their best interest to show work regardless. Answers should be written on sheets of loose paper,
clearly labeled, with every problem on its own sheet. Write the problem number in the top left corner. If you have
multiple pages for a problem, number them and write the total number of pages for the problem in the bottom right
corner (e.g. 1/2, 2/2).
Indicate your team ID number in the top right on each paper that you submit. Only submit one set of solutions for
the team. Do not turn in any scratch work. In your solution for a given problem, you may cite the statements of
earlier problems (but not later ones) without additional justification, even if you haven’t solved them. The problems
are ordered by content, NOT DIFFICULTY. It is to your advantage to attempt problems from throughout the test.
While completing the round, you should not any materials outside of the content of this test (including results not
covered in this power round). You may not use calculators. Good luck!

1
 Power Round April 8, 2023

1 Introduction to Game Theory

This section focuses on providing an introduction to the fundamental concepts of game theory that we will build
off in the later sections. Intuitively, games are situations where participants’ payoffs (what they get out of a game,
whether it be money, joy from winning, etc.) depend not only on their own actions but also on the actions of their
opponents. Examples include games in the traditional sense such as chess and rock-paper-scissors but also can include
real-world interactions such as auctions and how firms decide prices.
In any given game, there is a set of players (this test will focus on the case where there are only two players, but
there can be any number of players in general); each player has a set of possible actions; and finally, there is some
mapping that takes action profiles to payoffs.
We start by working through formalizing the game of rock-paper-scissors. Rock-paper-scissors is a game we are
all familiar with, and we all probably have some intuitive idea about how to play it. How might we describe it
mathematically?
• This is a game involving n = 2 players (we can have more than 2 players in general, but this section will focus
on the case of two players).
• Each player is allowed to throw rock, paper, or scissors. We could write this as

A1 = A2 = {rock, paper, scissors}

where A1 is the set of actions available to the first player and A2 is the set of actions available to the second
player. In the particular case of “Rock, Paper, Scissors”, both players have the same options, namely rock,
paper, or scissors. However, this is not generally true: in tic-tac-toe for instance, if one player claims a square
then that square is no longer available to the other player.
• To fully describe what happens in a single instance of the rock-paper-scissors game, I could provide an element
of A = A1 × A2 , which is the set of action profiles. For instance, (rock, paper) is an element of A and
corresponds to player one throwing rock and player two throwing scissors.
• There’s either a winner and a loser, or the players draw. For concreteness, we assign each outcome a value: 1
for a win, 0 for a draw, and -1 for a loss. (This is sometimes called the player’s utility or payoff ).
In general, for each combination of actions, each player gets a certain utility value. We can represent this as a
function ui : A → R for the i-th player.
All in all, a normal form game refers to the triple (N, {Ai }, {ui }) of some number of players, a set of actions for
each player, and a utility function for each player. For two players, we can represent this information succinctly
in a table (called the payoff/utility matrix): the rows correspond to player 1’s actions, the columns correspond
to player 2’s actions, and the pairs describe player 1 and player 2’s utilities, respectively. For instance, if player

R P S
R (0, 0) (−1, 1) (1, −1)
P (1, −1) (0, 0) (−1, 1)
S (−1, 1) (1, −1) (0, 0)

one throws rock and player two throws paper, this corresponds to row R and column P . The entry there is
(−1, 1) which corresponds to player one losing and receiving a payoff of −1 and player two winning and receiving
a payoff of 1. This is exactly what happens in rock-paper-scissors, as paper does in fact beat rock. To see the
connection between the payoff matrix and each player’s utility function, note

u1 ((R, P )) = −1 and u2 ((R, P )) = 1.

With this in mind, we move on to what it means to “solve” a game. Intuitively, we want choices to be such that no
single player can do better for themselves, keeping the choices of other players fixed.
Definition 1.1 (Pure Strategy Nash Equilibrium). A pure strategy profile {ai } forms a Nash equilibrium of a game
(N, {Ai }, {ui }) if there are no profitable deviations: for all players j, their action aj achieves a weakly higher payoff
than any action a′j keeping all other actions a−j fixed. In other words, uj (aj , a−j ) ≥ uj (a′j , a−j ) for all a′j .

2
 Power Round April 8, 2023

One method of computing Nash Equilibrium is by finding best responses. In particular, when given a payoff matrix,
do the following:
1. For every column, circle player one’s maximum attainable payoff in that column if player two plays the action
of that column;
2. For every row, circle player two’s maximum attainable payoff in that row if player one plays the action of that
row;
3. If an entry in the payoff matrix has both player one’s payoff and player two’s payoff circled, then we call the
action profile that leads to that payoff profile a mutual best response.
Going forward, call this process “circling best responses”. Here is some practice for finding mutual best-responses.
Problem 1.1 (2 points). Find all strategy profiles that are mutual best responses of the following game:

X Y
A (10, 7) (−5, 1)
B (7, −8) (−2, −3)

Problem 1.2 (3 points). Find all strategy profiles that are mutual best responses of the following game:

X Y Z
A (5, −3) (1, 0) (7, −1)
B (5, 1) (0, 0) (7, 1)
C (3, 10) (1, −1) (5, 7)

Next, we show that the process of circling best responses finds all pure strategy Nash equilibria.
Problem 1.3 (4 points). Prove that the process of circling best responses finds exactly all Nash equilibria.
So far, the games in normal form we’ve seen only capture situations where moves are decided simultaneously by
each player. Clearly, there are situations where this is not the case and timing plays a role. To capture this, we now
introduce extensive form games. Extensive form games can be represented by game trees.
For example, consider the fight-or-flight game. Two animals encounter one another. The first animal chooses to either
fight or flight. The second animal observes the first animal’s choice and also decides to fight or flight. If both fight,
both animals are injured. If both flight, nothing happens. If one fights and the other flights, the animal that chooses
fight wins.
Let’s try to first express this game as a normal form. There clearly are n = 2 players. The first animal’s action space
is A1 = {fight, flight}. However, the second animal’s action space is no longer just {fight, flight}: their decision is
informed by observing what the first animal does. Intuitively, animal two makes two choices: what to do if animal
one fights, and what to do if animal one flights. As such, there are four total strategies (two choices for the two
actions animal one has):
1. fight if animal one fights and fight if animal one flights;
2. fight if animal one fights and flight if animal one flights;
3. flight if animal one fights and fight if animal one flights;
4. flight if animal one fights and flight if animal one flights.
To simplify notation, let the action (x, y) denote “x if animal one fights and y if animal one flights”. Thus, we have

A2 = {(fight, fight); (fight, flight);(flight, fight); (flight, flight)}.

Writing out the normal form will have A1 = {fight, flight} as rows and A2 as defined above as columns. However,
what are the payoffs?

3
 Power Round April 8, 2023

If animal one plays flight and animal two plays (fight, flight) then animal one flights and animal two also flights, as
their strategy of “fight if animal one fights, flight if animal one flights” leads to flight when animal one flights. We
can model this with the following payoff matrix (with payoffs chosen arbitrarily):

(fight,fight) (fight,flight) (flight,fight) (flight,flight)

fight (−2, −2) (−2, −2) (2, −5) (2, −5)
flight (−5, 2) (0, 0) (−5, 2) (0, 0)

Alternatively, we can represent this game with a game tree:

To read this game tree, start from the top. At the node labeled 1, animal one has a choice of fight or flight, represented
by the two edges. After player one’s choice, animal two has a choice at each of the nodes labeled 2: one node for if
player one chose fight and one node for if player two chose flight. At each of those nodes, animal two can choose to
either fight or flight. Finally, payoffs are listed at the bottom corresponding to which path the animals’ actions take.
Problem 1.4 (4 points). Draw a game tree for the following game:
1. Player one chooses between A and B;
2. If player one chooses A, then players two and three play rock-paper-scissors, except player two moves first and
reveals what they play to player three before player two’s choice;
3. If player one chooses B, then players two and three play rock-paper-scissors, except player three moves first and
reveals what they play to player two before player two’s choice;
4. Payoffs are as follows:
• Player one’s payoff is 1 if players two and three tie in their game of rock-paper-scissors and is 0 otherwise;
• Player two’s payoff is 1 if they win the game of rock-paper-scissors, −1 if they lose the game of rock-paper-
scissors, and 0 otherwise;
• Player three’s payoff is 1 if they win the game of rock-paper-scissors, −1 if they lose the game of rock-
paper-scissors, and 0 otherwise.
In general, extensive form games are:
Definition 1.2 (Extensive Form Game). An extensive form game represented by a game tree consists of the following:
1. A set of players N = {1, 2, ..., n} as before;
2. A rooted tree1 with edges E, non-terminal nodes D (also known as decision nodes, and hence the D) and
terminal nodes T ;
3. A function P : D → N that indicates which player moves at each non-terminal node;
1 A rooted tree is a set of nodes V and edges E ⊂ V × V such that:

(a) there is some node r ∈ V that is designated as the root;

(b) for all v ∈ V , there exists a unique sequence v1 , ..., vn such that v1 = r, vn = v, and (vi , vi+1 ) ∈ E for all i = 1, ..., n − 1.

4
 Power Round April 8, 2023

4. A function u : T → Rn that assigns a payoff to each terminal node.

In this setting, the action space for player i at node v if P (v) = i is the set of edges starting at v pointing away from
the root of the game tree. Let A(v) denote the possible actions for player P (v) at node v.
Since players now might need to make multiple decisions, the set of strategies they choose from is richer. Formally,
we have the following.
Definition 1.3 (Strategy). A strategy for player i is a choice of action for every node they play at. Mathematically,
player i’s strategy space is the set of functions

Si = {si : P −1 (i) → A such that si (v) ∈ A(v)}.

Note: An action must be specified at every node, even nodes that are never reached due to some previous action. As
such, player 2’s strategy space in the extensive-form fight or flight game needs to specify what they do when player
1’s strategy is fight and when player 1’s strategy is flight, even though only one of the two will actually be played. As
such, player 2’s strategy space is {(flight, flight), (flight, fight);(fight, flight); (fight, fight)} opposed to {fight, flight}.
Problem 1.5 (2 points). Compute the number of strategies in Player 1’s strategy space. Compute the number of
strategies in Player 2’s strategy space.

In extensive games, the same definition of Nash Equilibrium holds. One issue when games are sequential is that some
threats may not be credible. If one player’s strategy specifies some choice at a future decision node, how do we know
that they’ll actually carry out that action when we arrive at that point?
Consider the following market entry game:

5
 Power Round April 8, 2023

There are two firms. Firm two is already in the market for axes at UC Berkeley. Firm one is deciding whether or not
to enter the market. If firm one enters, firm two can either fight by lowering prices, harming both firms. Otherwise,
they can share the market. If firm one does not enter, firm two keeps the entire market.
Clearly, firm two would prefer for firm one to not enter the market. One possible strategy for firm two is to commit
to fighting if firm one enters (and fight even if firm one does not). However, if firm one does choose to enter, firm
two’s best response is to Share.
Problem 1.6 (2 points). Find all Nash Equilibrium of the Market Entry game.
To weed out non-credible threats, we need a finer notion of equilibrium.
Definition 1.4 (Subgame). Let an extensive form game have players N , a rooted tree with edges E, non-terminal
nodes D, and terminal nodes T , a player assignment function P , and a payoff function u. Then, the subgame of that
extensive form game starting at node d ∈ D is the extensive form game with:
1. The same set of players N ;
2. A rooted tree T ′ with root d, and all edges and nodes that are below d in the original tree;
3. Player Assignment function P ′ equal to P restricted to non-terminal nodes of T ′ ;
4. Payoff function u′ equal to u restricted to terminal nodes of T ′ .
Definition 1.5 (Subgame Perfect Nash Equilibrium). A set of strategies for each player forms a Subgame Perfect
Nash Equilibrium strategy profile if for every subgame, the strategy of each player restricted to the subgame forms a
Nash Equilibrium.
Problem 1.7 (2 points). Find all Subgame Perfect Nash Equilibrium of the Market Entry game.
Problem 1.8 (2 points). Show that every Subgame Perfect Nash Equilibrium is a Nash Equilibrium. For full points,
do not directly appeal to the definition of Nash Equilibrium.

Problem 1.9 (3 point). Find the Subgame Perfect Nash Equilibrium of the above game.
Problem 1.10 (5 points). Does every extensive form game with a finite number of moves have at least one Subgame
Perfect Nash Equilibrium? Justify your answer.
For the next problem, we need to specify the difference between a Subgame Perfect Nash Equilibrium and an outcome.
A Subgame Perfect Nash Equilibrium specifies a full strategy profile for all players, including listing what happens at
nodes that are never encountered. However, an outcome only lists the sequence of actions that are played. As such,
multiple Subgame Perfect Nash Equilibrium (that differ on strategies at nodes that are never reached) can induce
the same outcome.
Problem 1.11 (4 points). Does every extensive form game have at most one Subgame Perfect Nash Equilibrium
outcome? Justify your answer.
To finish this section, we explore the connection between normal and extensive form games.
Definition 1.6 (Equivalent). A normal form game (N, {Ai }, {ui }) is equivalent to an extensive form game with
players N , player i’s strategy space Si , and player i’s payoff function u′i if for each i ∈ N there exists a function hi
such that

6
 Power Round April 8, 2023

1. hi is a bijection from Ai to Si ;
2. for every action profile a1 , ..., an of the normal form game it holds that

u(a1 , ..., an ) = u′ (h1 (a1 ), ..., hn (an )).

Similarly, an extensive form game with players N , player i’s strategy space Si , and player i’s payoff function ui is
equivalent to a normal form game (N, A, u′ ) if for each i ∈ N there exists a function gi such that
1. gi is a bijection from Si to Ai ;
2. for every strategy profile s1 , ..., sn of the extensive form game it holds that

u(s1 , ..., sn ) = u′ (g1 (s1 ), ..., gn (sn )).

Finally, two normal form games or two extensive form games can similarly be equivalent if there exists a bijection
between action or strategy spaces that preserve payoffs.
Problem 1.12 (4 points). Show that tic-tac-toe2 is equivalent to the following:
• Two players take turns picking numbers from {1, 2, ..., 9} without repetition;
• If one player has previously selected three numbers that add to exactly 15, the game ends and they win;
• If all numbers have been selected and no player has won, the game ends in a tie.
Problem 1.13 (4 points). Show that a normal form game is equivalent to an extensive form game if and only if the
extensive form game is equivalent to the normal form game.
Problem 1.14 (6 points). Does every two-player extensive form game have an equivalent two player normal form
game? Justify your answer.
Problem 1.15 (6 points). Does every two-player normal form game have an equivalent two player extensive form
game? Justify your answer.

2 Mixed Strategies
Some games do not have Nash equilibrium in pure strategies. In particular, the game of rock-paper-scissors does not
have a pure strategy Nash equilibrium.
Problem 2.1 (2 points). Show that the game of rock-paper-scissors has no pure strategy Nash equilibrium.
Intuitively, when players play rock-paper-scissors, they end up randomizing over what to play (try playing against
your teammates). To formalize this, we define the following:
Definition 2.1 (Probability Distribution). A probability distribution over a set X is a function p : X → [0, 1] such
that X
p(x) = 1.
x∈X

Intuitively, p(x) is just the probability of event x happening. Let ∆X denote the set of all probability distributions
over the set X.
Definition 2.2 (Mixed Strategy Extension of a Normal Form Game). Consider the normal form game (N, {Ai }, {ui }).
The mixed-strategy extension of this normal form game is the game with:
• Players N ;
• Each player i ∈ N has action space ∆Ai with pi denoting a distribution in ∆Ai ;
• Each player i ∈ N has the payoff function

Uj (p1 , ..., pI ) = E[uj (a1 , ..., aI )]

2 Two players take turns choosing squares on a 3x3 grid without replacement. If one player has three squares in a row, column, or long

diagonal, the game ends and they win. If all squares are chosen with no winner, the game ends in a tie.

7
 Power Round April 8, 2023

where the expectation is with respect to a1 ∼ p1 , ..., aI ∼ pI .

In the two person case, if player one plays p1 and player two plays p2 then payoffs are
X X
U1 (p1 , p2 ) = p1 (x)p2 (y)u1 (x, y)
x∈A1 y∈A2

and X X
U2 (p1 , p2 ) = p1 (x)p2 (y)u2 (x, y).
x∈A1 y∈A2

In general, if player one plays p1 and the other players play p−1 , player one’s payoffs are
X
U1 (p1 , p−1 ) = p1 (x)U1 (δx , p−1 )
x∈A1

where δx is a point mass:

Definition 2.3 (Point Mass). Given a set X, a point mass distribution at x ∈ X is denoted by δx (·) and is defined
by (
1 if y = x
δx (y) =
0 if y ̸= x.

Definition 2.4 (Mixed Strategy Nash Equilibrium). A mixed strategy Nash Equilibrium of the game (N, {Ai }, {ui })
is any pure strategy Nash Equilibrium of the Mixed Strategy Extension (N, {∆Ai }, {Ui }).
Let’s turn back to rock-paper-scissors for an example. One possible probability distribution over moves is to play
rock, paper, and scissors each with probability 1/3. It turns out that both players doing this is a Nash equilibrium.
Problem 2.2 (2 points). Suppose player one plays rock, paper, and scissors each with probability 1/3. Show that
player two can not get strictly higher expected payoff than also playing each with probability 1/3.
What’s the connection between mixed strategies and pure strategies? A valid probability distribution is to set p(a) = 1
for some a ∈ X and p(x) = 0 for all x ̸= a. Recall that these distributions are called point masses.
Naturally, if both players play point masses, payoffs in the mixed strategy extension are equal to payoffs in the
original game. Formally, let (N, {∆Ai }, {Ui }) be the mixed-strategy extension of the game (N, {Ai }, {ui }). Then, for
any a ∈ A1 , b ∈ A2 , we have that

U1 (δa , δb ) = u1 (a, b) and U2 (δa , δb ) = u2 (a, b).

Problem 2.3 (1 point). Prove the above result.

Problem 2.4 (6 points). Suppose (p1 , p−1 ) is a mixed strategy Nash equilibrium of the game (N, {Ai }, {ui }) and
p1 (a) > 0, p1 (b) > 0. Show the following holds:

U1 (δa , p−1 ) = U1 (δb , p−1 ) = U1 (p1 , p−1 ).

Problem 2.5 (3 points). Find the mixed strategy Nash Equilibrium of the normal form game with payoff matrix:

X Y
A (10, 8) (4, 1)
B (2, 3) (5, 7)

Problem 2.6 (4 points). Find the mixed strategy Nash Equilibrium of the normal form game with payoff matrix:

X Y Z
A (2, −3) (−1, 0) (7, −1)
B (1, −1) (0, 5) (7, 1)
C (3, 10) (1, 4) (5, 7)

8
 Power Round April 8, 2023

Next, we investigate the question of what strategies might be played in equilibrium. On the opposite end of the
spectrum from best responses are dominated actions.
Definition 2.5 (Dominated Action). An action ai is a dominated action for player i of the mixed strategy extension
(N, {∆Ai }, {Ui }) if for all possible mixed strategies of the other players p−i , there exists pi such that

Ui (pi , p−i ) > Ui (δai , p−i ).

If this is the case, we also say that action ai is dominated by the strategy pi .
Problem 2.7 (4 points). Suppose action ai is dominated by some strategy pi such that pi (ai ) > 0 (action ai is played
with positive probability in strategy pi ). Show that action ai is dominated by some strategy p′i such that p′i (ai ) = 0
(action ai is never played in strategy p′i ).
Problem 2.8 (6 points). Show that an action ai is a dominated action if and only if it is never played with positive
probability in any best response to any opponent strategy.
One of the foundational results in game theory is that in any finite normal form game, there exists a Nash equilibrium
in mixed strategies. While this result in full generality is beyond the scope of this round, we will prove a limited
result in the case where there are two players, each player has two actions, and the game is zero-sum.
Definition 2.6 (Zero-Sum Game). A two-player game is zero-sum if for all action profiles a, we have that u1 (a) +
u2 (a) = 0.
Suppose player one can play a1 or a2 and player two can play b1 or b2 . Then, the payoff matrix for this game can be
written as

b1 b2
a1 (v11 , −v11 ) (v12 , −v12 )
a2 (v21 , −v21 ) (v22 , −v22 )

For the remainder of this section, this will be the game under consideration. In this case, each mixed strategy can
be represented by a single value: q1 for player one and q2 for player two so p1 (a1 ) = q1 , p1 (a2 ) = 1 − q1 and p2 (b1 ) =
q2 , p2 (b2 ) = 1 − q2 . Going forward, let “the mixed strategy q1 ” denote the mixed strategy p1 (a1 ) = q1 , p1 (a2 ) = 1 − q1
and “the mixed strategy q2 ” denote the mixed strategy p2 (b1 ) = q2 , p2 (b2 ) = 1 − q2 .
We will use the following facts to establish existence of Nash equilibrium in this case. Formal definitions for “contin-
uous”, “convex”, and “concave” will be introduced when needed for problems.
Fact 2.1 (Continuous Functions attain Max/Min). Suppose X and Y are closed intervals of R and f is a con-
tinuous function that maps X × Y to R. Then, there exists x1 , x2 ∈ X and y1 , y2 ∈ Y such that (x1 , y1 ) solves
maxx miny f (x, y) and (x2 , y2 ) solves miny maxx f (x, y).
Fact 2.2 (Min-Max Theorem). Suppose X and Y are closed intervals and f is a continuous function X × Y → R
such that
• holding ŷ fixed, f (x, ŷ) is convex in x for all ŷ;
• holding x̂ fixed, f (x̂, y) is concave in y for all x̂.
Then,
max min f (x, y) = min max f (x, y).
x y y x

Here, maxx miny f (x, y) should be interpreted as “x is chosen first to maximize the smallest value f (x, y) can take
over all possible y values” while miny maxx f (x, y) should be interpreted as “y is chosen first to minimize the largest
value f (x, y) can take over all possible x values”.
Overall, the proof will proceed as follows: first, we will show that Min-Max Theorem can be applied to this setting.
Then, we will use the Min-Max Theorem to find the values that achieve the min max. Finally, we show that those
values form a Nash Equilibrium.
Problem 2.9 (1 point). Identify each player’s set of possible mixed strategies with a closed interval.

9
 Power Round April 8, 2023

Problem 2.10 (3 points). Suppose player one plays the mixed strategy q1 and player two plays the mixed strategy
q2 . What is the expected payoff for player one in terms of v11 , v12 , v21 , v22 ?
Going forward, let V (q1 , q2 ) denote the expected payoff for player one when player one plays the mixed strategy q1
and player two plays the mixed strategy q2 .
Definition 2.7 (Continuous). A function f : X × Y → R is continuous if for every (x, y) ∈ X × Y and ϵ > 0, there
exists δ > 0 such that if the Euclidean distance between (x′ , y ′ ) and (x, y) is less than δ, then |f (x′ , y ′ ) − f (x, y)| < ϵ.
Problem 2.11 (6 points). Show that V (q1 , q2 ) is continuous.
Definition 2.8 (Convex/Concave). A function f : X → R is convex if for all t ∈ [0, 1] and x, x′ ∈ X it holds that

f (tx + (1 − t)x′ ) ≤ tf (x) + (1 − t)f (x′ ).

A function g : Y → R is concave if −g is convex.

Problem 2.12 (6 points). Show that V (q1 , q2 ) is convex in q1 holding q2 fixed and is also concave in q2 holding q1
fixed.
Problem 2.13 (4 points). Show that there exists q1∗ , q2∗ such that

V (q1∗ , q2∗ ) = max min V (q1 , q2 ) = min max V (q1 , q2 ).

q1 q2 q2 q1

Problem 2.14 (10 points). Show that q1∗ , q2∗ from the previous problem is a Nash Equilibrium of the two-player
two-action zero-sum game.

3 Application to Auctions and Competition

3.1 Second Price Auctions
The first application of game theory we analyze are second price auctions. The setting is as follows:
• There is some set of agents 1, 2, ..., n and a single good;
• Each agent i values the good at vi for i = 1, 2, ..., n (you may assume that all vi ’s are distinct);
• Each agent i bids some value bi for i = 1, 2, ..., n.
Each agent only knows their own value and bids are made simultaneously. After all bids are made, the agent that
submitted the highest bid wins the item and pays the second highest bid. All other agents do not receive the item
and pay nothing. If agent i obtains the object at price p, their utility is vi − p. Otherwise, if agent i does not the
obtain the object and does not pay anything, their utility is 0.
Problem 3.1 (2 points). Write agent i’s utility as a function of vi , b1 , b2 , ..., bn . In other words, define ui (b1 , ..., bn ).
Problem 3.2 (3 points). Suppose agent i wins the item and pays p > vi . Show that agent i has a profitable deviation
or prove that they do not.
Problem 3.3 (4 points). Suppose agent i wins the item and pays p ≤ vi . Show that agent i has a profitable deviation
or prove that they do not.
Problem 3.4 (5 points). Describe a Nash equilibrium of the second price auction. Justify that it is a Nash equilibrium.

3.2 First Price Auctions

First price auctions share the same environment as second price auctions. The one difference is that instead of paying
the second highest bid, the winner of the action (still the agent with the highest bid) pays their own bid. Payoffs are
still the same. While calculus is needed to derive the Nash equilibrium of first price auctions, we can still investigate
them a bit.
Problem 3.5 (2 points). Write agent i’s utility as a function of vi , b1 , b2 , ..., bn . In other words, define ui (b1 , ..., bn ).
Problem 3.6 (3 points). Suppose agent i wins the item and pays p = vi and there is some distance between each
bid. Show that agent i has a profitable deviation or prove that they do not.

10
 Power Round April 8, 2023

3.3 Competition
We now turn our attention to competition between firms. The setting here is as follows:
• There are two firms, each firm i = 1, 2 has a cost function ci (qi ) that describes the cost to firm i to produce qi
goods;
• There is an inverse demand function p(q) that describes the market price of each good when there are q total
goods in the market;
• Each firm’s utility function is their profit:

ui (qi , q−i ) = p(qi + q−i ) · qi − ci (qi )

for i = 1, 2.
Suppose p(q) = 22 − 2q, c1 (q1 ) = 6q1 , and c2 (q2 ) = 2q2 . The following fact may be useful:
Fact 3.1 (Maximum of a Quadratic). The function f (x) = −(x − a)(x − b) attains a maximum at x = a+b
2 .

Problem 3.7 (3 points). What is firm one’s best response to firm two playing q2∗ ?
Problem 3.8 (3 points). What is firm two’s best response to firm one playing q1∗ ?
Problem 3.9 (4 points). Find the Nash Equilibrium of the competition game if firms choose quantities simultane-
ously. What are equilibrium profits?
Problem 3.10 (4 points). Find the Subgame Perfect Nash Equilibrium of the competition game if firm one chooses
their quantity before firm two (and firm two can observe their choice before choosing their own quantity).
Problem 3.11 (4 points). Find the Subgame Perfect Nash Equilibrium of the competition game if firm two chooses
their quantity before firm one (and firm one can observe their choice before choosing their own quantity).

3.4 We Scream for Ice Cream

Congratulations on making it to the end of the power round! To celebrate, all 500 SMT participants go to the beach,
which happens to be 500 meters long so there is one person every meter. At each end of the beach is an ice cream
stand, suppose stand A is at meter 0 and stand B is at meter 500 on the beach. Stand A charges price pA and stand
B charges price pB . The overall cost to buy ice cream from a stand is equal to the price charged by the stand plus
the distance to the stand (so for someone at meter 50, the cost to buy ice cream from stand A is 50 + pA and the cost
to buy ice cream from stand B is 450 + pB ). Each of the 500 SMT participants buys ice cream from the stand that
has a lower overall cost. If a participant is indifferent between the two stands, they choose one to go to at random.
Each ice cream stand’s payoff is equal to the price they charge multiplied by the number of people they serve.
Problem 3.12 (2 points). At what meter is the cost to going to stand A equal to the cost of going to stand B if
stand A charges pA and stand B charges pB ?
Problem 3.13 (2 points). Write each stand’s profits as a function of pA and pB .
Problem 3.14 (6 points). What prices do the two firms charge in equilibrium?
Problem 3.15 (8 points). Suppose a better wooden boardwalk on the beach decreases the cost of walking, making the
overall cost of buying ice cream equal to the price plus half the distance travelled. What is the new equilibrium? In
this new equilibrium, do the ice cream stands make more or less money?

11