Document Open Access Logo

The Role of A-priori Information in Networks of Rational Agents

Authors Yehuda Afek, Shaked Rafaeli, Moshe Sulamy

PDF
Thumbnail PDF

File

LIPIcs.DISC.2018.5.pdf
  • Filesize: 0.65 MB
  • 18 pages

Document Identifiers

Author Details

Yehuda Afek
  • Tel-Aviv University, Tel-Aviv, Israel
Shaked Rafaeli
  • Tel-Aviv University, Tel-Aviv, Israel
Moshe Sulamy
  • Tel-Aviv University, Tel-Aviv, Israel

Funding

This research was supported by the Israel Science Foundation (grant 1386/11).

Cite As Get BibTex

Yehuda Afek, Shaked Rafaeli, and Moshe Sulamy. The Role of A-priori Information in Networks of Rational Agents. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.DISC.2018.5

Abstract

Until now, distributed algorithms for rational agents have assumed a-priori knowledge of n, the size of the network. This assumption is challenged here by proving how much a-priori knowledge is necessary for equilibrium in different distributed computing problems. Duplication - pretending to be more than one agent - is the main tool used by agents to deviate and increase their utility when not enough knowledge about n is given.
We begin by proving that when no information on n is given, equilibrium is impossible for both Coloring and Knowledge Sharing. We then provide new algorithms for both problems when n is a-priori known to all agents. However, what if agents have partial knowledge about n? We provide tight upper and lower bounds that must be a-priori known on n for equilibrium to be possible in Leader Election, Knowledge Sharing, Coloring, Partition and Orientation.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
Keywords
  • rational agents
  • distributed game theory
  • coloring
  • knowledge sharing

Metrics

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

Related Versions

