  We consider a setting where a verifier with limited computation power
delegates a resource intensive computation task---which requires a $T\times S$
computation tableau---to two provers where the provers are rational in that
each prover maximizes their own payoff---taking into account losses incurred by
the cost of computation. We design a mechanism called the Minimal Refereed
Mechanism (MRM) such that if the verifier has $O(\log S + \log T)$ time and
$O(\log S + \log T)$ space computation power, then both provers will provide a
honest result without the verifier putting any effort to verify the results.
The amount of computation required for the provers (and thus the cost) is a
multiplicative $\log S$-factor more than the computation itself, making this
schema efficient especially for low-space computations.

Computer Science and Game Theory;Cryptography and Security