1 Search Results for "Solodkin, Lior"

Document
DOI: 10.4230/LIPIcs.DISC.2021.37
Truthful Information Dissemination in General Asynchronous Networks

Authors: Lior Solodkin and Rotem Oshman

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

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.
Cite as

Lior Solodkin and Rotem Oshman. Truthful Information Dissemination in General Asynchronous Networks. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 37:1-37:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.37},
  URN =		{urn:nbn:de:0030-drops-148398},
  doi =		{10.4230/LIPIcs.DISC.2021.37},
  annote =	{Keywords: game theory, asynchronous networks, information dissemination}
}
  • Refine by Author
  • 1 Oshman, Rotem
  • 1 Solodkin, Lior

  • Refine by Classification
  • 1 Theory of computation → Algorithmic game theory and mechanism design
  • 1 Theory of computation → Distributed algorithms

  • Refine by Keyword
  • 1 asynchronous networks
  • 1 game theory
  • 1 information dissemination

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact