Skip to main content

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

Author(s): Cai, Linda; Thomas, Clay; Weinberg, S Matthew

To refer to this page use:
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.
Publication Date: 2020
Citation: Cai, Linda, Clay Thomas, and S. Matthew Weinberg. "Implementation in Advised Strategies: Welfare Guarantees from Posted-Price Mechanisms When Demand Queries Are NP-Hard." In 11th Innovations in Theoretical Computer Science Conference (ITCS) (2020): 61:1-61:32. doi:10.4230/LIPIcs.ITCS.2020.61
DOI: 10.4230/LIPIcs.ITCS.2020.61
ISSN: 1868-8969
Pages: 61:1 - 61:32
Type of Material: Conference Article
Journal/Proceeding Title: 11th Innovations in Theoretical Computer Science Conference
Version: Final published version. This is an open access article.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.