Arena-Independent Finite-Memory Determinacy in Stochastic Games

Bouyer, Patricia; Oualhadj, Youssouf; Randour, Mickaël; Vandenhove, Pierre

doi:10.4230/LIPIcs.CONCUR.2021.26

Download

Paper published in a journal (Scientific congresses and symposiums)

Arena-Independent Finite-Memory Determinacy in Stochastic Games

Bouyer, Patricia; Oualhadj, Youssouf; Randour, Mickaël et al.

2021 • In Leibniz International Proceedings in Informatics, 203, p. 26:1-26:18

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/20.500.12907/32103

DOI
10.4230/LIPIcs.CONCUR.2021.26

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

2102.10104.pdf

Author preprint (566.72 kB)

Download

All documents in ORBi UMONS are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Research center :

CREMMI - Modélisation mathématique et informatique

Disciplines :

Mathematics
Computer science

Author, co-author :

Bouyer, Patricia; Université Paris-Saclay > Laboratoire Méthodes Formelles (LMF)

Oualhadj, Youssouf; Univ Paris Est Creteil > LACL

Randour, Mickaël ; Université de Mons > Faculté des Sciences > Service de Mathématiques effectives

Vandenhove, Pierre ; Université de Mons - UMONS > Faculté des Sciences > Service de Mathématiques effectives ; Université Paris-Saclay > Laboratoire Méthodes Formelles (LMF)

Language :

English

Title :

Arena-Independent Finite-Memory Determinacy in Stochastic Games

Publication date :

23 August 2021

Event name :

International Conference on Concurrency Theory

Event place :

Paris, France

Event date :

2021

Event number :

32nd

Audience :

International

Journal title :

Leibniz International Proceedings in Informatics

ISSN :

1868-8969

Publisher :

[Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH], Germany

Volume :

203

Pages :

26:1-26:18

Peer reviewed :

Peer Reviewed verified by ORBi

Research unit :

S820 - Mathématiques effectives

Research institute :

R150 - Institut de Recherche sur les Systèmes Complexes

Name of the research project :

4743 - ASP-Vandenhove - FrontieRS - Fédération Wallonie Bruxelles
3284 - CQ-Randour - ManySynth - Fédération Wallonie Bruxelles
3944 - MIS-Randour - ManySynth - Fédération Wallonie Bruxelles
3750 - MS FNRS IN-Oualhadj - Synthèse de contrôleurs pour systèmes réactifs: synthèse quantitative dans des environnements stochastiques - Fédération Wallonie Bruxelles

Funders :

F.R.S.-FNRS - Fonds de la Recherche Scientifique [BE]

Available on ORBi UMONS :

since 05 July 2021

Statistics

Number of views

1 (1 by UMONS)

Number of downloads

2 (0 by UMONS)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

Bibliography

