Revenue Guarantees of No-Swap-Regret Dynamics in First Price Auctions

We study the revenue of approximate correlated equilibrium in discrete first price auctions - the set of allowable bids is $\mathcal{B} = \{0, 1/k, \dots, 1 - 1/k, 1\}$ for some $k \in \mathbb{N}$. We show that the revenue of any $\epsilon$-\textit{approximate} correlated equilibrium is at least $v_2 - \Theta(1/k)- \Theta(\epsilon k^2)$, where $v_2 \geq 0$ is the second-highest valuation. Our results establish the first polynomial convergence rates on the revenue generated by no-swap regret bidders in first-price auctions. For instance, if bidders admit the optimal swap regret of $\mathcal{O}(\sqrt{k T})$, then the time-averaged revenue is at least $v_2 - \Theta(1/k) - \Theta(\epsilon)$ after $\mathcal{O}(k^5/\epsilon^2)$ rounds.

Online advertising is a multi-billion dollar industry that has recently changed the auction format used to sell advertisement slots. Because these auctions are repeated frequently, bidders can learn from past outcomes to refine their strategies. While existing research guarantees that auctioneer revenue under the new format eventually reaches the guarantees of the old format, the number of repetitions required to achieve these results is impractically large. We apply a novel technique to provide revenue guarantees while drastically reducing the number of repetitions required for the auction to become efficient. This work enhances our understanding of the digital advertising landscape and provides greater transparency for both bidders and auctioneers.