Document Open Access Logo

Truthful Information Dissemination in General Asynchronous Networks

Authors Lior Solodkin, Rotem Oshman

PDF
Thumbnail PDF

File

LIPIcs.DISC.2021.37.pdf
  • Filesize: 0.61 MB
  • 19 pages

Document Identifiers

Author Details

Lior Solodkin
  • Blavatnik School of Computer Science, Tel Aviv University, Israel
Rotem Oshman
  • Blavatnik School of Computer Science, Tel Aviv University, Israel

Funding

  • Oshman, Rotem: Research funded by the Israel Science Foundation, Grant No. 2801/20.

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.DISC.2021.37

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Theory of computation → Algorithmic game theory and mechanism design
Keywords
  • game theory
  • asynchronous networks
  • information dissemination

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ittai Abraham, Danny Dolev, Ivan Geffner, and Joseph Y. Halpern. Implementing mediators with asynchronous cheap talk. In PODC 2019, pages 501-510, 2019. Google Scholar
  2. Ittai Abraham, Danny Dolev, Rica Gonen, and Joe Halpern. Distributed computing meets game theory: Robust mechanisms for rational secret sharing and multiparty computation. In PODC 2006, pages 53-62, 2006. Google Scholar
  3. Ittai Abraham, Danny Dolev, and Joseph Y Halpern. Lower bounds on implementing robust and resilient mediators. In TCC 2008, pages 302-319, 2008. Google Scholar
  4. Ittai Abraham, Danny Dolev, and Joseph Y. Halpern. Distributed protocols for leader election: A game-theoretic perspective. ACM Trans. Economics and Comput., 7(1):4:1-4:26, 2019. Google Scholar
  5. Yehuda Afek, Yehonatan Ginzberg, Shir Landau Feibish, and Moshe Sulamy. Distributed computing building blocks for rational agents. In PODC 2014, pages 406-415, 2014. Google Scholar
  6. Yehuda Afek, Shaked Rafaeli, and Moshe Sulamy. The role of a-priori information in networks of rational agents. In DISC 2018, pages 5:1-5:18, 2018. Google Scholar
  7. Mor Amitai. Cheap-talk with incomplete information on both sides. Discussion paper 90, Center for Rationality, The Hebrew University of Jerusalem, 1996. Google Scholar
  8. Itai Ashlagi, Dov Monderer, and Moshe Tennenholtz. On the value of correlation. J. Artif. Int. Res., 33(1):575-613, 2008. Google Scholar
  9. Robert J. Aumann. Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics, 1(1):67-96, 1974. Google Scholar
  10. Elchanan Ben-Porath. Cheap talk in games with incomplete information. J. Economic Theory, 108(1):45-71, 2003. Google Scholar
  11. Arkadev Chattopadhyay, Jaikumar Radhakrishnan, and Atri Rudra. Topology matters in communication. In FOCS 2014, pages 631-640, 2014. Google Scholar
  12. Francoise Forges. An approach to communication equilibria. Econometrica, 54(6):1375-1385, 1986. Google Scholar
  13. Joseph Halpern and Vanessa Teague. Rational secret sharing and multiparty computation. In STOC 2004, pages 623-632, 2004. Google Scholar
  14. Joseph Y Halpern and Xavier Vilaça. Rational consensus. In PODC 2016, pages 137-146, 2016. Google Scholar
  15. Itay Harel, Amit Jacob-Fanani, Moshe Sulamy, and Yehuda Afek. Consensus in Equilibrium: Can One Against All Decide Fairly? In OPODIS 2019, pages 20:1-20:17, 2019. Google Scholar
  16. Juraj Hromkovič, Claus-Dieter Jeschke, and Burkhard Monien. Optimal algorithms for dissemination of information in some interconnection networks. Algorithmica, 10(1):24-40, 1993. Google Scholar
  17. Sergei Izmalkov, Silvio Micali, and Matt Lepinski. Rational secure computation and ideal mechanism design. In FOCS 2015, pages 585-594, 2015. Google Scholar
  18. David M Kreps and Robert Wilson. Sequential equilibria. Econometrica: Journal of the Econometric Society, pages 863-894, 1982. Google Scholar
  19. Matt Lepinski, Silvio Micali, Chris Peikert, and Abhi Shelat. Completely fair sfe and coalition-safe cheap talk. In PODC 2004, pages 1-10, 2004. Google Scholar
  20. Merav Parter and Eylon Yogev. Secure distributed computing made (nearly) optimal. In PODC 2019, pages 107-116, 2019. Google Scholar
  21. Ryan M. Rogers and Aaron Roth. Asymptotically truthful equilibrium selection in large congestion games. In Proceedings of the Fifteenth ACM Conference on Economics and Computation, EC '14, pages 771-782, 2014. Google Scholar
  22. R. W. Rosenthal. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2:65-67, 1973. Google Scholar
  23. Assaf Yifrach and Yishay Mansour. Fair leader election for rational agents in asynchronous rings and networks. In PODC 2018, pages 217-226, 2018. Google Scholar
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