Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

An improved welfare guarantee for first-price auctions

An improved welfare guarantee for first-price auctions We highlight recent progress in worst-case analysis of welfare in first price auctions. It was shown in [Syrgkanis and Tardos 2013] that in any Bayes-Nash equilibrium of a first-price auction, the expected social welfare is at least a (1 - 1/e) .63-fraction of optimal. This result uses smoothness, the standard technique for worst-case welfare analysis of games, and is tight if bidders' value distributions are permitted to be correlated. With independent distributions, however, the worst-known example, due to [Hartline et al. 2014], exhibits welfare that is a .89-fraction of optimal. This gap has persisted in spite of the canonical nature of the first-price auction and the prevalence of the independence assumption. In [Hoy et al. 2018], we improve the worst-case lower bound on first-price auction welfare assuming independently distributed values from (1 - 1/e) to .743. Notably, the proof of this result eschews smoothness in favor of techniques which exploit independence. This note overviews the new approach, and discusses research directions opened up by the result. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM SIGecom Exchanges Association for Computing Machinery

An improved welfare guarantee for first-price auctions

Hoy, Darrell; Taggart, Sam; Wang, Zihe
ACM SIGecom Exchanges , Volume 17 (1): 7 – May 7, 2019
Download PDF
7 pages

Loading next page...
 
/lp/association-for-computing-machinery/an-improved-welfare-guarantee-for-first-price-auctions-IFlOz6bi0z
Publisher
Association for Computing Machinery
Copyright
Copyright © 2019 Authors
ISSN
1551-9031
eISSN
1551-9031
DOI
10.1145/3331033.3331040
Publisher site
See Article on Publisher Site

Abstract

We highlight recent progress in worst-case analysis of welfare in first price auctions. It was shown in [Syrgkanis and Tardos 2013] that in any Bayes-Nash equilibrium of a first-price auction, the expected social welfare is at least a (1 - 1/e) .63-fraction of optimal. This result uses smoothness, the standard technique for worst-case welfare analysis of games, and is tight if bidders' value distributions are permitted to be correlated. With independent distributions, however, the worst-known example, due to [Hartline et al. 2014], exhibits welfare that is a .89-fraction of optimal. This gap has persisted in spite of the canonical nature of the first-price auction and the prevalence of the independence assumption. In [Hoy et al. 2018], we improve the worst-case lower bound on first-price auction welfare assuming independently distributed values from (1 - 1/e) to .743. Notably, the proof of this result eschews smoothness in favor of techniques which exploit independence. This note overviews the new approach, and discusses research directions opened up by the result.

Journal

ACM SIGecom Exchanges – Association for Computing Machinery

Published: May 7, 2019

References

  • Tight bounds for the price of anarchy of simultaneous first-price auctions
    Christodoulou, ; G., ; Kovács, ; A., ; Sgouritsa, ; A., ; Tang, ; B.,
  • On the efficiency of all-pay mechanisms
    Christodoulou, ; G., ; Sgouritsa, ; A., ; Tang, ; B.,
  • Price of anarchy for auction revenue
    Hartline, ; J., ; Hoy, ; D., ; Taggart, ; S.,
  • No-regret learning in bayesian games
    Hartline, ; J., ; Syrgkanis, ; V., ; Tardos, ; E.,
  • A tighter welfare guarantee for first-price auctions
    Hoy, ; D., ; Taggart, ; S., ; Wang, ; Z.,
  • Asymmetric first price auctions
    Kirkegaard, ; R.,
  • The price of anarchy in auctions
    Roughgarden, ; T., ; Syrgkanis, ; V., ; Tardos, ; E.,
  • Efficiency of mechanisms in complex markets
    Syrgkanis, ; V.,
  • Composable and efficient mechanisms
    Syrgkanis, ; V., ; Tardos, ; E.,
  • Counterspeculation, auctions, and competitive sealed tenders
    Vickrey, ; W.,