Benjamin Aminof and Sasha Rubin. First-cycle games. Inf. Comput., 254:195-216, 2017. doi:10.1016/j.ic.2016.10.008.
Christel Baier and Joost-Pieter Katoen. Principles of model checking. MIT Press, 2008.
Raphaël Berthon, Mickael Randour, and Jean-François Raskin. Threshold constraints with guarantees for parity objectives in Markov decision processes. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 121:1-121:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPIcs.ICALP.2017.121.
Alessandro Bianco, Marco Faella, Fabio Mogavero, and Aniello Murano. Exploring the boundary of half-positionality. Ann. Math. Artif. Intell., 62(1-2):55-77, 2011. doi:10.1007/s10472-011-9250-1.
Patricia Bouyer, Ulrich Fahrenberg, Kim Guldstrand Larsen, Nicolas Markey, and Jirí Srba. Infinite runs in weighted timed automata with energy constraints. In Franck Cassez and Claude Jard, editors, Formal Modeling and Analysis of Timed Systems, 6th International Conference, FORMATS 2008, Saint Malo, France, September 15-17, 2008. Proceedings, volume 5215 of Lecture Notes in Computer Science, pages 33-47. Springer, 2008. doi:10.1007/978-3-540-85778-5-4.
Patricia Bouyer, Piotr Hofman, Nicolas Markey, Mickael Randour, and Martin Zimmermann. Bounding average-energy games. In Javier Esparza and Andrzej S. Murawski, editors, Foundations of Software Science and Computation Structures - 20th International Conference, FOSSACS 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Uppsala, Sweden, April 22-29, 2017, Proceedings, volume 10203 of Lecture Notes in Computer Science, pages 179-195, 2017. doi:10.1007/978-3-662-54458-7-11.
Patricia Bouyer, Stéphane Le Roux, Youssouf Oualhadj, Mickael Randour, and Pierre Vandenhove. Games where you can play optimally with arena-independent finite memory. In Igor Konnov and Laura Kovács, editors, 31st International Conference on Concurrency Theory, CONCUR 2020, September 1-4, 2020, Vienna, Austria (Virtual Conference), volume 171 of LIPIcs, pages 24:1-24:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs.CONCUR.2020.24.
Patricia Bouyer, Nicolas Markey, Mickael Randour, Kim G. Larsen, and Simon Laursen. Average-energy games. Acta Informatica, 55(2):91-127, 2018. doi:10.1007/s00236-016-0274-1.
Patricia Bouyer, Youssouf Oualhadj, Mickael Randour, and Pierre Vandenhove. Arenaindependent finite-memory determinacy in stochastic games. CoRR, abs/2102.10104, 2021. arXiv:2102.10104.
Tomás Brázdil, Václav Brozek, and Kousha Etessami. One-counter stochastic games. In Kamal Lodaya and Meena Mahajan, editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010, December 15-18, 2010, Chennai, India, volume 8 of LIPIcs, pages 108-119. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010. doi:10.4230/LIPIcs.FSTTCS.2010.108.
Thomas Brihaye, Florent Delgrange, Youssouf Oualhadj, and Mickael Randour. Life is random, time is not: Markov decision processes with window objectives. Log. Methods Comput. Sci., 16(4), 2020. URL: https://lmcs.episciences.org/6975.
Véronique Bruyère, Emmanuel Filiot, Mickael Randour, and Jean-François Raskin. Meet your expectations with guarantees: Beyond worst-case synthesis in quantitative games. Inf. Comput., 254:259-295, 2017. doi:10.1016/j.ic.2016.10.011.
Véronique Bruyère, Quentin Hautem, and Mickael Randour. Window parity games: an alternative approach toward parity games with time bounds. In Domenico Cantone and Giorgio Delzanno, editors, Proceedings of the Seventh International Symposium on Games, Automata, Logics and Formal Verification, GandALF 2016, Catania, Italy, 14-16 September 2016, volume 226 of EPTCS, pages 135-148, 2016. doi:10.4204/EPTCS.226.10.
Véronique Bruyère, Quentin Hautem, Mickael Randour, and Jean-François Raskin. Energy mean-payoff games. In Wan Fokkink and Rob van Glabbeek, editors, 30th International Conference on Concurrency Theory, CONCUR 2019, August 27-30, 2019, Amsterdam, the Netherlands, volume 140 of LIPIcs, pages 21:1-21:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.CONCUR.2019.21.
Krishnendu Chatterjee. The complexity of stochastic Müller games. Inf. Comput., 211:29-48, 2012. doi:10.1016/j.ic.2011.11.004.
Krishnendu Chatterjee, Luca de Alfaro, and Thomas A. Henzinger. Trading memory for randomness. In 1st International Conference on Quantitative Evaluation of Systems (QEST 2004), 27-30 September 2004, Enschede, The Netherlands, pages 206-217. IEEE Computer Society, 2004. doi:10.1109/QEST.2004.1348035.
Krishnendu Chatterjee and Laurent Doyen. Energy parity games. Theor. Comput. Sci., 458:49-60, 2012. doi:10.1016/j.tcs.2012.07.038.
Krishnendu Chatterjee and Laurent Doyen. Perfect-information stochastic games with generalized mean-payoff objectives. In Martin Grohe, Eric Koskinen, and Natarajan Shankar, editors, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '16, New York, NY, USA, July 5-8, 2016, pages 247-256. ACM, 2016. doi:10.1145/2933575.2934513.
Krishnendu Chatterjee, Laurent Doyen, Hugo Gimbert, and Thomas A. Henzinger. Randomness for free. In Petr Hlinený and Antonín Kucera, editors, Mathematical Foundations of Computer Science 2010, 35th International Symposium, MFCS 2010, Brno, Czech Republic, August 23-27, 2010. Proceedings, volume 6281 of Lecture Notes in Computer Science, pages 246-257. Springer, 2010. doi:10.1007/978-3-642-15155-2-23.
Krishnendu Chatterjee and Thomas A. Henzinger. A survey of stochastic ω-regular games. J. Comput. Syst. Sci., 78(2):394-413, 2012. doi:10.1016/j.jcss.2011.05.002.
Krishnendu Chatterjee, Thomas A. Henzinger, and Nir Piterman. Generalized parity games. In Helmut Seidl, editor, Foundations of Software Science and Computational Structures, 10th International Conference, FOSSACS 2007, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2007, Braga, Portugal, March 24-April 1, 2007, Proceedings, volume 4423 of Lecture Notes in Computer Science, pages 153-167. Springer, 2007. doi:10.1007/978-3-540-71389-0-12.
Krishnendu Chatterjee, Marcin Jurdzinski, and Thomas A. Henzinger. Quantitative stochastic parity games. In J. Ian Munro, editor, Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 11- 14, 2004, pages 121-130. SIAM, 2004. URL: http://dl.acm.org/citation.cfm?id=982792. 982808.
Krishnendu Chatterjee, Joost-Pieter Katoen, Maximilian Weininger, and Tobias Winkler. Stochastic games with lexicographic reachability-safety objectives. In Shuvendu K. Lahiri and Chao Wang, editors, Computer Aided Verification - 32nd International Conference, CAV 2020, Los Angeles, CA, USA, July 21-24, 2020, Proceedings, Part II, volume 12225 of Lecture Notes in Computer Science, pages 398-420. Springer, 2020. doi:10.1007/978-3-030-53291-8-21.
Krishnendu Chatterjee, Zuzana Kretínská, and Jan Kretínský. Unifying two views on multiple mean-payoff objectives in Markov decision processes. Log. Methods Comput. Sci., 13(2), 2017. doi:10.23638/LMCS-13(2:15)2017.
Krishnendu Chatterjee and Nir Piterman. Combinations of qualitative winning for stochastic parity games. In Wan J. Fokkink and Rob van Glabbeek, editors, 30th International Conference on Concurrency Theory, CONCUR 2019, August 27-30, 2019, Amsterdam, the Netherlands, volume 140 of LIPIcs, pages 6:1-6:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.CONCUR.2019.6.
Krishnendu Chatterjee, Mickael Randour, and Jean-François Raskin. Strategy synthesis for multi-dimensional quantitative objectives. Acta Inf., 51(3-4):129-163, 2014. doi:10.1007/s00236-013-0182-6.
Taolue Chen, Vojtech Forejt, Marta Z. Kwiatkowska, Aistis Simaitis, Ashutosh Trivedi, and Michael Ummels. Playing stochastic games precisely. In Maciej Koutny and Irek Ulidowski, editors, CONCUR 2012 - Concurrency Theory - 23rd International Conference, CONCUR 2012, Newcastle upon Tyne, UK, September 4-7, 2012. Proceedings, volume 7454 of Lecture Notes in Computer Science, pages 348-363. Springer, 2012. doi:10.1007/978-3-642-32940-1-25.
Taolue Chen, Vojtech Forejt, Marta Z. Kwiatkowska, Aistis Simaitis, and Clemens Wiltsche. On stochastic games with multiple objectives. In Krishnendu Chatterjee and Jirí Sgall, editors, Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings, volume 8087 of Lecture Notes in Computer Science, pages 266-277. Springer, 2013. doi:10.1007/978-3-642-40313-2-25.
Anne Condon. The complexity of stochastic games. Inf. Comput., 96(2):203-224, 1992. doi:10.1016/0890-5401(92)90048-K.
Florent Delgrange, Joost-Pieter Katoen, Tim Quatmann, and Mickael Randour. Simple strategies in multi-objective MDPs. In Armin Biere and David Parker, editors, Tools and Algorithms for the Construction and Analysis of Systems - 26th International Conference, TACAS 2020, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020, Dublin, Ireland, April 25-30, 2020, Proceedings, Part I, volume 12078 of Lecture Notes in Computer Science, pages 346-364. Springer, 2020. doi:10.1007/978-3-030-45190-5-19.
Hugo Gimbert. Pure stationary optimal strategies in Markov decision processes. In Wolfgang Thomas and Pascal Weil, editors, STACS 2007, 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007, Proceedings, volume 4393 of Lecture Notes in Computer Science, pages 200-211. Springer, 2007. doi:10.1007/978-3-540-70918-3-18.
Hugo Gimbert and Edon Kelmendi. Submixing and shift-invariant stochastic games. CoRR, abs/1401.6575, 2014. arXiv:1401.6575.
Hugo Gimbert and Wieslaw Zielonka. Games where you can play optimally without any memory. In Martín Abadi and Luca de Alfaro, editors, CONCUR 2005 - Concurrency Theory, 16th International Conference, CONCUR 2005, San Francisco, CA, USA, August 23-26, 2005, Proceedings, volume 3653 of Lecture Notes in Computer Science, pages 428-442. Springer, 2005. doi:10.1007/11539452-33.
Hugo Gimbert and Wieslaw Zielonka. Pure and Stationary Optimal Strategies in Perfect- Information Stochastic Games with Global Preferences. Unpublished, 2009. URL: https://hal.archives-ouvertes.fr/hal-00438359.
Eryk Kopczynski. Half-positional determinacy of infinite games. In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors, Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part II, volume 4052 of Lecture Notes in Computer Science, pages 336-347. Springer, 2006. doi:10.1007/11787006-29.
Eryk Kopczynski. Half-positional Determinacy of Infinite Games. PhD thesis, Warsaw University, 2008.
Stéphane Le Roux and Arno Pauly. Extending finite-memory determinacy to multi-player games. Inf. Comput., 261(Part):676-694, 2018. doi:10.1016/j.ic.2018.02.024.
Stéphane Le Roux, Arno Pauly, and Mickael Randour. Extending finite-memory determinacy by boolean combination of winning conditions. In Sumit Ganguly and Paritosh K. Pandya, editors, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018, December 11-13, 2018, Ahmedabad, India, volume 122 of LIPIcs, pages 38:1-38:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. doi: 10.4230/LIPIcs.FSTTCS.2018.38.
Richard Mayr, Sven Schewe, Patrick Totzke, and Dominik Wojtczak. MDPs with energyparity objectives. In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20-23, 2017, pages 1-12. IEEE Computer Society, 2017. doi:10.1109/LICS.2017.8005131.
Richard Mayr, Sven Schewe, Patrick Totzke, and Dominik Wojtczak. Simple stochastic games with almost-sure energy-parity objectives are in NP and coNP. In Stefan Kiefer and Christine Tasson, editors, Foundations of Software Science and Computation Structures - 24th International Conference, FOSSACS 2021, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2021, Luxembourg City, Luxembourg, March 27 - April 1, 2021, Proceedings, volume 12650 of Lecture Notes in Computer Science, pages 427-447. Springer, 2021. doi:10.1007/978-3-030-71995-1-22.
Benjamin Monmege, Julie Parreaux, and Pierre-Alain Reynier. Reaching your goal optimally by playing at random with no memory. In Igor Konnov and Laura Kovács, editors, 31st International Conference on Concurrency Theory, CONCUR 2020, September 1-4, 2020, Vienna, Austria (Virtual Conference), volume 171 of LIPIcs, pages 26:1-26:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs.CONCUR.2020.26.
Andrzej W. Mostowski. Regular expressions for infinite trees and a standard form of automata. In Andrzej Skowron, editor, Computation Theory - Fifth Symposium, Zaborów, Poland, December 3-8, 1984, Proceedings, volume 208 of Lecture Notes in Computer Science, pages 157-168. Springer, 1984. doi:10.1007/3-540-16066-3-15.
Martin J. Osborne. An introduction to game theory. Oxford University Press, 2004.
Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley Series in Probability and Statistics. Wiley, 1994. doi:10.1002/9780470316887.
Mickael Randour. Automated synthesis of reliable and efficient systems through game theory: A case study. In Proc. of ECCS 2012, Springer Proceedings in Complexity XVII, pages 731-738. Springer, 2013. doi:10.1007/978-3-319-00395-5-90.
Mickael Randour, Jean-François Raskin, and Ocan Sankur. Variations on the stochastic shortest path problem. In Deepak D'Souza, Akash Lal, and Kim Guldstrand Larsen, editors, Verification, Model Checking, and Abstract Interpretation - 16th International Conference, VMCAI 2015, Mumbai, India, January 12-14, 2015. Proceedings, volume 8931 of Lecture Notes in Computer Science, pages 1-18. Springer, 2015. doi:10.1007/978-3-662-46081-8-1.
Mickael Randour, Jean-François Raskin, and Ocan Sankur. Percentile queries in multidimensional Markov decision processes. Formal Methods Syst. Des., 50(2-3):207-248, 2017. doi:10.1007/s10703-016-0262-7.
L. S. Shapley. Stochastic games. Proceedings of the National Academy of Sciences, 39(10):1095- 1100, 1953. doi:10.1073/pnas.39.10.1095.
Wolfgang Thomas. Church's problem and a tour through automata theory. In Arnon Avron, Nachum Dershowitz, and Alexander Rabinovich, editors, Pillars of Computer Science, Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday, volume 4800 of Lecture Notes in Computer Science, pages 635-655. Springer, 2008. doi:10.1007/978-3-540-78127-1-35.
Yaron Velner, Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger, Alexander Moshe Rabinovich, and Jean-François Raskin. The complexity of multi-mean-payoff and multi-energy games. Inf. Comput., 241:177-196, 2015. doi:10.1016/j.ic.2015.03.001.