Games for Exchanging Information

Gillat Kol       Moni Naor

Abstract:

We deal with protocols that encourage participants to exchange information about their inputs for their mutual benefit. Our assumption is that the participants are rational and try to maximize their utility. Our goal is to design games and strategies where rational players do not have any incentive to deviate from the strategy.

We investigate the problem of rational secret sharing, where a dealer pre-distributed shares of a secret which can in turn be reconstructed by the participants at a later stage. In addition, we consider the more general problem of rational function evaluation, where the participants wish to evaluate a given function of their values. We call the above problems 'information exchanging'.

These tasks are two of the classical problems in foundations of cryptography, and have been intensively studied over the last three decades. However, their rational versions introduce new obstacles. One such obstacle is the behavior in the last round: if a participant knows that the current round is the last one, what is his incentive to send useful information?

We show that schemes for the above tasks where player values come from a bounded (finite) domain cannot satisfy some of the most desirable properties of such protocols. For instance, for two parties no non-trivial exchange can have a Nash-equilibrium. In contrast, we suggest protocols for rational secret sharing where the values come from an unbounded domain, but with a finite (and polynomial sized) expectation. The protocol is a strict Nash equilibrium and it avoids the above mentioned problem of the last round.

Paper: Postscript, gzipped Postscript, PDF. Slides: ppt.

 
Related On-Line Papers:

Back to: On-Line PublicationsRecent Papers

Back Home