<p>This is a pretty general algorithm, you can probably tailor a better one to your specific problem.</p>

<p>If you stick to this discreet strategy space it seems to me you would have to find the equilibria via brute force. Basically you would look at all bid profiles $(x_1,x_2,x_3)$ and check whether it is an equilibrium. To do this, you would have to check if player 1 would be better off by making another bid. Let us denote the payoff of player 1 by $\pi_1$. This is a function of the bids. Let's assume $x_2 &gt; x_3 + 1$. Then you would have to check
\begin{eqnarray*}
\pi_1(x_1,x_2,x_3) &amp; \geq &amp; \pi_1(x_2+1,x_2,x_3) \\
\\
\pi_1(x_1,x_2,x_3) &amp; \geq &amp; \pi_1(x_2-1,x_2,x_3) \\
\\
\pi_1(x_1,x_2,x_3) &amp; \geq &amp; \pi_1(x_3-1,x_2,x_3) \\
\\
\end{eqnarray*}
If all these and the corresponding inequialites for other players hold then you have found an equilibrium.</p>

<p>If $x_2 = x_3 + 1$ you need to take the tie breaking rule into consideration.</p>

<p>You could limit the number of profiles $(x_1,x_2,x_3)$ you check by reasoning about the reservation prices. (E.g. for any N.E. where someone bids higher than their reservation price you have an N.E. where they bid just that.)</p>

CC BY-SA 3.0
2015-06-05T10:20:07.263Z
Thank you for your answer. But I have no clue why you're stressing discrete space. My feeling is that restricting to discrete strategy space only serves  characterizing an best response easier.
Metta World Peace
CC BY-SA 3.0
2015-06-05T10:12:31.460Z
2015-06-05T10:22:01.847Z
2015-06-05T10:22:01.847Z
Giskard
<p>Suppose three advertisers, I, II, III are participating in an auction for three positions for online advertising, top, middle and bottom. Assume that click per second  for a position is not affected by who poses an advertisement there. For top, the click through rate is 3 click per second, for middle, it's 2, for bottom, it's 1. But advertisers have private value per click. For I, it's \$16 per click. For II, it's \$15. For III, it's \$14. The one who submits the highest wins the top position and pays the second highest bid, second highest bidder got the middle position and pays the third highest bid. The third highest bidder end up with bottom position, but pays zero. If there's a tie, then choose the winner ramdomly by a fair dice. The strategy space for each bidder is $\mathbb{R}_{+}$.</p>

<p>There're a lot of NE for this game. For example, I,II,III simultaneously submit bids of, \$7 per click, \$9 per click, \$11 per click respectively. Their payoff will be $1 \times (16-0)$ dollars, $2\times (15-7)$ dollars, and $3 \times (14-9)$ dollars respectively. </p>

<p>$$
\begin{array}{c|l|c|r}
\hline
 &amp;(0,7) &amp; (7,9) &amp; (9,11) &amp; (11, +\infty)\\
\hline
\text{player I}&amp; \color{blue}{16}  &amp;  \color{blue}{16}  &amp; 2(16-9)=14&amp; 3(16-11)=15 \\ 
\hline
\text{player II}&amp; 15 &amp; 2(15-7)=\color{blue}{16} &amp; 2(15-7)=\color{blue}{16}&amp; 3(15-11)=12 \\ 
\hline
\text{player III}&amp; 14 &amp; 2(14-7)=14 &amp; 3(14-9)= \color{blue}{15} &amp; 3(14-9)= \color{blue}{15}\\ 
\hline
\end{array}
$$</p>

<p>How to find other NE?</p>

<p><strong>Added</strong>: I want to study this numerical example, because I want to understand better the motivation of <a href="http://users.cms.caltech.edu/~adamw/courses/241/lectures/search2.pdf" rel="nofollow">this paper</a>.</p>

CC BY-SA 3.0
2015-06-05T09:55:40.463Z
The strategy set is not convex at all, right? So you cannot bid \$10.95? Nor can you bid \$10 with 50% probability and \$11 with 50% probability?
Giskard
CC BY-SA 3.0
2015-06-05T09:56:07.503Z
@denesp I have to admit I haven't thought about this. Before your comment, I only want to have an idea how severe the equilibria multiplicity problem arises in GSPA.
Metta World Peace
CC BY-SA 3.0
2015-06-05T09:58:50.870Z
I think in GSPA the bidding space is usually convex, so you could place any real number as a bid. Then the example you provided would not be an equilibrium.
Giskard
CC BY-SA 3.0
2015-06-05T10:04:51.053Z
Also I think you have to provide a tie breaking rule for equal bids.
Giskard
CC BY-SA 3.0
2015-06-05T10:07:24.970Z
@denesp I should admit I only started studying auction very recently, so I'm not familiar with the convention in this field.  I check it again but still feel it's an NE. I thought about tie breaking as flipping a coin, and felt it might not be important. Because it seems to me it can't be the case there 's a tie in an NE.
Metta World Peace
CC BY-SA 3.0
2015-06-05T10:15:40.900Z
Are you aware of Varian (2006): "Position auctions", *Inernational Journal of Industrial Organization*, where the set of equilibria in this game are characterised?
Ubiquitous
CC BY-SA 3.0
2015-06-05T10:16:59.677Z
@Ubiquitous Thank you for reminding me of this. I will take a look at it.
Metta World Peace
<mechanism-design><auctions><algorithms><search-and-matching>
Is there an algorithm to find as many NE as possible in this generalized second price auction?
Metta World Peace
# Is there an algorithm to find as many NE as possible in this generalized second price auction?

