Distributed Computing Meets Game Theory: Fault Tolerance and Implementation with Cheap Talk

Traditionally, work in distributed computing has divided the agents into "good guys" and "bad guys".  The good guys follow the protocol; the bad guys do everything in their power to make sure it does not work.  By way of contrast, game theory has focused on ``rational'' agents, who try to maximize their utilities.  Here I try to combine these viewpoints. Specifically, I consider what we call (k,t)-robust protocols/strategies, which tolerate coalitions of rational players of size up to $k$ and up to $t$ malicious players.   I focus in particular on the problem that economists have called implementing a mediator; in computer science, this essentially amounts to multiparty computation.  Ideas from cryptography and distributed computing allow us to prove results on how many agents are required to implement a (k,t)-robust mediator just using "cheap talk", that is, just talking to each other.  These results subsume (and, in some cases, correct) results from the game theory literature. The talk is self-contained.  No background in game theory or distributed computing will be assumed.  It includes joint work with Ittai Abraham, Danny Dolev, Ivan Geffner, and Rica Gonen.