Revenue Guarantees of No-Swap-Regret Dynamics in First Price Auctions
It provides the first polynomial convergence guarantees on revenue from no-swap regret dynamics in first-price auctions, addressing a gap in understanding the revenue properties of learning dynamics in auction theory.
The paper proves that in discrete first-price auctions, the revenue from any ε-approximate correlated equilibrium is at least the second-highest valuation minus small error terms, establishing polynomial convergence rates for no-swap regret bidders.
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 $ε$-approximate correlated equilibrium is at least $v_2 - Θ(1/k)- Θ(ε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 - Θ(1/k) - Θ(ε)$ after $\mathcal{O}(k^5/ε^2)$ rounds.