(Asked by: username_0 on 2015-06-05)

Suppose three advertisers, I, II, III are participating in an auction for three positions for online advertising, top, middle and bottom. Assume that click per second for a position is not affected by who poses an advertisement there. For top, the click through rate is 3 click per second, for middle, it's 2, for bottom, it's 1. But advertisers have private value per click. For I, it's \$16 per click. For II, it's \$15. For III, it's \$14. The one who submits the highest wins the top position and pays the second highest bid, second highest bidder got the middle position and pays the third highest bid. The third highest bidder end up with bottom position, but pays zero. If there's a tie, then choose the winner ramdomly by a fair dice. The strategy space for each bidder is $\mathbb{R}\_{+}$.

There're a lot of NE for this game. For example, I,II,III simultaneously submit bids of, \$7 per click, \$9 per click, \$11 per click respectively. Their payoff will be $1 \times (16-0)$ dollars, $2\times (15-7)$ dollars, and $3 \times (14-9)$ dollars respectively.

$$
\begin{array}{c|l|c|r}
\hline
&(0,7) & (7,9) & (9,11) & (11, +\infty)\\
\hline
\text{player I}& \color{blue}{16} & \color{blue}{16} & 2(16-9)=14& 3(16-11)=15 \\
\hline
\text{player II}& 15 & 2(15-7)=\color{blue}{16} & 2(15-7)=\color{blue}{16}& 3(15-11)=12 \\
\hline
\text{player III}& 14 & 2(14-7)=14 & 3(14-9)= \color{blue}{15} & 3(14-9)= \color{blue}{15}\\
\hline
\end{array}
$$

How to find other NE?

**Added**: I want to study this numerical example, because I want to understand better the motivation of [this paper](http://users.cms.caltech.edu/~adamw/courses/241/lectures/search2.pdf).

**Tags:** mechanism-design, auctions, algorithms, search-and-matching

> **Comments:**
> **username_1**: The strategy set is not convex at all, right? So you cannot bid \$10.95? Nor can you bid \$10 with 50% probability and \$11 with 50% probability?  
> **username_0**: @denesp I have to admit I haven't thought about this. Before your comment, I only want to have an idea how severe the equilibria multiplicity problem arises in GSPA.  
> **username_1**: I think in GSPA the bidding space is usually convex, so you could place any real number as a bid. Then the example you provided would not be an equilibrium.  
> **username_1**: Also I think you have to provide a tie breaking rule for equal bids.  
> **username_0**: @denesp I should admit I only started studying auction very recently, so I'm not familiar with the convention in this field.  I check it again but still feel it's an NE. I thought about tie breaking as flipping a coin, and felt it might not be important. Because it seems to me it can't be the case there 's a tie in an NE.  
> **username_2**: Are you aware of Varian (2006): "Position auctions", *Inernational Journal of Industrial Organization*, where the set of equilibria in this game are characterised?  
> **username_0**: @username_2 Thank you for reminding me of this. I will take a look at it.  

---

## 1 answers

### Answer by username_1 on 2015-06-05. Score: 1

This is a pretty general algorithm, you can probably tailor a better one to your specific problem.

If you stick to this discreet strategy space it seems to me you would have to find the equilibria via brute force. Basically you would look at all bid profiles $(x\_1,x\_2,x\_3)$ and check whether it is an equilibrium. To do this, you would have to check if player 1 would be better off by making another bid. Let us denote the payoff of player 1 by $\pi\_1$. This is a function of the bids. Let's assume $x\_2 > x\_3 + 1$. Then you would have to check
\begin{eqnarray\*}
\pi\_1(x\_1,x\_2,x\_3) & \geq & \pi\_1(x\_2+1,x\_2,x\_3) \\
\\
\pi\_1(x\_1,x\_2,x\_3) & \geq & \pi\_1(x\_2-1,x\_2,x\_3) \\
\\
\pi\_1(x\_1,x\_2,x\_3) & \geq & \pi\_1(x\_3-1,x\_2,x\_3) \\
\\
\end{eqnarray\*}
If all these and the corresponding inequialites for other players hold then you have found an equilibrium.

If $x\_2 = x\_3 + 1$ you need to take the tie breaking rule into consideration.

You could limit the number of profiles $(x\_1,x\_2,x\_3)$ you check by reasoning about the reservation prices. (E.g. for any N.E. where someone bids higher than their reservation price you have an N.E. where they bid just that.)

> **Comments:**
> **username_0**: Thank you for your answer. But I have no clue why you're stressing discrete space. My feeling is that restricting to discrete strategy space only serves  characterizing an best response easier.  

---

