Document Open Access Logo

Multi-Round Cooperative Search Games with Multiple Players

Authors Amos Korman , Yoav Rodeh

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.146.pdf
  • Filesize: 0.49 MB
  • 14 pages

Document Identifiers

Author Details

Amos Korman
  • Université de Paris, IRIF, CNRS, F-75013 Paris, France
Yoav Rodeh
  • Ort Braude College, Karmiel, Israel

Funding

This work has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (grant agreement No 648032).

Cite AsGet BibTex

Amos Korman and Yoav Rodeh. Multi-Round Cooperative Search Games with Multiple Players. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 146:1-146:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.146

Abstract

Assume that a treasure is placed in one of M boxes according to a known distribution and that k searchers are searching for it in parallel during T rounds. We study the question of how to incentivize selfish players so that group performance would be maximized. Here, this is measured by the success probability, namely, the probability that at least one player finds the treasure. We focus on congestion policies C(l) that specify the reward that a player receives if it is one of l players that (simultaneously) find the treasure for the first time. Our main technical contribution is proving that the exclusive policy, in which C(1)=1 and C(l)=0 for l>1, yields a price of anarchy of (1-(1-{1}/{k})^{k})^{-1}, and that this is the best possible price among all symmetric reward mechanisms. For this policy we also have an explicit description of a symmetric equilibrium, which is in some sense unique, and moreover enjoys the best success probability among all symmetric profiles. For general congestion policies, we show how to polynomially find, for any theta>0, a symmetric multiplicative (1+theta)(1+C(k))-equilibrium. Together with an appropriate reward policy, a central entity can suggest players to play a particular profile at equilibrium. As our main conceptual contribution, we advocate the use of symmetric equilibria for such purposes. Besides being fair, we argue that symmetric equilibria can also become highly robust to crashes of players. Indeed, in many cases, despite the fact that some small fraction of players crash (or refuse to participate), symmetric equilibria remain efficient in terms of their group performances and, at the same time, serve as approximate equilibria. We show that this principle holds for a class of games, which we call monotonously scalable games. This applies in particular to our search game, assuming the natural sharing policy, in which C(l)=1/l. For the exclusive policy, this general result does not hold, but we show that the symmetric equilibrium is nevertheless robust under mild assumptions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory and mechanism design
  • Theory of computation → Parallel algorithms
Keywords
  • Algorithmic Mechanism Design
  • Parallel Algorithms
  • Collaborative Search
  • Fault-Tolerance
  • Price of Anarchy
  • Price of Stability
  • Symmetric Equilibria

Metrics

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

Related Versions

