Playing Against Fair Adversaries in Stochastic Games with Total Rewards
| Title | Playing Against Fair Adversaries in Stochastic Games with Total Rewards |
| Publication Type | Book Chapter |
| Year of Publication | 2022 |
| Authors | Castro, PF, D'Argenio, PR, Demasi, R, Putruele, L |
| Editor | Shoham, S, Vizel, Y |
| Book Title | Computer Aided Verification - 34th International Conference, CAV 2022, Haifa, Israel, August 7-10, 2022, Proceedings, Part II |
| Series Title | Lecture Notes in Computer Science |
| Volume | 13372 |
| Pagination | 48–69 |
| Publisher | Springer |
| Abstract | We investigate zero-sum turn-based two-player stochastic games in which the objective of one player is to maximize the amount of rewards obtained during a play, while the other aims at minimizing it. We focus on games in which the minimizer plays in a fair way. We believe that these kinds of games enjoy interesting applications in software verification, where the maximizer plays the role of a system intending to maximize the number of “milestones” achieved, and the minimizer represents the behavior of some uncooperative but yet fair environment. Normally, to study total reward properties, games are requested to be stopping (i.e., they reach a terminal state with probability 1). We relax the property to request that the game is stopping only under a fair minimizing player. We prove that these games are determined, i.e., each state of the game has a value defined. Furthermore, we show that both players have memoryless and deterministic optimal strategies, and the game value can be computed by approximating the greatest-fixed point of a set of functional equations. We implemented our approach in a prototype tool, and evaluated it on an illustrating example and an Unmanned Aerial Vehicle case study. |
| URL | https://doi.org/10.1007/978-3-031-13188-2_3 |
| DOI | 10.1007/978-3-031-13188-2_3 |
PDF (Full text):
