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 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.|
|Citation:||Cai, Yang, Nikhil R. Devanur, and S. Matthew Weinberg. "A duality based unified approach to Bayesian mechanism design." In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (2016): pp. 926-939. doi:10.1145/2897518.2897645|
|Pages:||926 - 939|
|Type of Material:||Conference Article|
|Journal/Proceeding Title:||Proceedings of the forty-eighth annual ACM symposium on Theory of Computing|
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.