#
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 Publications, Recent Papers

Back Home