  Truthfulness is fragile and demanding. It is oftentimes computationally
harder than solving the original problem. Even worse, truthfulness can be
utterly destroyed by small uncertainties in a mechanism's outcome. One obstacle
is that truthful payments depend on outcomes other than the one realized, such
as the lengths of non-shortest-paths in a shortest-path auction. Single-call
mechanisms are a powerful tool that circumvents this obstacle --- they
implicitly charge truthful payments, guaranteeing truthfulness in expectation
using only the outcome realized by the mechanism. The cost of such truthfulness
is a trade-off between the expected quality of the outcome and the risk of
large payments.
  We largely settle when and to what extent single-call mechanisms are
possible. The first single-call construction was discovered by Babaioff,
Kleinberg, and Slivkins [BKS10] in single-parameter domains. They give a
transformation that turns any monotone, single-parameter allocation rule into a
truthful-in-expectation single-call mechanism. Our first result is a natural
complement to [BKS10]: we give a new transformation that produces a single-call
VCG mechanism from any allocation rule for which VCG payments are truthful.
Second, in both the single-parameter and VCG settings, we precisely
characterize the possible transformations, showing that that a wide variety of
transformations are possible but that all take a very simple form. Finally, we
study the inherent trade-off between the expected quality of the outcome and
the risk of large payments. We show that our construction and that of [BKS10]
simultaneously optimize a variety of metrics in their respective domains.
  As an example, we analyze pay-per-click advertising auctions, where the
truthfulness of the standard VCG-based auction is easily broken when the
auctioneer's estimated click-through-rates are imprecise.
