<p>Let's first determine the sets of actions of the players.</p>
<p>An action of player 1 is simply a bid <span class="math-container">$x_1 \in \mathbb{R}_+$</span>.</p>
<p>An action of player 2 is a function: <span class="math-container">$f_2: \mathbb{R}_+ \to \mathbb{R}_+$</span> that determines for every action <span class="math-container">$x_1$</span> of Player <span class="math-container">$1$</span> an action <span class="math-container">$x_2 = f_2(x_1) \in \mathbb{R}_+$</span>. Let us denote by <span class="math-container">$F_2$</span> the set of all actions of player 2.</p>
<p>Let's now look at the payoffs:
<span class="math-container">$$
\begin{align*}
u_1(x_1, f_2) &amp;= \left\{\begin{array}{ll} 500 - x_1 &amp;\text{ if } x_1 &gt; f_2(x_1)\\ \frac{500 - x_1}{2} &amp;\text{ if } x_1 = f_2(x_1),\\
0 &amp;\text{ if } x_1 &lt; f_2(x_1)\end{array}\right.\\
u_2(x_1, f_2) &amp;= \left\{\begin{array}{ll} 500 - f_2(x_1) &amp;\text{ if } f_2(x_1) &gt; x_1\\ \frac{500 - f_2(x_1)}{2} &amp;\text{ if } x_1 = f_2(x_1),\\
0 &amp;\text{ if } f_2(x_1) &lt; x_1 \end{array}\right.
\end{align*}
$$</span></p>
<p>A strategy profile <span class="math-container">$(x_1^\ast, f_2^\ast)$</span> is a <em>Nash equilibrium</em> iff for all other <span class="math-container">$(x_1, f_2)$</span>
<span class="math-container">$$
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).
$$</span></p>
<p><strong>Claim 1:</strong> If <span class="math-container">$(x_1^\ast, f_2^\ast)$</span> is a Nash equilibrium and if <span class="math-container">$x_1^\ast &lt; 500$</span>, then <span class="math-container">$f_2^\ast(x_1^\ast) \in (x_1^\ast, 500)$</span>.</p>
<blockquote>
<p><em>proof</em>: Assume not, then either <span class="math-container">$f_2^\ast(x_1^\ast) \le x_1^\ast$</span> or <span class="math-container">$f_2^\ast(x_1^\ast) \ge 500$</span>. Notice that <span class="math-container">$u_2(x_1^\ast, f_2^\ast) \le 0$</span>.  Now take the strategy <span class="math-container">$f_2$</span> where <span class="math-container">$f_2(x_1) = f_2^\ast(x_1)$</span> for all <span class="math-container">$x_1 \ne x_1^\ast$</span> and <span class="math-container">$f_2(x_1^\ast) = (500 +2 x_1^\ast)/3 &gt; x_1^\ast$</span> . Then:
<span class="math-container">$$
&gt; u_2(x_1^\ast, f_2) = 500 - \frac{500 + 2 x_1}{3} &gt; \frac{500 - x_1^\ast}{2} \ge u_2(x_1^\ast, f_2^\ast),
&gt; $$</span>
Contradicting the definition of a Nash equilibrium.</p>
</blockquote>
<p><strong>Claim 2:</strong> If <span class="math-container">$(x_1^\ast, f_2^\ast)$</span> is a Nash equilibrium and if <span class="math-container">$x_1^\ast = 500$</span>, then <span class="math-container">$f_2^\ast(x_1^\ast) \le 500$</span>.</p>
<blockquote>
<p><em>proof:</em> Towards a contradiction, assume that <span class="math-container">$f_2^\ast(x_1^\ast) &gt; 500$</span>. Take the strategy <span class="math-container">$f_2$</span> where <span class="math-container">$f_2(x_1) = 500$</span> for all <span class="math-container">$x_1$</span>. Then:
<span class="math-container">$$
&gt; u_2(x_1^\ast, f_2^\ast) = 500 - f_2^\ast(x_1^\ast) &lt; 0 = u_2(x_1^\ast, f_2)
&gt; $$</span>
This contradicts the definition of a Nash equilibrium.</p>
</blockquote>
<p><strong>Claim 3:</strong> If <span class="math-container">$(x_1^\ast, f_2^\ast)$</span> is a Nash equilibrium and if <span class="math-container">$x_1^\ast &gt; 500$</span> then <span class="math-container">$f_2^\ast(x_1^\ast) &lt; x_1^\ast$</span>.</p>
<blockquote>
<p><em>proof:</em>  Towards a contradiction, assume that <span class="math-container">$f_2^\ast(x_1^\ast) \ge x_1^\ast$</span>. Take the strategy <span class="math-container">$f_2$</span> where <span class="math-container">$f_2(x_1) = 500$</span> for all <span class="math-container">$x_1$</span>. Then:
<span class="math-container">$$
&gt; u_2(x_1^\ast, f_2^\ast) \le \frac{500 - x_1^\ast}{2} &lt; 0 = u_2(x_1^\ast, f_2).
&gt; $$</span>
This contradicts the definition of a Nash equilibrium</p>
</blockquote>
<p><strong>Claim 4:</strong> If <span class="math-container">$(x_1^\ast, f_2^\ast)$</span> is a Nash equilibrium, then <span class="math-container">$x_1^\ast \le 500$</span>.</p>
<blockquote>
<p><em>proof</em>: Towards a contradiction, if <span class="math-container">$x_1^\ast &gt; 500$</span> then we know from Claim 3 that that <span class="math-container">$f_2^\ast(x_1) &lt; x_1^\ast$</span>. As such:
<span class="math-container">$$
&gt; u_1(x_1^\ast, f_2^\ast) = 500 - x_1^\ast &lt; 0 \le u_1(500, f_2^\ast).
&gt; $$</span>
This contradicts the assumption of a Nash equilibrium.</p>
</blockquote>
<p><strong>Claim 5:</strong> There is no Nash equilibrium <span class="math-container">$(x_1^\ast, f_2^\ast)$</span> with <span class="math-container">$x_1^\ast &lt; 500$</span>.</p>
<blockquote>
<p><em>proof:</em> Assume that <span class="math-container">$(x_1^\ast, f_2^\ast)$</span> is a Nash equilibrium with <span class="math-container">$x_1^\ast &lt; 500$</span>. From Claim 1, we know that <span class="math-container">$f_2^\ast \in (x_1^\ast, 500)$</span>. Take the strategy <span class="math-container">$f_2$</span> where <span class="math-container">$f_2(x_1) = \frac{x_1 + f_2^\ast(x_1)}{2}$</span>. Notice that <span class="math-container">$f_2(x_1^\ast) &gt; x_1^\ast$</span>. Then:
<span class="math-container">$$
&gt; u_2(x_1^\ast, f_2) = 500 - \frac{x_1 + f_2(x_1^\ast)}{2} &gt; u_2(x_1^\ast, f_2^\ast),
&gt; $$</span>
This contradicts the assumption of a Nash equilibrium</p>
</blockquote>
<p><strong>Claim 6:</strong> There is no Nash equilibrium <span class="math-container">$(x_1^\ast, f_2^\ast)$</span> with <span class="math-container">$x_1^\ast &gt; 500$</span>.</p>
<blockquote>
<p><em>proof:</em> Towards a contradiction, assume that <span class="math-container">$(x_1^\ast, f_2^\ast)$</span> is a Nash equilibrium and <span class="math-container">$x_1^\ast &gt; 500$</span>. From Claim 3, we know that <span class="math-container">$f_2^\ast(x_1^\ast) &lt; x_1^\ast$</span>. Then:
<span class="math-container">$$
&gt; u_1(x_1^\ast, f_2^\ast) = 500 - x_1^\ast &lt; 0  = u_1(500, f_2^\ast).
&gt; $$</span>
Again a contradiction with the definition of a Nash equilibrium</p>
</blockquote>
<p>The last two theorems show that if there is a Nash equilibrium <span class="math-container">$(x_1^\ast, f_2^\ast)$</span>, then <span class="math-container">$x_1^\ast = 500$</span>.</p>
<p><strong>Claim 7</strong> if <span class="math-container">$(x_1^\ast, f_2^\ast)$</span> is a Nash equilibrium then for all <span class="math-container">$x_1 &lt; 500$</span>, we have <span class="math-container">$f_2^\ast(x_1) &gt; x_1$</span>.</p>
<blockquote>
<p><em>proof:</em> Towards a contradiction, let <span class="math-container">$x_1 &lt; 500$</span> and <span class="math-container">$f_2^\ast(x_1) \le x_1$</span> then:
<span class="math-container">$$
&gt; u_1(x_1, f_2^\ast) \ge \frac{500 - x_1}{2} &gt; 0 = u_1(x_1^\ast, f_2^\ast),
&gt; $$</span>
A contradiction with the definition of a Nash equilibrium</p>
</blockquote>
<p><strong>Claim 8</strong> A strategy profile <span class="math-container">$(x_1^\ast, f_2^\ast)$</span> is a Nash equilibrium if and only if it of the following form:
<span class="math-container">$$
x_1^\ast = 500,\\
f_2^\ast(x_1) = \left\{\begin{array}{ll} \in [0,500] &amp;\text{ if } x_1 = 500,\\
\in (x_1, + \infty) &amp;\text{ if } x_1 &lt; 500,\\
\in \mathbb{R}_+ &amp;\text{ if } x_1 &gt; 500. \end{array}\right.
$$</span></p>
<blockquote>
<p><em>proof:</em> <span class="math-container">$(\rightarrow)$</span> If <span class="math-container">$(x_1^\ast, f_2^\ast)$</span> is a Nash equilibrium, then <span class="math-container">$x_1^\ast = 500$</span> follows from Claim 5 and 6. Next, <span class="math-container">$f_2^\ast(500) = f_2^\ast(x_1^\ast) \in [0, 500]$</span> follows from Claim 2. <span class="math-container">$f_2(x_1) \in (x_1, + \infty)$</span> for <span class="math-container">$x_1 &lt; 500$</span> follows from Claim 7. Finally, that <span class="math-container">$f_2^\ast(x) \in \mathbb{R}_+$</span> for <span class="math-container">$x &gt; 500$</span> is obvious.</p>
<p><span class="math-container">$(\leftarrow)$</span> Assume that <span class="math-container">$x_1^\ast = 500$</span> and that <span class="math-container">$f_2^\ast$</span> satisfies the restrictions in the claim. Notice that: <span class="math-container">$u_1(x_1^\ast, f_2^\ast) = 0$</span> and <span class="math-container">$u_2(x_1^\ast, f_2^\ast) = 0$</span>.</p>
<p>Also, for all <span class="math-container">$f_2 \in F_2$</span>, <span class="math-container">$u_2(x_1^\ast, f_2) \le 0$</span> and for all <span class="math-container">$x_1 \in \mathbb{R}_+$</span>, we have <span class="math-container">$u_1(x_1) \le 0$</span>. As such:
<span class="math-container">$$
&gt; u_2(x_1^\ast, f_2) \le 0 = u_2(x_1^\ast, f_2^\ast),\\
&gt; u_1(x_1, f_2^\ast) \le 0 = u_1(x_1^\ast, f_2^\ast).
&gt; $$</span>
So <span class="math-container">$(x_1^\ast, f_2^\ast)$</span> is a Nash equilibrium.</p>
</blockquote>

CC BY-SA 4.0
2021-05-05T07:13:51.263Z
2021-05-05T07:13:51.263Z
tdm
<p>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.</p>
<p>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.</p>

CC BY-SA 4.0
2021-05-05T07:07:02.900Z
2021-05-05T07:21:49.317Z
2021-05-05T07:21:49.317Z
Giskard
<p>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 <span class="math-container">$\Bbb R_+$</span>. Suppose the two players both value the item at £500.</p>
<p>Find all pure-strategy Nash equilibria of this game.</p>
<p>The answer provided didn't seem too intuitive:</p>
<ol>
<li>Player 1’s strategy is to bid 500.</li>
<li>At the information set following 1 bidding 500, Player 2’s bid is in [0, 500].</li>
<li>At all information sets where 1 bids any x1 below 500, Player 2 bid is in (x1, <span class="math-container">$\infty$</span>).</li>
<li>At all information sets where 1 bids above 500, Player 2 bids anything in <span class="math-container">$\Bbb R_+$</span>.</li>
</ol>
<p>I somehow get that we do NOT need to consider sequential rationality, but how does point 4 follow i.e P2 bids anything in <span class="math-container">$\Bbb R_+$</span>?</p>
<p>Any help will be greatly appreciated.</p>

<game-theory><nash-equilibrium><auctions><rationality>
Auctions and finding nash equilibrium of a dynamic game
jeff123
# Auctions and finding nash equilibrium of a dynamic game

(Asked by: username_0 on 2021-05-05)

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.

**Tags:** game-theory, nash-equilibrium, auctions, rationality

---

## 2 answers

### Answer by username_1 on 2021-05-05. Score: 6

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.


---

### Answer by username_2 on 2021-05-05. Score: 6

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.


---

