@inproceedings{f2e17f90a5b64507aabdf04a3438e707,
title = "Games for exchanging information",
abstract = "We consider the rational versions of two of the classical problems in foundations of cryptography: secret sharing and multiparty computation, suggested by Halpern and Teague (STOC 2004). Our goal is to design games and fair strategies that encourage rational participants to exchange information about their inputs for their mutual benefit, when the only mean of communication is a broadcast channel. We show that protocols for the above information exchanging tasks, where players' values come from a bounded domain, cannot satisfy some of the most desirable properties. In contrast, we provide a rational secret sharing scheme with simultaneous broadcast channel in which shares are taken from an unbounded domain, but have finite (and poly-nomial sized) expectation. Previous schemes (mostly cryptographic) have required computational assumptions, making them inexact and susceptible to backward induction, or used stronger communication channels. Our scheme is non-cryptographic, immune to backward induction, and satisfies a stronger rationality concept (strict Nash equilibrium). We show that our solution can also be used to construct an ε-Nash equilibrium secret sharing scheme for the case of a non-simultaneous broadcast channel.",
keywords = "Backward induction, Computation, Cryptography, Game theory, Multiparty, Nash equilibrium, Secret sharing",
author = "Gillat Kol and Moni Naor",
year = "2008",
doi = "10.1145/1374376.1374437",
language = "English (US)",
isbn = "9781605580470",
series = "Proceedings of the Annual ACM Symposium on Theory of Computing",
publisher = "Association for Computing Machinery (ACM)",
pages = "423--432",
booktitle = "STOC'08",
address = "United States",
note = "40th Annual ACM Symposium on Theory of Computing, STOC 2008 ; Conference date: 17-05-2008 Through 20-05-2008",
}