License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.Tokenomics.2021.1
URN: urn:nbn:de:0030-drops-158981
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15898/
Halpern, Joseph Y.
Distributed Computing Meets Game Theory: Fault Tolerance and Implementation with Cheap Talk (Invited Talk)
Abstract
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, following the work of Abraham et al. [I. Abraham et al., 2006], I consider (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. That is, can the players in the system, just talking among themselves (using what economists call "cheap talk") simulate the effects of the mediator (see, e.g., [I. Barany, 1992; E. Ben-Porath, 2003; Forges, 1990; D. Gerardi, 2004; Y. Heller, 2005; A. Urbano and J. E. Vila, 2002; A. Urbano and J. E. Vila, 2004]). In computer science, this essentially amounts to multiparty computation [O. Goldreich et al., 1987; A. Shamir et al., 1981; A. Yao, 1982]. 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. These results subsume (and, in some cases, correct) results from the game theory literature.
The results of Abraham et al. [I. Abraham et al., 2006] were proved for what are called synchronous systems in the distributed computing community; this is also the case for all the results in the economics literature cited above. In synchronous systems, communication proceeds in atomic rounds, and all messages sent during round r are received by round r + 1. But many systems in the real world are asynchronous. In an asynchronous setting, there are no rounds; messages sent by the players may take arbitrarily long to get to their recipients. Markets and the internet are best viewed as asynchronous. Blockchain implementations assume partial synchrony, where there is an upper bound on how long messages take to arrive. The partial synchronous setting already shows some of the difficulty of moving away from synchrony: An agent i can wait to take its action until it receives a message from j (on which its action can depend). This cannot happen in a synchronous setting. Abraham, Dolev, Geffner, abnd Halpern [I. Abraham et al., 2019] extend the results on implementing mediators to the asynchronous setting.
BibTeX - Entry
@InProceedings{halpern:OASIcs.Tokenomics.2021.1,
author = {Halpern, Joseph Y.},
title = {{Distributed Computing Meets Game Theory: Fault Tolerance and Implementation with Cheap Talk}},
booktitle = {3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)},
pages = {1:1--1:2},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-220-4},
ISSN = {2190-6807},
year = {2022},
volume = {97},
editor = {Gramoli, Vincent and Halaburda, Hanna and Pass, Rafael},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15898},
URN = {urn:nbn:de:0030-drops-158981},
doi = {10.4230/OASIcs.Tokenomics.2021.1},
annote = {Keywords: robust equilibrium, implementing mediators, asynchronous systems}
}
|
Keywords: |
|
robust equilibrium, implementing mediators, asynchronous systems |
|
Collection: |
|
3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
18.03.2022 |
