TY - GEN
T1 - A duality based unified approach to Bayesian mechanism design
AU - Cai, Yang
AU - Devanur, Nikhil R.
AU - Weinberg, S. Matthew
N1 - Copyright:
Copyright 2016 Elsevier B.V., All rights reserved.
PY - 2016/6/19
Y1 - 2016/6/19
N2 - 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.
AB - 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.
KW - Revenue
KW - Simple and approximately optimal auctions
UR - http://www.scopus.com/inward/record.url?scp=84979238769&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84979238769&partnerID=8YFLogxK
U2 - 10.1145/2897518.2897645
DO - 10.1145/2897518.2897645
M3 - Conference contribution
AN - SCOPUS:84979238769
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 926
EP - 939
BT - STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing
A2 - Mansour, Yishay
A2 - Wichs, Daniel
PB - Association for Computing Machinery
T2 - 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016
Y2 - 19 June 2016 through 21 June 2016
ER -