Strategy improvement for concurrent reachability and turn-based stochastic safety games

Area of Science:

• Game theory
• Theoretical computer science
• Algorithmic game theory

Background:

• Concurrent games involve simultaneous player moves determining state transitions.
• Key objectives include safety (staying in states) and reachability (reaching states).
• Existing proofs for memoryless optimal strategies in concurrent games can be complex.

Purpose of the Study:

• To present a simpler, combinatorial proof for the existence of memoryless epsilon-optimal strategies in concurrent reachability games.
• To introduce a strategy-improvement algorithm for concurrent games with reachability objectives.
• To develop a strategy-improvement algorithm for turn-based stochastic games with safety objectives.

Main Methods:

• A novel, elementary, and combinatorial proof technique for strategy existence.
• Development and application of strategy-improvement (policy-iteration) algorithms.
• Analysis of strategy sequences for monotonic convergence to game values.

Main Results:

• A simplified proof demonstrates the existence of memoryless epsilon-optimal strategies for concurrent reachability games.
• A new strategy-improvement algorithm is proposed for concurrent reachability games.
• A strategy-improvement algorithm is presented for turn-based stochastic games with safety objectives.

Conclusions:

• The study provides elementary proofs and efficient algorithms for solving concurrent and turn-based stochastic games.
• Algorithms guarantee monotonic convergence of player-1 winning probabilities to the game's value.
• Findings contribute to the understanding and computational solution of complex game-theoretic problems.