  It is widely believed that computing payments needed to induce truthful
bidding is somehow harder than simply computing the allocation. We show that
the opposite is true: creating a randomized truthful mechanism is essentially
as easy as a single call to a monotone allocation rule. Our main result is a
general procedure to take a monotone allocation rule for a single-parameter
domain and transform it (via a black-box reduction) into a randomized mechanism
that is truthful in expectation and individually rational for every
realization. The mechanism implements the same outcome as the original
allocation rule with probability arbitrarily close to 1, and requires
evaluating that allocation rule only once. We also provide an extension of this
result to multi-parameter domains and cycle-monotone allocation rules, under
mild star-convexity and non-negativity hypotheses on the type space and
allocation rule, respectively.
  Because our reduction is simple, versatile, and general, it has many
applications to mechanism design problems in which re-evaluating the allocation
rule is either burdensome or informationally impossible. Applying our result to
the multi-armed bandit problem, we obtain truthful randomized mechanisms whose
regret matches the information-theoretic lower bound up to logarithmic factors,
even though prior work showed this is impossible for truthful deterministic
mechanisms. We also present applications to offline mechanism design, showing
that randomization can circumvent a communication complexity lower bound for
deterministic payments computation, and that it can also be used to create
truthful shortest path auctions that approximate the welfare of the VCG
allocation arbitrarily well, while having the same running time complexity as
Dijkstra's algorithm.
