Distributed Computing Meets Game Theory: upper and lower bounds for mediator implementation with cheap talk (Joint work with Danny Dolev, Rica Gonen and Joe Halpern)

Abstract: A mediator can help non-cooperative agents obtain an equilibrium that may otherwise not be possible. We give matching upper and lower bounds on the ability of rational agents to obtain the same equilibrium without a mediator, simply by engaging in non-binding pre-play communication, known as ``cheap talk''. Our upper bounds are based on k-resilient Nash equilibria for the secret sharing game, joint strategies where no member of a coalition of size up to k can do better, even if the whole coalition defects. Our results on implementing mediators with ``cheap talk'' reveal some connections between game theory, cryptography and distributed computing. Our upper bounds require both known and new tools in secure multi party computation. Our lower bounds require both known and new results in Byzantine fault tolerance and distributed computing.

Elath Hall, 2nd floor, Feldman Building, Edmond J. Safra Campus
Sunday, March 18, 2007 - 16:15 to 18:15
Old Lecturers: 
Old Lecturers University: