Multi-parameter mechanism design and sequential posted pricing

Shuchi Chawla*, Jason D Hartline, David L. Malec, Balasubramanian Sivan

*Corresponding author for this work

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

222 Scopus citations

Abstract

We study the classic mathematical economics problem of Bayesian optimal mechanism design where a principal aims to optimize expected revenue when allocating resources to self-interested agents with preferences drawn from a known distribution. In single parameter settings (i.e., where each agent's preference is given by a single private value for being served and zero for not being served) this problem is solved [20]. Unfortunately, these single parameter optimal mechanisms are impractical and rarely employed [1], and furthermore the underlying economic theory fails to generalize to the important, relevant, and unsolved multi-dimensional setting (i.e., where each agent's preference is given by multiple values for each of the multiple services available) [25]. In contrast to the theory of optimal mechanisms we develop a theory of sequential posted price mechanisms, where agents in sequence are offered take-it-or-leave-it prices. We prove that these mechanisms are approximately optimal in single-dimensional settings. These posted-price mechanisms avoid many of the properties of optimal mechanisms that make the latter impractical. Furthermore, these mechanisms generalize naturally to multi-dimensional settings where they give the first known approximations to the elusive optimal multi-dimensional mechanism design problem. In particular, we solve multi-dimensional multi-unit auction problems and generalizations to matroid feasibility constraints. The constant approximations we obtain range from 1.5 to 8. For all but one case, our posted price sequences can be computed in polynomial time. This work can be viewed as an extension and improvement of the single-agent algorithmic pricing work of [9] to the setting of multiple agents where the designer has combinatorial feasibility constraints on which agents can simultaneously obtain each service.

Original languageEnglish (US)
Title of host publicationSTOC'10 - Proceedings of the 2010 ACM International Symposium on Theory of Computing
Pages311-320
Number of pages10
DOIs
StatePublished - Jul 23 2010
Event42nd ACM Symposium on Theory of Computing, STOC 2010 - Cambridge, MA, United States
Duration: Jun 5 2010Jun 8 2010

Publication series

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

Other

Other42nd ACM Symposium on Theory of Computing, STOC 2010
CountryUnited States
CityCambridge, MA
Period6/5/106/8/10

Keywords

  • Bayesian mechanism design

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Multi-parameter mechanism design and sequential posted pricing'. Together they form a unique fingerprint.

  • Cite this

    Chawla, S., Hartline, J. D., Malec, D. L., & Sivan, B. (2010). Multi-parameter mechanism design and sequential posted pricing. In STOC'10 - Proceedings of the 2010 ACM International Symposium on Theory of Computing (pp. 311-320). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/1806689.1806733