References

  1. Ittai Abraham, Lorenzo Alvisi, and Joseph Y. Halpern. Distributed computing meets game theory: Combining insights from two fields. SIGACT News, 42(2):69-76, 2011. URL: http://dx.doi.org/10.1145/1998037.1998055.
  2. Ittai Abraham, Danny Dolev, Rica Gonen, and Joseph Y. Halpern. Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation. In PODC, pages 53-62, 2006. URL: http://dx.doi.org/10.1145/1146381.1146393.
  3. Ittai Abraham, Danny Dolev, and Joseph Y. Halpern. Lower bounds on implementing robust and resilient mediators. In TCC, pages 302-319, 2008. URL: http://dx.doi.org/10.1007/978-3-540-78524-8_17.
  4. Ittai Abraham, Danny Dolev, and Joseph Y. Halpern. Distributed protocols for leader election: A game-theoretic perspective. In DISC, pages 61-75, 2013. URL: http://dx.doi.org/10.1007/978-3-642-41527-2_5.
  5. Norman Abramson. The aloha system: Another alternative for computer communications. In Proceedings of the November 17-19, 1970, Fall Joint Computer Conference, AFIPS '70 (Fall), pages 281-285, New York, NY, USA, 1970. ACM. Google Scholar
  6. Y. Afek, S. Rafaeli, and M. Sulamy. Cheating by Duplication: Equilibrium Requires Global Knowledge. ArXiv e-prints, 2017. URL: http://arxiv.org/abs/1711.04728.
  7. Yehuda Afek, Yehonatan Ginzberg, Shir Landau Feibish, and Moshe Sulamy. Distributed computing building blocks for rational agents. In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, PODC '14, 2014. Google Scholar
  8. Amitanand S. Aiyer, Lorenzo Alvisi, Allen Clement, Michael Dahlin, Jean-Philippe Martin, and Carl Porth. Bar fault tolerance for cooperative services. In SOSP, pages 45-58, 2005. URL: http://dx.doi.org/10.1145/1095810.1095816.
  9. Hagit Attiya and Jennifer Welch. Distributed Computing: Fundamentals, Simulations and Advanced Topics. John Wiley &Sons, 2004. Google Scholar
  10. B. Awerbuch, M. Luby, A. V. Goldberg, and S. A. Plotkin. Network decomposition and locality in distributed computation. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science, SFCS '89, pages 364-369, Washington, DC, USA, 1989. IEEE Computer Society. URL: http://dx.doi.org/10.1109/SFCS.1989.63504.
  11. D. Bank, M. Sulamy, and E. Waserman. Reaching Distributed Equilibrium with Limited ID Space. ArXiv e-prints, 2018. URL: http://arxiv.org/abs/1804.06197.
  12. Imre Bárány. Fair distribution protocols or how the players replace fortune. Math. Oper. Res., 17(2):327-340, 1992. URL: http://dx.doi.org/10.1287/moor.17.2.327.
  13. Elchanan Ben-Porath. Cheap talk in games with incomplete information. J. Economic Theory, 108(1):45-71, 2003. URL: http://dx.doi.org/10.1016/S0022-0531(02)00011-X.
  14. Rajat Bhattacharjee and Ashish Goel. Avoiding ballot stuffing in ebay-like reputation systems. In Proceedings of the 2005 ACM SIGCOMM Workshop on Economics of Peer-to-peer Systems, P2PECON '05, pages 133-137, New York, NY, USA, 2005. ACM. Google Scholar
  15. Monica Bianchini, Marco Gori, and Franco Scarselli. Inside pagerank. ACM Trans. Internet Technol., 5(1):92-128, 2005. Google Scholar
  16. Alice Cheng and Eric Friedman. Sybilproof reputation mechanisms. In Proceedings of the 2005 ACM SIGCOMM Workshop on Economics of Peer-to-peer Systems, P2PECON '05, pages 128-132, New York, NY, USA, 2005. ACM. Google Scholar
  17. Richard Cole and Uzi Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking. Inf. Control, 70(1):32-53, 1986. Google Scholar
  18. Varsha Dani, Mahnush Movahedi, Yamel Rodriguez, and Jared Saia. Scalable rational secret sharing. In PODC, pages 187-196, 2011. URL: http://dx.doi.org/10.1145/1993806.1993833.
  19. Yevgeniy Dodis, Shai Halevi, and Tal Rabin. A cryptographic solution to a game theoretic problem. In CRYPTO, pages 112-130, 2000. URL: http://dx.doi.org/10.1007/3-540-44598-6_7.
  20. John R. Douceur. The sybil attack. In Revised Papers from the First International Workshop on Peer-to-Peer Systems, IPTPS '01, pages 251-260, London, UK, UK, 2002. Springer-Verlag. Google Scholar
  21. Georg Fuchsbauer, Jonathan Katz, and David Naccache. Efficient rational secret sharing in standard communication networks. In TCC, pages 419-436, 2010. URL: http://dx.doi.org/10.1007/978-3-642-11799-2_25.
  22. S. Dov Gordon and Jonathan Katz. Rational secret sharing, revisited. In SCN, pages 229-241, 2006. URL: http://dx.doi.org/10.1007/11832072_16.
  23. Adam Groce, Jonathan Katz, Aishwarya Thiruvengadam, and Vassilis Zikas. Byzantine agreement with a rational adversary. In ICALP (2), pages 561-572, 2012. URL: http://dx.doi.org/10.1007/978-3-642-31585-5_50.
  24. Joseph Y. Halpern and Xavier Vilaça. Rational consensus: Extended abstract. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC '16, pages 137-146, New York, NY, USA, 2016. ACM. Google Scholar
  25. L. Kleinrock and F. Tobagi. Packet switching in radio channels: Part i - carrier sense multiple-access modes and their throughput-delay characteristics. IEEE Transactions on Communications, 23(12):1400-1416, December 1975. Google Scholar
  26. Fabian Kuhn and Rogert Wattenhofer. On the complexity of distributed graph coloring. In Proceedings of the Twenty-fifth Annual ACM Symposium on Principles of Distributed Computing, PODC '06, pages 7-15, New York, NY, USA, 2006. ACM. URL: http://dx.doi.org/10.1145/1146381.1146387.
  27. Matt Lepinski, Silvio Micali, Chris Peikert, and Abhi Shelat. Completely fair sfe and coalition-safe cheap talk. In PODC, pages 1-10, 2004. URL: http://dx.doi.org/10.1145/1011767.1011769.
  28. N. Linial. Legal coloring of graphs. Combinatorica, 6(1):49-54, 1986. URL: http://dx.doi.org/10.1007/BF02579408.
  29. Nathan Linial. Distributive graph algorithms global solutions from local data. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science, SFCS '87, pages 331-335, Washington, DC, USA, 1987. IEEE Computer Society. URL: http://dx.doi.org/10.1109/SFCS.1987.20.
  30. Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193-201, 1992. URL: http://dx.doi.org/10.1137/0221015.
  31. Anna Lysyanskaya and Nikos Triandopoulos. Rationality and adversarial behavior in multi-party computation. In CRYPTO, pages 180-197, 2006. URL: http://dx.doi.org/10.1007/11818175_11.
  32. Robert McGrew, Ryan Porter, and Yoav Shoham. Towards a general theory of non-cooperative computation. In TARK, pages 59-71, 2003. URL: http://dx.doi.org/10.1145/846241.846249.
  33. Thomas Moscibroda, Stefan Schmid, and Roger Wattenhofer. When selfish meets evil: byzantine players in a virus inoculation game. In PODC, pages 35-44, 2006. URL: http://dx.doi.org/10.1145/1146381.1146391.
  34. Rafael Pass and Elaine Shi. Hybrid Consensus: Efficient Consensus in the Permissionless Model. In 31st International Symposium on Distributed Computing (DISC 2017), 2017. Google Scholar
  35. Rafael Pass and Elaine Shi. The sleepy model of consensus. In Tsuyoshi Takagi and Thomas Peyrin, editors, Advances in Cryptology - ASIACRYPT 2017, pages 380-409, Cham, 2017. Springer International Publishing. Google Scholar
  36. Rafael Pass and Elaine Shi. Rethinking large-scale consensus. Cryptology ePrint Archive, Report 2018/302, 2018. URL: https://eprint.iacr.org/2018/302.
  37. Adi Shamir. How to share a secret. Commun. ACM, 22(11):612-613, 1979. URL: http://dx.doi.org/10.1145/359168.359176.
  38. Yoav Shoham and Moshe Tennenholtz. Non-cooperative computation: Boolean functions with correctness and exclusivity. Theoretical Computer Science, 343(1–2):97-113, 2005. Google Scholar
  39. Márió Szegedy and Sundar Vishwanathan. Locality based graph coloring. In Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, STOC '93, pages 201-207, New York, NY, USA, 1993. ACM. URL: http://dx.doi.org/10.1145/167088.167156.
  40. Amparo Urbano and Jose E. Vila. Computational complexity and communication: Coordination in two-player games. Econometrica, 70(5):1893-1927, September 2002. URL: http://ideas.repec.org/a/ecm/emetrp/v70y2002i5p1893-1927.html.
  41. Amparo Urbano and José E. Vila. Computationally restricted unmediated talk under incomplete information. Economic theory, 2004. Google Scholar
  42. Edmund L. Wong, Isaac Levy, Lorenzo Alvisi, Allen Clement, and Michael Dahlin. Regret freedom isn't free. In OPODIS, pages 80-95, 2011. URL: http://dx.doi.org/10.1007/978-3-642-25873-2_7.
  43. Assaf Yifrach and Yishay Mansour. Fair leader election for rational agents in asynchronous rings and networks. In PODC '18, 2018. URL: http://dx.doi.org/10.1145/3212734.3212767.
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 About DROPS Imprint Privacy Contact