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/
Cai, Linda ;
Thomas, Clay ;
Weinberg, S. Matthew
Implementation in Advised Strategies: Welfare Guarantees from Posted-Price Mechanisms When Demand Queries Are NP-Hard
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 |
