  We propose a generic mechanism for incentivizing behavior in an arbitrary
finite game using payments. Doing so is trivial if the mechanism is allowed to
observe all actions taken in the game, as this allows it to simply punish those
agents who deviate from the intended strategy. Instead, we consider an
abstraction where the mechanism probabilistically infers information about what
happened in the game. We show that payment schemes can be used to implement any
set of utilities if and only if the mechanism can essentially infer completely
what happened. We show that finding an optimal payment scheme for games of
perfect information is \textsf{P}-complete, and conjecture it to be
\textsf{PPAD}-hard for games of imperfect information. We prove a lower bound
on the size of the payments, showing that the payments must be linear in the
intended level of security. We demonstrate the applicability of our model to
concrete problems in distributed computing, namely decentralized commerce and
secure multiparty computation, for which the payments match the lower bound
asymptotically.
