Distributed Computing Meets Game Theory:Robust Mechanisms for Rational Secret Sharing and

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. Categories and Subject Descriptors: F.0 [Theory of Computation]: General