Implementation in advised strategies: Welfare guarantees from posted-price mechanisms when demand queries are NP-hard

Linda Cai, Clay Thomas, S. Matthew Weinberg

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

1 Scopus citations

Abstract

State-of-the-art posted-price mechanisms for submodular bidders with m items achieve approximation guarantees of O((log log m)3) [1]. Their truthfulness, however, requires bidders to compute an NP-hard demand-query. Some computational complexity of this form is unavoidable, as it is NP-hard for truthful mechanisms to guarantee even an m1/2−ε-approximation for any ε > 0 [21]. Together, these establish a stark distinction between computationally-efficient and communication-efficient truthful mechanisms. We show that this distinction disappears with a mild relaxation of truthfulness, which we term implementation in advised strategies. Specifically, advice maps a tentative strategy either to that same strategy itself, or one that dominates it. We say that a player follows advice as long as they never play actions which are dominated by advice. A poly-time mechanism guarantees an α-approximation in implementation in advised strategies if there exists advice (which runs in poly-time) for each player such that an α-approximation is achieved whenever all players follow advice. Using an appropriate bicriterion notion of approximate demand queries (which can be computed in poly-time), we establish that (a slight modification of) the [1] mechanism achieves the same O((log log m)3)-approximation in implementation in advised strategies.

Original languageEnglish (US)
Title of host publication11th Innovations in Theoretical Computer Science Conference, ITCS 2020
EditorsThomas Vidick
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771344
DOIs
StatePublished - Jan 2020
Event11th Innovations in Theoretical Computer Science Conference, ITCS 2020 - Seattle, United States
Duration: Jan 12 2020Jan 14 2020

Publication series

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

Conference

Conference11th Innovations in Theoretical Computer Science Conference, ITCS 2020
CountryUnited States
CitySeattle
Period1/12/201/14/20

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Combinatorial auctions
  • Incentive compatible
  • Posted-price mechanisms
  • Submodular valuations

Fingerprint Dive into the research topics of 'Implementation in advised strategies: Welfare guarantees from posted-price mechanisms when demand queries are NP-hard'. Together they form a unique fingerprint.

Cite this