Learning Utilities and Equilibria in Non-Truthful Auctions (Hu Fu)
Abstract
In non-truthful auctions, agents' utility for a strategy depends on the strategies of the opponents and also the prior distribution over their private types; the set of Bayes Nash equilibria generally has an intricate dependence on the prior. Using the First Price Auction as our main demonstrating example, we show that \tilde O(n / \eps^2) samples from the prior with n agents suffice for an algorithm to learn the interim utilities for all monotone bidding strategies, up to \eps additive error. As a consequence, this number of samples suffice for learning all approximate equilibria. We give almost matching (up to polylog factors) lower bound on the sample complexity for learning utilities.
Time
2021-06-19 09:00-09:30
Speaker
Hu Fu, Shanghai University of Finance and Economics
Room
Guangdong Hotel Shanghai
