Document Open Access Logo

Concurrent Games and Semi-Random Determinacy

Author Stéphane Le Roux

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.40.pdf
  • Filesize: 443 kB
  • 15 pages

Document Identifiers

Author Details

Stéphane Le Roux
  • Darmstadt Technical University, Department of Mathematics, Darmstadt, Germany

Cite AsGet BibTex

Stéphane Le Roux. Concurrent Games and Semi-Random Determinacy. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 40:1-40:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.MFCS.2018.40

Abstract

Consider concurrent, infinite duration, two-player win/lose games played on graphs. If the winning condition satisfies some simple requirement, the existence of Player 1 winning (finite-memory) strategies is equivalent to the existence of winning (finite-memory) strategies in finitely many derived one-player games. Several classical winning conditions satisfy this simple requirement. Under an additional requirement on the winning condition, the non-existence of Player 1 winning strategies from all vertices is equivalent to the existence of Player 2 stochastic strategies almost-sure winning from all vertices. Only few classical winning conditions satisfy this additional requirement, but a fairness variant of omega-regular languages does.

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
  • Theory of computation → Verification by model checking
  • Software and its engineering → Software verification
  • Software and its engineering → Model checking
Keywords
  • Two-player win/lose
  • graph
  • infinite duration
  • abstract winning condition

Metrics

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

