# Auctions and finding nash equilibrium of a dynamic game

Suppose we have a sequential version of an Auction game: • Player 1 places a bid. • Player 2 observes player 1’s bid, then places a bid. • The player with the highest bid wins the item at auction. • In case of a tie, the winner is determined randomly (with equal probability among those tied). • The winning player pays his bid. Two players bid for a rare bottle of Scotch. This is an auction in which they can bid any amount in $$\Bbb R_+$$. Suppose the two players both value the item at £500.

Find all pure-strategy Nash equilibria of this game.

The answer provided didn't seem too intuitive:

1. Player 1’s strategy is to bid 500.
2. At the information set following 1 bidding 500, Player 2’s bid is in [0, 500].
3. At all information sets where 1 bids any x1 below 500, Player 2 bid is in (x1, $$\infty$$).
4. At all information sets where 1 bids above 500, Player 2 bids anything in $$\Bbb R_+$$.

I somehow get that we do NOT need to consider sequential rationality, but how does point 4 follow i.e P2 bids anything in $$\Bbb R_+$$?

Any help will be greatly appreciated.

Let's first determine the sets of actions of the players.

An action of player 1 is simply a bid $$x_1 \in \mathbb{R}_+$$.

An action of player 2 is a function: $$f_2: \mathbb{R}_+ \to \mathbb{R}_+$$ that determines for every action $$x_1$$ of Player $$1$$ an action $$x_2 = f_2(x_1) \in \mathbb{R}_+$$. Let us denote by $$F_2$$ the set of all actions of player 2.

Let's now look at the payoffs: \begin{align*} u_1(x_1, f_2) &= \left\{\begin{array}{ll} 500 - x_1 &\text{ if } x_1 > f_2(x_1)\\ \frac{500 - x_1}{2} &\text{ if } x_1 = f_2(x_1),\\ 0 &\text{ if } x_1 < f_2(x_1)\end{array}\right.\\ u_2(x_1, f_2) &= \left\{\begin{array}{ll} 500 - f_2(x_1) &\text{ if } f_2(x_1) > x_1\\ \frac{500 - f_2(x_1)}{2} &\text{ if } x_1 = f_2(x_1),\\ 0 &\text{ if } f_2(x_1) < x_1 \end{array}\right. \end{align*}

A strategy profile $$(x_1^\ast, f_2^\ast)$$ is a Nash equilibrium iff for all other $$(x_1, f_2)$$ $$u_1(x_1^\ast, f_2^\ast) \ge u_1(x_1, f_2^\ast),\\ u_2(x_1^\ast, f_2^\ast) \ge u_1(x_1^\ast, f_2).$$

Claim 1: If $$(x_1^\ast, f_2^\ast)$$ is a Nash equilibrium and if $$x_1^\ast < 500$$, then $$f_2^\ast(x_1^\ast) \in (x_1^\ast, 500)$$.

proof: Assume not, then either $$f_2^\ast(x_1^\ast) \le x_1^\ast$$ or $$f_2^\ast(x_1^\ast) \ge 500$$. Notice that $$u_2(x_1^\ast, f_2^\ast) \le 0$$. Now take the strategy $$f_2$$ where $$f_2(x_1) = f_2^\ast(x_1)$$ for all $$x_1 \ne x_1^\ast$$ and $$f_2(x_1^\ast) = (500 +2 x_1^\ast)/3 > x_1^\ast$$ . Then: $$> u_2(x_1^\ast, f_2) = 500 - \frac{500 + 2 x_1}{3} > \frac{500 - x_1^\ast}{2} \ge u_2(x_1^\ast, f_2^\ast), >$$ Contradicting the definition of a Nash equilibrium.

Claim 2: If $$(x_1^\ast, f_2^\ast)$$ is a Nash equilibrium and if $$x_1^\ast = 500$$, then $$f_2^\ast(x_1^\ast) \le 500$$.

proof: Towards a contradiction, assume that $$f_2^\ast(x_1^\ast) > 500$$. Take the strategy $$f_2$$ where $$f_2(x_1) = 500$$ for all $$x_1$$. Then: $$> u_2(x_1^\ast, f_2^\ast) = 500 - f_2^\ast(x_1^\ast) < 0 = u_2(x_1^\ast, f_2) >$$ This contradicts the definition of a Nash equilibrium.

Claim 3: If $$(x_1^\ast, f_2^\ast)$$ is a Nash equilibrium and if $$x_1^\ast > 500$$ then $$f_2^\ast(x_1^\ast) < x_1^\ast$$.

proof: Towards a contradiction, assume that $$f_2^\ast(x_1^\ast) \ge x_1^\ast$$. Take the strategy $$f_2$$ where $$f_2(x_1) = 500$$ for all $$x_1$$. Then: $$> u_2(x_1^\ast, f_2^\ast) \le \frac{500 - x_1^\ast}{2} < 0 = u_2(x_1^\ast, f_2). >$$ This contradicts the definition of a Nash equilibrium

