Economic Theory
August 2020
State-of-the-art posted-price mechanisms for submodular bidders with m items achieve approximation guarantees of O((loglogm)3) [Assadi and 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 m1/2−ε-approximation for any ε>0 [Dobzinski and 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, and that has been previously studied in relation to “Implementation in Undominated Strategies” [Babaioff et al, 2009]. 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 poly-time advice 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 [Assadi and Singla, 2019] mechanism achieves the same O((loglogm)3)-approximation in implementation in advised strategies.