Computing simple mechanisms: Lift-and-round over marginal reduced forms

DOI10.1145/3519935.3520029MaRDI QIDQ6083525zbMATH OpenOpenAlexFDO

Authors Yang Cai, Mingfei Zhao

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2111.03962

zbMATH Keywords

computational complexitylinear program liftingrevenue maximizationsimple and approximately optimal auctionsXOS valuations

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We study revenue maximization in multi-item multi-bidder auctions under the natural item-independence assumption - a classical problem in Multi-Dimensional Bayesian Mechanism Design. One of the biggest challenges in this area is developing algorithms to compute (approximately) optimal mechanisms that are not brute-force in the size of the bidder type space, which is usually exponential in the number of items in multi-item auctions. Unfortunately, such algorithms were only known for basic settings of our problem when bidders have unit-demand [CHMS10,CMS15] or additive valuations [Yao15]. In this paper, we significantly improve the previous results and design the first algorithm that runs in time polynomial in the number of items and the number of bidders to compute mechanisms that are $O(1)$-approximations to the optimal revenue when bidders have XOS valuations, resolving an open problem raised in [CM16,CZ17]. Moreover, the computed mechanism has a simple structure: It is either a posted price mechanism or a two-part tariff mechanism. As a corollary of our result, we show how to compute an approximately optimal and simple mechanism efficiently using only sample access to the bidders' value distributions. Our algorithm builds on two innovations that allow us to search over the space of mechanisms efficiently: (i) a new type of succinct representation of mechanisms - the marginal reduced forms, and (ii) a novel Lift-and-Round procedure that concavifies the problem.

Recommendations

• On the computational complexity of optimal simple mechanisms
• Multidimensional mechanism design: finite-dimensional approximations and efficient computation
• Computing Simply Stable Equilibria
• A note on the tight simplification of mechanisms
• Efficient computation of optimal auctions via reduced forms
• Computing equilibria: a computational complexity perspective
• Approximation techniques for utilitarian mechanism design
• Approximation techniques for utilitarian mechanism design
• Computational techniques for a simple theory of conditional preferences
• Reducing mechanism design to algorithm design via machine learning

Cited in

(4)

• A Duality-Based Unified Approach to Bayesian Mechanism Design
• A note on the tight simplification of mechanisms
• Multi-agent contracts
• An algorithmic framework for black-box reductions from Bayesian mechanism design to algorithm design

This page was built for publication: Computing simple mechanisms: Lift-and-round over marginal reduced forms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083525)