Certifying Strategyproof Auction Networks
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Strategyproofness and Monotone Allocation of Auction in Social Networks
Strategyproofness in network auctions requires that bidders not only report their valuations truthfully, but also do their best to invite neighbours from the social network. In contrast to canonical auctions, where the v…
Differentiable Economics for Randomized Affine Maximizer Auctions
A recent approach to automated mechanism design, differentiable economics, represents auctions by rich function approximators and optimizes their performance by gradient descent. The ideal auction architecture for differ…
"Auction Learning as a Two Player Game": GANs (?) for Mechanism Design
Designing strategyproof, revenue-maximizing auctions is an important task, but it is surprisingly difficult -- even in some seemingly trivial cases, nothing is known about the optimal auction design. Motivated by this la…
Deep LearningVocal Bursts Valence PredictionNeural Auctions Compromise Bidder Information
Single-shot auctions are commonly used as a means to sell goods, for example when selling ad space or allocating radio frequencies, however devising mechanisms for auctions with multiple bidders and multiple items can be…
PreferenceNet: Encoding Human Preferences in Auction Design with Deep Learning
The design of optimal auctions is a problem of interest in economics, game theory and computer science. Despite decades of effort, strategyproof, revenue-maximizing auction designs are still not known outside of restrict…
Deep LearningDiversityFairness