Document Open Access Logo

Games with Delays - A Frankenstein Approach

Authors Dietmar Berwanger, Marie van den Bogaard

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2015.307.pdf
  • Filesize: 401 kB
  • 13 pages

Document Identifiers

Author Details

Dietmar Berwanger
Marie van den Bogaard

Cite AsGet BibTex

Dietmar Berwanger and Marie van den Bogaard. Games with Delays - A Frankenstein Approach. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 307-319, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.FSTTCS.2015.307

Abstract

We investigate infinite games on finite graphs where the information flow is perturbed by non- deterministic signalling delays. It is known that such perturbations make synthesis problems virtually unsolvable, in the general case. On the classical model where signals are attached to states, tractable cases are rare and difficult to identify. In this paper, we propose a model where signals are detached from control states, and we identify a subclass on which equilibrium outcomes can be preserved, even if signals are delivered with a delay that is finitely bounded. To offset the perturbation, our solution procedure combines responses from a collection of virtual plays following an equilibrium strategy in the instant- signalling game to synthesise, in a Dr. Frankenstein manner, an equivalent equilibrium strategy for the delayed-signalling game.
Keywords
  • infinite games on graphs
  • imperfect information
  • delayed monitoring
  • distributed synthesis

Metrics

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

References

  1. Salman Azhar, Gary Peterson, and John Reif. Lower bounds for multiplayer non-cooperative games of incomplete information. Journal of Computers and Mathematics with Applications, 41:957-992, 2001. Google Scholar
  2. Dietmar Berwanger, Łukasz Kaiser, and Bernd Puchala. Perfect-information construction for coordination in games. In Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011), Proc., volume 13 of Leibniz International Proceedings in Informatics, pages 387-398, Mumbai, India, December 2011. Leibniz-Zentrum für Informatik. Google Scholar
  3. Patricia Bouyer, Romain Brenguier, Nicolas Markey, and Michael Ummels. Nash equilibria in concurrent games with Büchi objectives. In Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011), Proc., volume 13 of LIPIcs, pages 375-386. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2011. Google Scholar
  4. Patricia Bouyer, Romain Brenguier, Nicolas Markey, and Michael Ummels. Pure Nash equilibria in concurrent games. Logical Methods in Computer Science, 11(2:9), June 2015. Google Scholar
  5. Thomas Brihaye, Véronique Bruyére, and Julie De Pril. On equilibria in quantitative games with reachability/safety objectives. Theory of Computing Systems, 54(2):150-189, 2014. Google Scholar
  6. Krishnendu Chatterjee, Laurent Doyen, Emmanuel Filiot, and Jean-François Raskin. Doomsday equilibria for omega-regular games. In KennethL. McMillan and Xavier Rival, editors, Verification, Model Checking, and Abstract Interpretation, volume 8318 of Lecture Notes in Computer Science, pages 78-97. Springer Berlin Heidelberg, 2014. Google Scholar
  7. B. Finkbeiner and S. Schewe. Uniform distributed synthesis. In Logic in Computer Science (LICS'05), Proc., pages 321-330. IEEE, 2005. Google Scholar
  8. Drew Fudenberg, Yuhta Ishii, and Scott Duke Kominers. Delayed-response strategies in repeated games with observation lags. J. Economic Theory, 150:487-514, 2014. Google Scholar
  9. Hugo Gimbert and Edon Kelmendi. Two-player perfect-information shift-invariant submixing stochastic games are half-positional. CoRR, abs/1401.6575, 2014. Google Scholar
  10. Orna Kupferman and Moshe Y. Vardi. Synthesizing distributed systems. In Logic in Computer Science (LICS'01), Proc., pages 389-398. IEEE Computer Society Press, June 2001. Google Scholar
  11. Gary L. Peterson and John H. Reif. Multiple-Person Alternation. In Proc 20th Annual Symposium on Foundations of Computer Science, (FOCS 1979), pages 348-363. IEEE, 1979. Google Scholar
  12. Amir Pnueli and Roni Rosner. Distributed reactive systems are hard to synthesize. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science, (FoCS '90), pages 746-757. IEEE Computer Society Press, 1990. Google Scholar
  13. Dinah Rosenberg, Eilon Solan, and Nicolas Vieille. Stochastic games with imperfect monitoring. In Alain Haurie, Shigeo Muto, LeonA. Petrosjan, and T.E.S. Raghavan, editors, Advances in Dynamic Games, volume 8 of Annals of the International Society of Dynamic Games, pages 3-22. Birkhäuser Boston, 2006. Google Scholar
  14. Eran Shmaya. The determinacy of infinite games with eventual perfect monitoring. Proc. Am. Math. Soc., 139(10):3665-3678, 2011. Google Scholar
  15. Michael Ummels. The complexity of Nash equilibria in infinite multiplayer games. In Roberto Amadio, editor, Foundations of Software Science and Computational Structures, volume 4962 of Lecture Notes in Computer Science, pages 20-34. Springer Berlin Heidelberg, 2008. Google Scholar
  16. Michael Ummels and Dominik Wojtczak. The complexity of Nash equilibria in limit-average games. In Joost-Pieter Katoen and Barbara König, editors, CONCUR 2011 – Concurrency Theory, volume 6901 of Lecture Notes in Computer Science, pages 482-496. Springer Berlin Heidelberg, 2011. Google Scholar
  17. Michael Ummels and Dominik Wojtczak. The complexity of Nash equilibria in stochastic multiplayer games. Logical Methods in Computer Science, 7(3), 2011. 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