Simple auctions with simple strategies

Nikhil Devanur, Jamie Morgenstern, Vasilis Syrgkanis, S. Matthew Weinberg

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

12 Scopus citations

Abstract

We introduce single-bid auctions as a new format for combinatorial auctions. In single-bid auctions, each bidder submits a single real-valued bid for the right to buy items at a fixed price. Contrary to other simple auction formats, such as simultaneous or sequential single-item auctions, bidders can implement no-regret learning strategies for single-bid auctions in polynomial time. Price of anarchy bounds for correlated equilibria concepts in single-bid auctions therefore have more bite than their counterparts for auctions and equilibria for which learning is not known to be computationally tractable (or worse, known to be computationally intractable [Cai and Papadimitriou 2014; Dobzinski et al. 2015] this end, we show that for any subadditive valuations the social welfare at equilibrium is an O(logm)-approximation to the optimal social welfare, where m is the number of items. We also provide tighter approximation results for several subclasses. Our welfare guarantees hold for Nash equilibria and no-regret learning outcomes in both Bayesian and complete information settings via the smooth-mechanism framework. Of independent interest, our techniques show that in a combinatorial auction setting, efficiency guarantees of a mechanism via smoothness for a very restricted class of cardinality valuations extend, with a small degradation, to subadditive valuations, the largest complement-free class of valuations.

Original languageEnglish (US)
Title of host publicationEC 2015 - Proceedings of the 2015 ACM Conference on Economics and Computation
PublisherAssociation for Computing Machinery, Inc
Pages305-322
Number of pages18
ISBN (Electronic)9781450334105
DOIs
StatePublished - Jun 15 2015
Event16th ACM Conference on Economics and Computation, EC 2015 - Portland, United States
Duration: Jun 15 2015Jun 19 2015

Publication series

NameEC 2015 - Proceedings of the 2015 ACM Conference on Economics and Computation

Other

Other16th ACM Conference on Economics and Computation, EC 2015
CountryUnited States
CityPortland
Period6/15/156/19/15

All Science Journal Classification (ASJC) codes

  • Economics and Econometrics
  • Statistics and Probability
  • Computer Science (miscellaneous)
  • Computational Mathematics
  • Marketing

Keywords

  • Auction design
  • Mechanism design

Fingerprint Dive into the research topics of 'Simple auctions with simple strategies'. Together they form a unique fingerprint.

  • Cite this

    Devanur, N., Morgenstern, J., Syrgkanis, V., & Weinberg, S. M. (2015). Simple auctions with simple strategies. In EC 2015 - Proceedings of the 2015 ACM Conference on Economics and Computation (pp. 305-322). (EC 2015 - Proceedings of the 2015 ACM Conference on Economics and Computation). Association for Computing Machinery, Inc. https://doi.org/10.1145/2764468.2764484