615. Revenue Efficiency of First Price Auctions over Approximate Correlated Equilibrium
Invited abstract in session MB-10: Optimization, Learning, and Games I, stream Optimization, Learning, and Games.
Monday, 10:30-12:30Room: B100/8011
Authors (first author is the speaker)
| 1. | Efstratios Skoulakis
|
| Aarhus University |
Abstract
In this work 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.
Keywords
- Computational game theory
Status: accepted
Back to the list of papers