Distributed
Computing Meets Game Theory: Robust Mechanisms for Rational Secret Sharing and Multiparty
Computation
Ittai Abraham Danny Dolev Rica Gonen Joe Halpern
Abstract
We study k-resilient Nash equilibria,
joint strategies where no member of a coalition C of size up to k can do
better, even if the whole coalition defects. We show that such k-resilient Nash
equilibria exist for secret sharing and multiparty computation,
provided that players prefer to get the information than not to get it. Our
results hold even if there are only 2 players, so we can do multiparty
computation with only two rational agents. We extend our results so that they
hold even in the presence of up to t players with “unexpected” utilities.
Finally, we show that our techniques can be used to simulate games with
mediators by games without mediators.
[PODC pdf]