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

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.

• 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 Jun 5 '15 at 9:55 • @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 Jun 5 '15 at 9:56 • 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 Jun 5 '15 at 9:58 • Also I think you have to provide a tie breaking rule for equal bids. – Giskard Jun 5 '15 at 10:04 • @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 Jun 5 '15 at 10:07 ## 1 Answer 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.)

• 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 Jun 5 '15 at 10:20