Optimal multi-dimensional mechanism design: Reducing revenue to welfare maximization

Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg

Research output: Contribution to journalConference article

86 Scopus citations

Abstract

We provide a reduction from revenue maximization to welfare maximization in multi-dimensional Bayesian auctions with arbitrary (possibly combinatorial) feasibility constraints and independent bidders with arbitrary (possibly combinatorial) demand constraints, appropriately extending Myerson's single-dimensional result [Myerson81] to this setting. We also show that every feasible Bayesian auction (including in particular the revenue-optimal one) can be implemented as a distribution over virtual VCG allocation rules. A virtual VCG allocation rule has the following simple form: Every bidder's type t i is transformed into a virtual type fi(ti), via a bidder-specific function. Then, the allocation maximizing virtual welfare is chosen. Using this characterization, we show how to find and run the revenue-optimal auction given only black-box access to an implementation of the VCG allocation rule. We generalize this result to arbitrarily correlated bidders, introducing the notion of a second-order VCG allocation rule. Our results are computationally efficient for all multi-dimensional settings where the bidders are additive, or can be efficiently mapped to be additive, albeit the feasibility and demand constraints may still remain arbitrary combinatorial. In this case, our mechanisms run in time polynomial in the number of items and the total number of bidder types, but not type profiles. This is polynomial in the number of items, the number of bidders, and the cardinality of the support of each bidder's value distribution. For generic correlated distributions, this is the natural description complexity of the problem. The runtime can be further improved to polynomial in only the number of items and the number of bidders in item-symmetric settings by making use of techniques from [15].

Original languageEnglish (US)
Article number6375290
Pages (from-to)130-139
Number of pages10
JournalProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
DOIs
StatePublished - Dec 1 2012
Externally publishedYes
Event53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012 - New Brunswick, NJ, United States
Duration: Oct 20 2012Oct 23 2012

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Auctions
  • Convex Optimization
  • Game Theory
  • Mechanism Design
  • Multi-Dimensional
  • Revenue

Fingerprint Dive into the research topics of 'Optimal multi-dimensional mechanism design: Reducing revenue to welfare maximization'. Together they form a unique fingerprint.

  • Cite this