References

  1. Susanne Albers and Matthias Hellwig. Online Makespan Minimization with Parallel Schedules. CoRR, abs/1304.5625, 2013. URL: http://arxiv.org/abs/1304.5625.
  2. Sayan Bhattacharya, Sungjin Im, Janardhan Kulkarni, and Kamesh Munagala. Coordination mechanisms from (almost) all scheduling policies. In Innovations in Theoretical Computer Science, ITCS'14, Princeton, NJ, USA, January 12-14, 2014, pages 121-134, 2014. URL: http://dx.doi.org/10.1145/2554797.2554811.
  3. Artur Czumaj and Berthold Vöcking. Tight Bounds for Worst-case Equilibria. ACM Trans. Algorithms, 3(1):4:1-4:17, February 2007. URL: http://dx.doi.org/10.1145/1186810.1186814.
  4. Dariusz Dereniowski, Yann Disser, Adrian Kosowski, Dominik Pajak, and Przemyslaw Uznanski. Fast collaborative graph exploration. Inf. Comput., 243:37-49, 2015. URL: http://dx.doi.org/10.1016/j.ic.2014.12.005.
  5. Stefan Dobrev, Rastislav Královic, and Dana Pardubská. Treasure Hunt with Barely Communicating Agents. In 21st International Conference on Principles of Distributed Systems, OPODIS 2017, Lisbon, Portugal, December 18-20, 2017, pages 14:1-14:16, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.OPODIS.2017.14.
  6. Yuval Emek, Tobias Langner, Jara Uitto, and Roger Wattenhofer. Solving the ANTS Problem with Asynchronous Finite State Machines. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II, pages 471-482, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43951-7_40.
  7. Ofer Feinerman and Amos Korman. The ANTS problem. Distributed Computing, 30(3):149-168, 2017. URL: http://dx.doi.org/10.1007/s00446-016-0285-8.
  8. Pierre Fraigniaud, Amos Korman, and Yoav Rodeh. Parallel Bayesian Search with no Coordination. J. ACM, 2019. Google Scholar
  9. Peter Frazier, David Kempe, Jon Kleinberg, and Robert Kleinberg. Incentivizing exploration. In Proceedings of the fifteenth ACM conference on Economics and computation, pages 5-22. ACM, 2014. Google Scholar
  10. Martin Gairing. Covering Games: Approximation through Non-cooperation. In Internet and Network Economics, 5th International Workshop, WINE 2009, Rome, Italy, December 14-18, 2009. Proceedings, pages 184-195, 2009. URL: http://dx.doi.org/10.1007/978-3-642-10841-9_18.
  11. Luc-Alain Giraldeau and Thomas Caraco. Social Foraging Theory. Princeton University Press, 2000. Google Scholar
  12. Ronen Gradwohl and Omer Reingold. Fault tolerance in large games. Games and Economic Behavior, 86:438-457, 2014. URL: http://dx.doi.org/10.1016/j.geb.2013.06.007.
  13. Joseph Y. Halpern. A computer scientist looks at game theory. Games and Economic Behavior, 45(1):114-131, 2003. URL: http://dx.doi.org/10.1016/S0899-8256(02)00529-8.
  14. Joseph Y. Halpern. Computer Science and Game Theory: A Brief Survey. CoRR, abs/cs/0703148, 2007. URL: http://arxiv.org/abs/cs/0703148.
  15. Yuya Higashikawa, Naoki Katoh, Stefan Langerman, and Shin-Ichi Tanigawa. Online Graph Exploration Algorithms for Cycles and Trees by Multiple Searchers. J. Comb. Optim., 28(2):480-495, August 2014. URL: http://dx.doi.org/10.1007/s10878-012-9571-y.
  16. Thomas T Hills, Peter M Todd, David Lazer, A David Redish, Iain D Couzin, Cognitive Search Research Group, et al. Exploration versus exploitation in space, mind, and society. Trends in cognitive sciences, 19(1):46-54, 2015. Google Scholar
  17. Martyn Kennedy and Russell D. Gray. Can Ecological Theory Predict the Distribution of Foraging Animals? A Critical Analysis of Experiments on the Ideal Free Distribution. Oikos, 68(1):158-166, 1993. URL: http://www.jstor.org/stable/3545322.
  18. Jon Kleinberg and Sigal Oren. Mechanisms for (mis) allocating scientific credit. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 529-538. ACM, 2011. Google Scholar
  19. Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. Computer Science Review, 3(2):65-69, 2009. URL: http://dx.doi.org/10.1016/j.cosrev.2009.04.003.
  20. Ilan Kremer, Yishay Mansour, and Motty Perry. Implementing the "Wisdom of the Crowd". Journal of Political Economy, 122(5):988-1012, 2014. Google Scholar
  21. Yishay Mansour, Aleksandrs Slivkins, and Vasilis Syrgkanis. Bayesian incentive-compatible bandit exploration. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, pages 565-582. ACM, 2015. Google Scholar
  22. Dov Monderer and Lloyd S Shapley. Potential games. Games and economic behavior, 14(1):124-143, 1996. Google Scholar
  23. John Nash. Non-Cooperative Games. Annals of Mathematics, 54(2):286-295, 1951. URL: http://www.jstor.org/stable/1969529.
  24. Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007. Google Scholar
  25. University of California Berkeley. BOINC. https://boinc.berkeley.edu/, 2017.
  26. Yiangos Papanastasiou, Kostas Bimpikis, and Nicos Savva. Crowdsourcing exploration. Management Science, 2017. Google Scholar
  27. Arthur C Pigou. The Economics of Welfare. Library of Economics and Liberty, 1932. Google Scholar
  28. Vinod Ramaswamy, Dario Paccagnan, and Jason R. Marden. The Impact of Local Information on the Performance of Multiagent Systems. CoRR, abs/1710.01409, 2017. URL: http://arxiv.org/abs/1710.01409.
  29. Robert W Rosenthal. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2(1):65-67, 1973. Google Scholar
  30. Christian Scheideler and Jeremy T. Fineman, editors. Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, SPAA 2018, Vienna, Austria, July 16-18, 2018. ACM, 2018. URL: http://dx.doi.org/10.1145/3210377.
  31. Adrian Vetta. Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions. In Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on, pages 416-425. IEEE, 2002. 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