From Local to Global Optimality in Concurrent Parity Games

被引:0
作者
Bordais, Benjamin [1 ,2 ,3 ]
Bouyer, Patricia [1 ]
Le Roux, Stephane [1 ]
机构
[1] Univ Paris Saclay, LMF, ENS Paris Saclay, CNRS, F-91190 Gif Sur Yvette, France
[2] TU Dortmund Univ, Dortmund, Germany
[3] Univ Alliance Ruhr, Ctr Trustworthy Data Sci & Secur, Dortmund, Germany
来源
32ND EACSL ANNUAL CONFERENCE ON COMPUTER SCIENCE LOGIC, CSL 2024 | 2024年 / 288卷
关键词
Game forms; stochastic games; parity games; Blackwell/Martin values;
D O I
10.4230/LIPIcs.CSL.2024.18
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
We study two-player games on finite graphs. Turn-based games have many nice properties, but concurrent games are harder to tame: e.g. turn-based stochastic parity games have positional optimal strategies, whereas even basic concurrent reachability games may fail to have optimal strategies. We study concurrent stochastic parity games, and identify a local structural condition that, when satisfied at each state, guarantees existence of positional optimal strategies for both players.
引用
收藏
页数:21
相关论文
共 16 条
[1]  
Bordais B, 2023, Arxiv, DOI arXiv:2311.14373
[2]   Subgame Optimal Strategies in Finite Concurrent Games with Prefix-Independent Objectives [J].
Bordais, Benjamin ;
Bouyer, Patricia ;
Le Roux, Stephane .
FOUNDATIONS OF SOFTWARE SCIENCE AND COMPUTATION STRUCTURES, FOSSACS 2023, 2023, 13992 :541-560
[3]  
Bordais Benjamin, 2021, LIPICS, V213, DOI [10.4230/ LIPIcs. FSTTCS. 2021.41, DOI 10.4230/LIPICS.FSTTCS.2021.41]
[4]  
Bordais Benjamin, 2022, LIPICS, V250, DOI [10.4230/LIPIcs.FSTTCS.2022.33, DOI 10.4230/LIPICS.FSTTCS.2022.33]
[5]  
Bordais Benjamin, 2022, LIPIcs, V216, DOI DOI 10.4230/LIPICS
[6]  
Chatterjee K., 2004, P 15 ANN ACM SIAM S, P121
[7]   The Complexity of Quantitative Concurrent Parity Games [J].
Chatterjee, Krishnendu ;
de Alfaro, Luca ;
Henzinger, Thomas A. .
PROCEEDINGS OF THE SEVENTHEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2006, :678-+
[8]   Quantitative solution of omega-regular games [J].
de Alfaro, L ;
Majumdar, R .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2004, 68 (02) :374-397
[9]   Concurrent omega-regular games [J].
de Alfaro, L ;
Henzinger, TA .
15TH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, PROCEEDINGS, 2000, :141-154
[10]  
Everett H, 1957, ANN MATH STUD, V3, P67, DOI DOI 10.1515/9781400882151-004