License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2021.37
URN: urn:nbn:de:0030-drops-148398
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14839/
Go to the corresponding LIPIcs Volume Portal

Solodkin, Lior ; Oshman, Rotem

Truthful Information Dissemination in General Asynchronous Networks

pdf-format:
LIPIcs-DISC-2021-37.pdf (0.6 MB)

Abstract

We give a protocol for information dissemination in asynchronous networks of rational players, where each player may have its own desires and preferences as to the outcome of the protocol, and players may deviate from the protocol if doing so achieves their goals. We show that under minimalistic assumptions, it is possible to solve the information dissemination problem in a truthful manner, such that no participant has an incentive to deviate from the protocol we design. Our protocol works in any asynchronous network, provided the network graph is at least 2-connected. We complement the protocol with two impossibility results, showing that 2-connectivity is necessary, and also that our protocol achieves optimal bit complexity.
As an application, we show that truthful information dissemination can be used to implement a certain class of communication equilibria, which are equilibria that are typically reached by interacting with a trusted third party. Recent work has shown that communication equilibria can be implemented in synchronous networks, or in asynchronous, complete networks; we show that in some useful cases, our protocol yields a lightweight mechanism for implementing communication equilibria in any 2-connected asynchronous network.

BibTeX - Entry

@InProceedings{solodkin_et_al:LIPIcs.DISC.2021.37,
  author =	{Solodkin, Lior and Oshman, Rotem},
  title =	{{Truthful Information Dissemination in General Asynchronous Networks}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{37:1--37:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14839},
  URN =		{urn:nbn:de:0030-drops-148398},
  doi =		{10.4230/LIPIcs.DISC.2021.37},
  annote =	{Keywords: game theory, asynchronous networks, information dissemination}
}

Keywords: game theory, asynchronous networks, information dissemination
Collection: 35th International Symposium on Distributed Computing (DISC 2021)
Issue Date: 2021
Date of publication: 04.10.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI