Statistically Truthful Auctions via Acceptance Rule

Auctions are key for maximizing sellers' revenue and ensuring truthful bidding among buyers. Recently, an approach known as differentiable economics based on machine learning (ML) has shown promise in learning powerful auction mechanisms for multiple items and participants. However, this approach has no guarantee of strategy-proofness at test time. Strategy-proofness is crucial as it ensures that buyers are incentivized to bid their true valuations, leading to optimal and fair auction outcomes without the risk of manipulation. In this work, we propose a formulation of statistical strategy-proofness for auction mechanisms. Specifically, we offer a method that bounds the regret -- quantifying deviation from truthful bidding -- below a pre-specified level with high probability. Building upon conformal prediction techniques, we develop an auction acceptance rule that leverages regret predictions to guarantee that the data-driven auction mechanism meets the statistical strategy-proofness requirement with high probability. Our method -- Statistically Truthful Auctions via Acceptance Rule (STAR) -- represents a practical middle-ground between two extremes: enforcing truthfulness -- zero-regret -- at the cost of significant revenue loss, and naively using ML to construct auctions with the hope of attaining low regret, with no test-time guarantees.