Learning Utilities and Equilibria in Non-Truthful Auctions. (arXiv:2007.01722v3 [cs.GT] UPDATED)

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 / \epsilon^2)$ samples from the prior with $n$ agents
suffice for an algorithm to learn the interim utilities for all monotone
bidding strategies. As a consequence, this …

arxiv equilibria utilities