Credible, Strategyproof, Optimal, and Bounded Expected-Round Single-Item Auctions for All Distributions

Meryem Essaidi, Matheus V.X. Ferreira, S. Matthew Weinberg

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

1 Scopus citations

Abstract

We consider a revenue-maximizing seller with a single item for sale to multiple buyers with independent and identically distributed valuations. Akbarpour and Li (2020) show that the only optimal, credible, strategyproof auction is the ascending price auction with reserves which has unbounded communication complexity. Recent work of Ferreira and Weinberg (2020) circumvents their impossibility result assuming the existence of cryptographically secure commitment schemes, and designs a two-round credible, strategyproof, optimal auction. However, their auction is only credible when buyers' valuations are MHR or α-strongly regular: they show their auction might not be credible even when there is a single buyer drawn from a non-MHR distribution. In this work, under the same cryptographic assumptions, we identify a new single-item auction that is credible, strategyproof, revenue optimal, and terminates in constant rounds in expectation for all distributions with finite monopoly price.

Original languageEnglish (US)
Title of host publication13th Innovations in Theoretical Computer Science Conference, ITCS 2022
EditorsMark Braverman
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772174
DOIs
StatePublished - Jan 1 2022
Event13th Innovations in Theoretical Computer Science Conference, ITCS 2022 - Berkeley, United States
Duration: Jan 31 2022Feb 3 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume215
ISSN (Print)1868-8969

Conference

Conference13th Innovations in Theoretical Computer Science Conference, ITCS 2022
Country/TerritoryUnited States
CityBerkeley
Period1/31/222/3/22

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Credible auctions
  • Cryptographically secure
  • Single-item

Fingerprint

Dive into the research topics of 'Credible, Strategyproof, Optimal, and Bounded Expected-Round Single-Item Auctions for All Distributions'. Together they form a unique fingerprint.

Cite this