  State-of-the-art posted-price mechanisms for submodular bidders with $m$
items achieve approximation guarantees of $O((\log \log m)^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
$m^{1/2-\varepsilon}$-approximation for any $\varepsilon > 0$ [Dobzinski and
Vondr\'ak, 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 $\alpha$-approximation
in implementation in advised strategies if there exists poly-time advice for
each player such that an $\alpha$-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((\log \log m)^3)$-approximation in implementation in advised
strategies.
