Learning Utilities and Equilibria in Non-Truthful Auctions (Hu Fu)


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.


2021-06-19  09:00-09:30   


Hu Fu, Shanghai University of Finance and Economics


Guangdong Hotel Shanghai