Lecture: Rational Proofs

Silvio Micali

Abstract:

We unify the treatment of asymmetry of information in theoretical computer science and economics.
We put forward a new type of proof system, where an unbounded Prover and a bounded Verifier interact, on inputs a string x and a function f, so that the Verifier may learn f(x). In our setting Provers are not “honest” or “malicious”, but RATIONAL, that is, trying to maximize their utility. In essence, (1) the Verifier gives the Prover a reward in [0,1] determined by the transcript of their interaction; (2) the Prover wishes to maximize his expected reward; and (3) the reward is maximized only if the verifier correctly learns f(x).
Rational proofs are as powerful as interactive ones, but can be amazingly more efficient in the amount of communication involved: that is, the number of bits exchanged and the number of rounds of interaction.
Joint work with Pablo Azar.

Silvio Micali

more