A Game-Theoretic Analysis of the Empirical Revenue Maximization Algorithm with Endogenous Sampling
This addresses a key issue in auction design for revenue-maximizing auctioneers by making ERM more robust against strategic manipulation, though it builds incrementally on prior work.
The paper tackles the problem of agents manipulating inputs to the Empirical Revenue Maximization (ERM) algorithm in auctions, which can lower output prices, by generalizing an incentive-awareness measure to quantify this effect and providing convergence rates as sample size increases. It results in an efficient, approximately incentive-compatible, and revenue-optimal learning algorithm for repeated auctions and shows approximate group incentive-compatibility in uniform-price auctions.
The Empirical Revenue Maximization (ERM) is one of the most important price learning algorithms in auction design: as the literature shows it can learn approximately optimal reserve prices for revenue-maximizing auctioneers in both repeated auctions and uniform-price auctions. However, in these applications the agents who provide inputs to ERM have incentives to manipulate the inputs to lower the outputted price. We generalize the definition of an incentive-awareness measure proposed by Lavi et al (2019), to quantify the reduction of ERM's outputted price due to a change of $m\ge 1$ out of $N$ input samples, and provide specific convergence rates of this measure to zero as $N$ goes to infinity for different types of input distributions. By adopting this measure, we construct an efficient, approximately incentive-compatible, and revenue-optimal learning algorithm using ERM in repeated auctions against non-myopic bidders, and show approximate group incentive-compatibility in uniform-price auctions.