References

  1. Rajeev Alur, Marco Faella, Sampath Kannan, and Nimit Singhania. Hedging Bets in Markov Decision Processes. In Jean-Marc Talbot and Laurent Regnier, editors, 25th EACSL Annual Conference on Computer Science Logic (CSL 2016), volume 62 of Leibniz International Proceedings in Informatics (LIPIcs), pages 29:1-29:20, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.CSL.2016.29.
  2. Rajeev Alur and Thomas A. Henzinger. Finitary fairness. ACM Trans. Program. Lang. Syst., 20(6):1171-1194, 1998. URL: http://dx.doi.org/10.1145/295656.295659.
  3. Patricia Bouyer, Romain Brenguier, Nicolas Markey, and Michael Ummels. Concurrent games with ordered objectives. In Lars Birkedal, editor, Foundations of Software Science and Computational Structures, pages 301-315, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. Google Scholar
  4. Patricia Bouyer, Nicolas Markey, Mickael Randour, Kim G. Larsen, and Simon Laursen. Average-energy games. Acta Informatica, Jul 2016. URL: http://dx.doi.org/10.1007/s00236-016-0274-1.
  5. Véronique Bruyère, Quentin Hautem, and Mickael Randour. Window parity games: an alternative approach toward parity games with time bounds. In Proceedings of the Seventh International Symposium on Games, Automata, Logics and Formal Verification, GandALF 2016, Catania, Italy, 14-16 September 2016., pages 135-148, 2016. URL: http://dx.doi.org/10.4204/EPTCS.226.10.
  6. Krishnendu Chatterjee. Concurrent games with tail objectives. Theoretical Computer Science, 388(1):181-198, 2007. URL: http://dx.doi.org/10.1016/j.tcs.2007.07.047.
  7. Krishnendu Chatterjee and Laurent Doyen. Energy parity games. In Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, and Paul G. Spirakis, editors, Automata, Languages and Programming, pages 599-610, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. Google Scholar
  8. Krishnendu Chatterjee, Laurent Doyen, Mickael Randour, and Jean-François Raskin. Looking at mean-payoff and total-payoff through windows. Inf. Comput., 242:25-52, 2015. URL: http://dx.doi.org/10.1016/j.ic.2015.03.010.
  9. Krishnendu Chatterjee, Thomas A. Henzinger, and Florian Horn. Finitary winning in Ω-regular games. ACM Trans. Comput. Logic, 11(1):1:1-1:27, nov 2009. URL: http://dx.doi.org/10.1145/1614431.1614432.
  10. Thomas Colcombet and Damian Niwiński. On the positional determinacy of edge-labeled games. Theoretical Computer Science, 352(1):190-196, 2006. URL: http://dx.doi.org/10.1016/j.tcs.2005.10.046.
  11. Luca de Alfaro and Thomas A. Henzinger. Concurrent omega-regular games. In 15th Annual IEEE Symposium on Logic in Computer Science, Santa Barbara, California, USA, June 26-29, 2000, pages 141-154, 2000. URL: http://dx.doi.org/10.1109/LICS.2000.855763.
  12. Nachum Dershowitz, D. N. Jayasimha, and Seungjoon Park. Bounded Fairness, pages 304-317. Springer Berlin Heidelberg, Berlin, Heidelberg, 2003. URL: http://dx.doi.org/10.1007/978-3-540-39910-0_14.
  13. Hugo Gimbert and Florian Horn. Solving simple stochastic tail games. In Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '10, pages 847-862, Philadelphia, PA, USA, 2010. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=1873601.1873670.
  14. Hugo Gimbert and Wiesław Zielonka. Games where you can play optimally without any memory. In CONCUR 2005 - Concurrency Theory, volume 3653 of Lecture Notes in Computer Science, pages 428-442. Springer Berlin Heidelberg, 2005. Google Scholar
  15. Julian Gutierrez, Aniello Murano, Giuseppe Perelli, Sasha Rubin, and Michael Wooldridge. Nash equilibria in concurrent games with lexicographic preferences. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, pages 1067-1073, 2017. URL: http://dx.doi.org/10.24963/ijcai.2017/148.
  16. John Hopcroft and Jean-Jacques Pansiot. On the reachability problem for 5-dimensional vector addition systems. Theoretical Computer Science, 8(2):135-159, 1979. URL: http://dx.doi.org/10.1016/0304-3975(79)90041-0.
  17. Richard M. Karp and Raymond E. Miller. Parallel program schemata. Journal of Computer and System Sciences, 3(2):147-195, 1969. URL: http://dx.doi.org/10.1016/S0022-0000(69)80011-5.
  18. Eryk Kopczyński. Half-positional determinacy of infinite games. In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors, Automata, Languages and Programming, pages 336-347, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. Google Scholar
  19. Stéphane Le Roux. Infinite sequential Nash equilibrium. Logical Methods in Computer Science, 9, 2013. Special Issue for the Conference "Computability and Complexity in Analysis" (CCA 2011). Google Scholar
  20. Stéphane Le Roux. From winning strategy to nash equilibrium. Math. Log. Q., 60(4-5):354-371, 2014. URL: http://dx.doi.org/10.1002/malq.201300034.
  21. Stéphane Le Roux. Infinite subgame perfect equilibrium in the hausdorff difference hierarchy. In Topics in Theoretical Computer Science - The First IFIP WG 1.8 International Conference, TTCS 2015, Tehran, Iran, August 26-28, 2015, Revised Selected Papers, pages 147-163, 2015. URL: http://dx.doi.org/10.1007/978-3-319-28678-5_11.
  22. Stéphane Le Roux and Arno Pauly. Infinite sequential games with real-valued payoffs. In Proceedings of LiCS, 2014. Google Scholar
  23. Stéphane Le Roux and Arno Pauly. Extending finite memory determinacy to multiplayer games. In Proceedings of the 4th International Workshop on Strategic Reasoning, SR 2016, New York City, USA, 10th July 2016., pages 27-40, 2016. URL: http://dx.doi.org/10.4204/EPTCS.218.3.
  24. Stéphane Le Roux, Arno Pauly, and Jean-François Raskin. Minkowski games. In 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany, pages 50:1-50:13, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2017.50.
  25. Donald A. Martin. Borel determinacy. Annals of Mathematics, 102(2):363-371, 1975. URL: http://www.jstor.org/stable/1971035.
  26. Donald A. Martin. The determinacy of blackwell games. Journal of Symbolic Logic, 63(4):1565–1581, 1998. URL: http://dx.doi.org/10.2307/2586667.
  27. Stéphane Le Roux and Arno Pauly. Extending finite-memory determinacy to multi-player games. Information and Computation, pages -, 2018. URL: http://dx.doi.org/10.1016/j.ic.2018.02.024.
  28. Wolfgang Thomas. Languages, automata, and logic. In Salomaa A. Rozenberg G., editor, Handbook of Formal Languages. Springer, Berlin, Heidelberg, 1997. 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