Is there an algorithm to find as many NE as possible in this generalized second price auction?

Question

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.

Answer 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.)