An algorithmic characterization of multi-dimensional mechanisms

Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg

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

75 Scopus citations

Abstract

We show that every feasible, Bayesian, multi-item multi-bidder mechanism for independent, additive bidders can be implemented as a mechanism that: (a) allocates every item independently of the other items; (b) for the allocation of each item it uses a strict ordering of all bidders' types; and allocates the item using a distribution over hierarchical mechanisms that iron this ordering into a non-strict ordering, and give the item uniformly at random to the bidders whose reported types dominate all other reported types according to the non-strict ordering. Combined with cyclic-monotonicity our results provide a characterization of feasible, Bayesian Incentive Compatible mechanisms in this setting. Our characterization is enabled by a new, constructive proof of Border's theorem [Border 1991], and a new generalization of this theorem to independent (but not necessarily identically distributed) bidders, improving upon the results of [Border 2007, Che-Kim-Mierendorf 2011]. For a single item and independent bidders, we show that every feasible reduced form auction can be implemented as a distribution over hierarchical mechanisms that are consistent with the same strict ordering of all bidders' types, which every mechanism in the support of the distribution irons to a non-strict ordering. We also give a polynomial-time algorithm for determining feasibility of a reduced form auction, or providing a separation hyperplane from the set of feasible reduced forms. To complete the picture, we provide polynomial-time algorithms to find and exactly sample from a distribution over hierarchical mechanisms consistent with a given feasible reduced form. All these results generalize to multi-item reduced form auctions for independent, additive bidders. Finally, for multiple items, additive bidders with hard demand constraints, and arbitrary value correlation across items or bidders, we give a proper generalization of Border's Theorem, and characterize feasible reduced form auctions as multi-commodity flows in related multi-commodity flow instances. We also show that our generalization holds for a broader class of feasibility constraints, including the intersection of any two matroids. As a corollary of our results we compute revenue-optimal, Bayesian Incentive Compatible (BIC) mechanisms in multi-item multi-bidder settings, when each bidder has arbitrarily correlated values over the items and additive valuations over bundles of items, and the bidders are independent. Our mechanisms run in time polynomial in the total number of bidder types (and not type profiles). This running time is polynomial in the number of bidders, but potentially exponential in the number of items. We improve the running time to polynomial in both the number of items and the number of bidders by using recent structural results on optimal BIC auctions in item-symmetric settings [DW11].

Original languageEnglish (US)
Title of host publicationSTOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing
Pages459-478
Number of pages20
DOIs
StatePublished - Jun 26 2012
Externally publishedYes
Event44th Annual ACM Symposium on Theory of Computing, STOC '12 - New York, NY, United States
Duration: May 19 2012May 22 2012

Publication series

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

Other

Other44th Annual ACM Symposium on Theory of Computing, STOC '12
CountryUnited States
CityNew York, NY
Period5/19/125/22/12

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Border's theorem
  • multidimensional mechanisms
  • optimal mechanism design

Fingerprint Dive into the research topics of 'An algorithmic characterization of multi-dimensional mechanisms'. Together they form a unique fingerprint.

  • Cite this

    Cai, Y., Daskalakis, C., & Weinberg, S. M. (2012). An algorithmic characterization of multi-dimensional mechanisms. In STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing (pp. 459-478). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/2213977.2214021