Claim 4: If $$(x_1^\ast, f_2^\ast)$$ is a Nash equilibrium, then $$x_1^\ast \le 500$$.

proof: Towards a contradiction, if $$x_1^\ast > 500$$ then we know from Claim 3 that that $$f_2^\ast(x_1) < x_1^\ast$$. As such: $$> u_1(x_1^\ast, f_2^\ast) = 500 - x_1^\ast < 0 \le u_1(500, f_2^\ast). >$$ This contradicts the assumption of a Nash equilibrium.

Claim 5: There is no Nash equilibrium $$(x_1^\ast, f_2^\ast)$$ with $$x_1^\ast < 500$$.

proof: Assume that $$(x_1^\ast, f_2^\ast)$$ is a Nash equilibrium with $$x_1^\ast < 500$$. From Claim 1, we know that $$f_2^\ast \in (x_1^\ast, 500)$$. Take the strategy $$f_2$$ where $$f_2(x_1) = \frac{x_1 + f_2^\ast(x_1)}{2}$$. Notice that $$f_2(x_1^\ast) > x_1^\ast$$. Then: $$> u_2(x_1^\ast, f_2) = 500 - \frac{x_1 + f_2(x_1^\ast)}{2} > u_2(x_1^\ast, f_2^\ast), >$$ This contradicts the assumption of a Nash equilibrium

Claim 6: There is no Nash equilibrium $$(x_1^\ast, f_2^\ast)$$ with $$x_1^\ast > 500$$.

proof: Towards a contradiction, assume that $$(x_1^\ast, f_2^\ast)$$ is a Nash equilibrium and $$x_1^\ast > 500$$. From Claim 3, we know that $$f_2^\ast(x_1^\ast) < x_1^\ast$$. Then: $$> u_1(x_1^\ast, f_2^\ast) = 500 - x_1^\ast < 0 = u_1(500, f_2^\ast). >$$ Again a contradiction with the definition of a Nash equilibrium

The last two theorems show that if there is a Nash equilibrium $$(x_1^\ast, f_2^\ast)$$, then $$x_1^\ast = 500$$.

Claim 7 if $$(x_1^\ast, f_2^\ast)$$ is a Nash equilibrium then for all $$x_1 < 500$$, we have $$f_2^\ast(x_1) > x_1$$.

proof: Towards a contradiction, let $$x_1 < 500$$ and $$f_2^\ast(x_1) \le x_1$$ then: $$> u_1(x_1, f_2^\ast) \ge \frac{500 - x_1}{2} > 0 = u_1(x_1^\ast, f_2^\ast), >$$ A contradiction with the definition of a Nash equilibrium

Claim 8 A strategy profile $$(x_1^\ast, f_2^\ast)$$ is a Nash equilibrium if and only if it of the following form: $$x_1^\ast = 500,\\ f_2^\ast(x_1) = \left\{\begin{array}{ll} \in [0,500] &\text{ if } x_1 = 500,\\ \in (x_1, + \infty) &\text{ if } x_1 < 500,\\ \in \mathbb{R}_+ &\text{ if } x_1 > 500. \end{array}\right.$$

proof: $$(\rightarrow)$$ If $$(x_1^\ast, f_2^\ast)$$ is a Nash equilibrium, then $$x_1^\ast = 500$$ follows from Claim 5 and 6. Next, $$f_2^\ast(500) = f_2^\ast(x_1^\ast) \in [0, 500]$$ follows from Claim 2. $$f_2(x_1) \in (x_1, + \infty)$$ for $$x_1 < 500$$ follows from Claim 7. Finally, that $$f_2^\ast(x) \in \mathbb{R}_+$$ for $$x > 500$$ is obvious.

$$(\leftarrow)$$ Assume that $$x_1^\ast = 500$$ and that $$f_2^\ast$$ satisfies the restrictions in the claim. Notice that: $$u_1(x_1^\ast, f_2^\ast) = 0$$ and $$u_2(x_1^\ast, f_2^\ast) = 0$$.

Also, for all $$f_2 \in F_2$$, $$u_2(x_1^\ast, f_2) \le 0$$ and for all $$x_1 \in \mathbb{R}_+$$, we have $$u_1(x_1) \le 0$$. As such: $$> u_2(x_1^\ast, f_2) \le 0 = u_2(x_1^\ast, f_2^\ast),\\ > u_1(x_1, f_2^\ast) \le 0 = u_1(x_1^\ast, f_2^\ast). >$$ So $$(x_1^\ast, f_2^\ast)$$ is a Nash equilibrium.

You are only required to get Nash equilibria and not sequentially rational/subgame perfect equilibria. Hence Player 2's actions at information sets that do not occur (that do not reflect Player 1's actual strategy) do not need to be best responses. All you have to make sure is that no one is better off by deviating.

In case 4., regardless of what Player 2 does, Player 1 cannot get a positive surplus; she wins with a higher than 500 bid or loses. This is not better for her than bidding 500 and losing.