Certifying Strategyproof Auction Networks
This work addresses the need for provably strategyproof auctions in multi-item settings, offering a solution to a long-standing problem in economics and AI, though it is incremental by building on existing differentiable economics approaches.
The paper tackles the problem of designing revenue-maximizing auctions for multiple items and participants, which remains an open challenge in mechanism design, by proposing a method to explicitly verify strategyproofness in learned auction networks, achieving certified results in settings where optimal mechanisms are unknown.
Optimal auctions maximize a seller's expected revenue subject to individual rationality and strategyproofness for the buyers. Myerson's seminal work in 1981 settled the case of auctioning a single item; however, subsequent decades of work have yielded little progress moving beyond a single item, leaving the design of revenue-maximizing auctions as a central open problem in the field of mechanism design. A recent thread of work in "differentiable economics" has used tools from modern deep learning to instead learn good mechanisms. We focus on the RegretNet architecture, which can represent auctions with arbitrary numbers of items and participants; it is trained to be empirically strategyproof, but the property is never exactly verified leaving potential loopholes for market participants to exploit. We propose ways to explicitly verify strategyproofness under a particular valuation profile using techniques from the neural network verification literature. Doing so requires making several modifications to the RegretNet architecture in order to represent it exactly in an integer program. We train our network and produce certificates in several settings, including settings for which the optimal strategyproof mechanism is not known.