Price of anarchy for auction revenue

Jason D Hartline, Darrell Hoy, Sam Taggart

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

12 Scopus citations

Abstract

This paper develops tools for welfare and revenue analyses of Bayes-Nash equilibria in asymmetric auctions with single-dimensional agents. We employ these tools to derive price of anarchy results for social welfare and revenue. Our approach separates the standard smoothness framework [e.g., Syrgkanis and Tardos 2013] into two distinct parts. The first part, value covering, employs best-response analysis to individually relate each agent's expected price for allocation and welfare in any Bayes-Nash equilibrium. The second part, revenue covering, uses properties of an auction's rules and feasibility constraints to relate the revenue of the auction to the agents' expected prices for allocation (not necessarily in equilibrium). Because value covering holds for any equilibrium, proving an auction is revenue covered is a sufficient condition for approximating optimal welfare, and under the right conditions, the optimal revenue. In mechanisms with reserve prices, our welfare results show approximation with respect to the optimal mechanism with the same reserves. As a center-piece result, we analyze the single-item first-price auction with individual monopoly reserves (the price that a monopolist would post to sell to that agent alone, these reserves are generally distinct for agents with values drawn from distinct distributions). When each distribution satisfies the regularity condition of Myerson [1981] the auction's revenue is at least a 2e/e-1 ≈ 3.16 approximation to the revenue of the optimal auction revenue. We also give bounds for matroid auctions with first price or all-pay semantics, and the generalized first price position auction. Finally, we give an extension theorem for simultaneous composition, i.e., when multiple auctions are run simultaneously, with single-valued and unit demand agents.

Original languageEnglish (US)
Title of host publicationEC 2014 - Proceedings of the 15th ACM Conference on Economics and Computation
PublisherAssociation for Computing Machinery
Pages693-710
Number of pages18
ISBN (Print)9781450325653
DOIs
StatePublished - 2014
Event15th ACM Conference on Economics and Computation, EC 2014 - Palo Alto, CA, United States
Duration: Jun 8 2014Jun 12 2014

Publication series

NameEC 2014 - Proceedings of the 15th ACM Conference on Economics and Computation

Other

Other15th ACM Conference on Economics and Computation, EC 2014
CountryUnited States
CityPalo Alto, CA
Period6/8/146/12/14

Keywords

  • approximation
  • bayesian mechanism design
  • mechanism design

ASJC Scopus subject areas

  • Computer Science (miscellaneous)

Fingerprint Dive into the research topics of 'Price of anarchy for auction revenue'. Together they form a unique fingerprint.

Cite this