2026-07-22T05:41:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11746 2024-03-06T10:48:36Z ddc:004 open_access

Implementation in Advised Strategies: Welfare Guarantees from Posted-Price Mechanisms When Demand Queries Are NP-Hard Cai, Linda Thomas, Clay Weinberg, S. Matthew Combinatorial auctions Posted-Price mechanisms Submodular valuations Incentive compatible 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Linda Cai and Clay Thomas and S. Matthew Weinberg 2020 Is Part Of LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2020.61 urn:nbn:de:0030-drops-117464 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.61 eng https://creativecommons.org/licenses/by/3.0/legalcode