I was reading this paper on position auctions for web ads. Basically, there are N slots each with an expected number of clicks (in a particular time period) $x$. Each agent makes a bid $B_i$ of how much they are willing to pay per click. The bids are put in decreasing order and agent who makes the $i^\text{th}$ highest bid receives receives the slot with the $i^\text{th}$ highest click through rate for a price $P_i$ equal to $B_{i+1}$ (except for the last agent who pays nothing).

To obtain the least price to win the $i^\text{th}$ slot, we note that we have to beat the $i^\text{th}$ agent's bid if we are moving up, but that we only have to beat the $i^\text{th}$ agents price if we are moving down. We easily obtain the following equations for Nash Equilibria:

$(v_s-p_s)x_s\ge(v_s-p_t)x_t$ for $t>s$

$(v_s-p_s)x_s\ge(v_s-P_{t-1})x_t$ for $t < s$

The paper then defines the symmetric Nash equilibrium to be a set of prices with:

$(v_s-p_s)x_s\ge(v_s-p_t)x_t$ for all $t$ and $s$

Basically, instead of having the second part of the previous conditions, the first part of the previous equations is valid anywhere.

Is the symmetric Nash equilibrium defined more generally? In particular, is it the same as the symmetric equilibrium in this Wikipedia article

  • $\begingroup$ I don't know how to write the subscript B_(i+1) yet :-( $\endgroup$ – Casebash Aug 3 '10 at 11:02
  • $\begingroup$ $B_{i+1}$. Note braces. $\endgroup$ – Doug Chatham Aug 3 '10 at 11:34
  • $\begingroup$ @Doug: Thanks. I still have $t<s$ showing up as $t though :-( $\endgroup$ – Casebash Aug 3 '10 at 11:43
  • 2
    $\begingroup$ @Casebash: Type \ge for ≥ $\endgroup$ – kennytm Aug 3 '10 at 16:58
  • 2
    $\begingroup$ Changed the $\ge$'s and superscripted the $i$th's. $\endgroup$ – Larry Wang Aug 3 '10 at 20:26

The notion "symmetric equilibrium" (the one from Wikipedia article) is not applicable here, because the game is not symmetric (different players have different "profits per click").

I've a look at the paper and I think, that "symmetric Nash equilibrium" in your case is nothing but technically convenient case of Nash equilibrium (the latter is not unique in your case).

Also I've noted a probable misprint in the proof of the "Fact 1". It should be $(v_s-p_s)x_s \geq (v_s-p_{S+1})x_{S+1}$ instead of $(v_s-p_s)x_s \geq (v_{S+1}-p_{S+1})x_{S+1}$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.