License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2020.61
URN: urn:nbn:de:0030-drops-117464
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11746/
Go to the corresponding LIPIcs Volume Portal


Cai, Linda ; Thomas, Clay ; Weinberg, S. Matthew

Implementation in Advised Strategies: Welfare Guarantees from Posted-Price Mechanisms When Demand Queries Are NP-Hard

pdf-format:
LIPIcs-ITCS-2020-61.pdf (0.7 MB)


Abstract

State-of-the-art posted-price mechanisms for submodular bidders with m items achieve approximation guarantees of O((log log m)^3) [Sepehr Assadi and Sahil Singla, 2019]. 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 m^(1/2-ε)-approximation for any ε > 0 [Shahar Dobzinski and Jan Vondrák, 2016]. 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 [Sepehr Assadi and Sahil Singla, 2019] mechanism achieves the same O((log log m)^3)-approximation in implementation in advised strategies.

BibTeX - Entry

@InProceedings{cai_et_al:LIPIcs:2020:11746,
  author =	{Linda Cai and Clay Thomas and S. Matthew Weinberg},
  title =	{{Implementation in Advised Strategies: Welfare Guarantees from Posted-Price Mechanisms When Demand Queries Are NP-Hard}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{61:1--61:32},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Thomas Vidick},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11746},
  URN =		{urn:nbn:de:0030-drops-117464},
  doi =		{10.4230/LIPIcs.ITCS.2020.61},
  annote =	{Keywords: Combinatorial auctions, Posted-Price mechanisms, Submodular valuations, Incentive compatible}
}

Keywords: Combinatorial auctions, Posted-Price mechanisms, Submodular valuations, Incentive compatible
Collection: 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Issue Date: 2020
Date of publication: 06.01.2020


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI