November 28, Tuesday
12:00 – 14:00
Distributed Computing Meets Game Theory: upper and lower bounds for mediator implementation with cheap talk
Computer Science seminar
Lecturer : Ittai Abraham
Affiliation : The Hebrew University of Jerusalem
Location : -101/58
Host : Dr. Michael Elkin
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. Joint work with Danny Dolev, Rica Gonen and Joe Halpern