Skip to main content

A Duality-Based Unified Approach to Bayesian Mechanism Design

Author(s): Cai, Yang; Devanur, Nikhil R; Weinberg, S Matthew

To refer to this page use:
Abstract: We provide a unified view of many recent developments in Bayesian mechanism design, including the black-box reductions of Cai, Daskalakis, and Weinberg [in Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013], simple auctions for additive buyers [S. Hart and N. Nisan, in Proceedings of the 13th ACM Conference on Electronic Commerce, 2012], and posted-price mechanisms for unit-demand buyers [S. Chawla, J. D. Hartline, and R. D. Kleinberg, in Proceedings of the 8th ACM Conference on Electronic Commerce, 2007, pp. 243--251]. Additionally, we show that viewing these three previously disjoint lines of work through the same lens leads to new developments as well. First, we provide a duality framework for Bayesian mechanism design, which naturally accommodates multiple agents and arbitrary objectives/feasibility constraints. Using this, we prove that either a posted-price mechanism or the Vickrey--Clarke--Groves auction with per-bidder entry fees achieves a constant factor of the optimal revenue achievable by a Bayesian Incentive Compatible mechanism whenever buyers are unit-demand or additive, unifying previous breakthroughs of Chawla et al. [in Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010] and Yao [in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015, pp. 92--109], and improving both approximation ratios (from 30 to 24 and 69 to 8, respectively). Finally, we show that this view also leads to improved structural characterizations in the framework of Cai, Daskalakis, and Weinberg.
Publication Date: 2021
Citation: Cai, Yang, Nikhil R. Devanur, and S. Matthew Weinberg. "A duality-based unified approach to bayesian mechanism design." SIAM Journal on Computing 50, no. 3 (2021): STOC16-160-STOC16-200.
DOI: 10.1137/16M1100113
ISSN: 0097-5397
EISSN: 1095-7111
Pages: STOC16 - 160-STOC16-200
Type of Material: Journal Article
Journal/Proceeding Title: SIAM Journal on Computing
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.