A duality based unified approach to Bayesian mechanism design

Yang Cai, Nikhil R. Devanur, S. Matthew Weinberg

Research output: Chapter in Book/Report/Conference proceedingConference contribution

72 Scopus citations


We provide a unified view of many recent developments in Bayesian mechanism design, including the black-box reductions of Cai et. al., simple auctions for additive buyers, and posted-price mechanisms for unit-demand buyers. 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 VCG auction with per-bidder entry fees achieves a constant-factor of the optimal Bayesian IC revenue whenever buyers are unit-demand or additive, unifying previous breakthroughs of Chawla et. al. and Yao, and improving both approximation ratios (from 33.75 to 24 and 69 to 8). Finally, we show that this view also leads to improved structural characterizations in the Cai et. al.framework.

Original languageEnglish (US)
Title of host publicationSTOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing
EditorsYishay Mansour, Daniel Wichs
PublisherAssociation for Computing Machinery
Number of pages14
ISBN (Electronic)9781450341325
StatePublished - Jun 19 2016
Event48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016 - Cambridge, United States
Duration: Jun 19 2016Jun 21 2016

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017


Other48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Software


  • Revenue
  • Simple and approximately optimal auctions


Dive into the research topics of 'A duality based unified approach to Bayesian mechanism design'. Together they form a unique fingerprint.

Cite this