GSP Auctions prove dominant strategy

Question

I need to show that considering a GSP auction for $n$ players, any bid $b_{i} > v_{i}$ is dominated by bid $b_{i} = v_{i}$. Where $i$ is the player, $b_{i}$ is the bid for player $i$ and $v_{i}$ the value player $i$ estimates the bid.

I don't really see how to prove it.

Thanks

Answer 1

Call a bid "winning" if it wins a slot, else call it "losing".

Suppose you're the $i$'th bidder.

For simplicity, assume you win on a tie.

Of the other bids, let $\bar{b}$ be the highest which is less than or equal to $b_i$.

Consider two cases . . .

Case $(1):\;\bar{b} > v_i$.

If $b_i > v_i$, then if you lose the bid, the net return is $0$, but if you win the bid, the net return is $v_i-\bar{b}$, which is negative.

If $b_i = v_i$, case $(1)$ can't happen, else $\bar{b} > b_i$, contradiction.

Case $(2):\;\bar{b} \le v_i$.

If your bid wins, your net return is $v_i - \bar{b}$, and if your bid loses, your net return is $0$.

But a bid $b_i > v_i$ is winning if and only the bid $b_i = v_i$ is winning (since there are no bids strictly between $b_i$ and $\bar{b}$).

Hence, regardless of whether $b_i > v_i$ or $b_i = v_i$, the results (win or lose) are the same, and the net returns are the same.

To recap:

• Choosing $b_i = v_i$ completely avoids case $(1)$, whereas for case $(1)$, if you choose $b_i > v_i$, there is a potential for a negative net return, and no potential for a positive net return.$\\[4pt]$
• For case $(2)$, choosing $b_i = v_i$ yields the same results as choosing $b_i > v_i$.

It follows that the strategy $b_i = v_i$ dominates any strategy for which $b_i > v_i$.