Playing against fair adversaries in stochastic games with total rewards
34th International Conference, CAV 2022, Haifa, Israel, August 7–10, 2022, Proceedings, Part II.
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | info:eu-repo/semantics/publishedVersion |
| Language: | eng |
| Published: |
2023
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/11086/546743 https://doi.org/10.1007/978-3-031-13188-2_3 |
| _version_ | 1801215884555976704 |
|---|---|
| author | Castro, Pablo Francisco D'Argenio, Pedro Ruben Demasi, Ramiro Adrián Putruele, Luciano |
| author2 | https://orcid.org/0000-0002-5835-4333 |
| author_facet | https://orcid.org/0000-0002-5835-4333 Castro, Pablo Francisco D'Argenio, Pedro Ruben Demasi, Ramiro Adrián Putruele, Luciano |
| author_sort | Castro, Pablo Francisco |
| collection | Repositorio Digital Universitario |
| description | 34th International Conference, CAV 2022, Haifa, Israel, August 7–10, 2022, Proceedings, Part II. |
| format | info:eu-repo/semantics/publishedVersion |
| id | rdu-unc.546743 |
| institution | Universidad Nacional de Cordoba |
| language | eng |
| publishDate | 2023 |
| record_format | dspace |
| spelling | rdu-unc.5467432023-08-31T13:16:53Z Playing against fair adversaries in stochastic games with total rewards Castro, Pablo Francisco D'Argenio, Pedro Ruben Demasi, Ramiro Adrián Putruele, Luciano https://orcid.org/0000-0002-5835-4333 https://orcid.org/0000-0002-8528-9215 https://orcid.org/0000-0003-1651-624X https://orcid.org/0000-0002-3063-4704 Teoría de juegos estocásticos Recompensa total esperada Stochastic game theory Expected total reward Fairness 34th International Conference, CAV 2022, Haifa, Israel, August 7–10, 2022, Proceedings, Part II. info:eu-repo/semantics/publishedVersion Fil: Castro, Pablo Francisco. Universidad Nacional de Rı́o Cuarto. Facultad de Ciencias Exactas, Físico-Químicas y Naturales. Departamento de Computación; Argentina. Fil: Castro, Pablo Francisco. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Fil: D'Argenio, Pedro Ruben. Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía, Física y Computación; Argentina. Fil: D'Argenio, Pedro Ruben. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Fil: D'Argenio, Pedro Ruben. Saarland University. Saarland Informatics Campus; Germany. Fil: Demasi, Ramiro Adrián. Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía, Física y Computación; Argentina. Fil: Demasi, Ramiro Adrián. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Fil: Putruele, Luciano. Universidad Nacional de Rı́o Cuarto. Facultad de Ciencias Exactas, Físico-Químicas y Naturales. Departamento de Computación; Argentina. Fil: Putruele, Luciano. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. 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. This work was supported by ANPCyT PICT-2017-3894 (RAFTSys), ANPCyT PICT 2019-03134, SeCyT-UNC 33620180100354CB (ARES), and EU Grant agreement ID: 101008233 (MISSION). info:eu-repo/semantics/publishedVersion Fil: Castro, Pablo Francisco. Universidad Nacional de Rı́o Cuarto. Facultad de Ciencias Exactas, Físico-Químicas y Naturales. Departamento de Computación; Argentina. Fil: Castro, Pablo Francisco. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Fil: D'Argenio, Pedro Ruben. Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía, Física y Computación; Argentina. Fil: D'Argenio, Pedro Ruben. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Fil: D'Argenio, Pedro Ruben. Saarland University. Saarland Informatics Campus; Germany. Fil: Demasi, Ramiro Adrián. Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía, Física y Computación; Argentina. Fil: Demasi, Ramiro Adrián. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Fil: Putruele, Luciano. Universidad Nacional de Rı́o Cuarto. Facultad de Ciencias Exactas, Físico-Químicas y Naturales. Departamento de Computación; Argentina. Fil: Putruele, Luciano. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. 2023-03-22T12:35:13Z 2023-03-22T12:35:13Z 2022 article http://hdl.handle.net/11086/546743 https://doi.org/10.1007/978-3-031-13188-2_3 eng Atribución 4.0 Internacional http://creativecommons.org/licenses/by/4.0/ Impreso; Electrónico y/o Digital e-ISSN: 1611-3349 ISSN: 0302-9743 e-ISBN: 978-3-031-13188-2 ISBN: 978-3-031-13187-5 |
| spellingShingle | Teoría de juegos estocásticos Recompensa total esperada Stochastic game theory Expected total reward Fairness Castro, Pablo Francisco D'Argenio, Pedro Ruben Demasi, Ramiro Adrián Putruele, Luciano Playing against fair adversaries in stochastic games with total rewards |
| title | Playing against fair adversaries in stochastic games with total rewards |
| title_full | Playing against fair adversaries in stochastic games with total rewards |
| title_fullStr | Playing against fair adversaries in stochastic games with total rewards |
| title_full_unstemmed | Playing against fair adversaries in stochastic games with total rewards |
| title_short | Playing against fair adversaries in stochastic games with total rewards |
| title_sort | playing against fair adversaries in stochastic games with total rewards |
| topic | Teoría de juegos estocásticos Recompensa total esperada Stochastic game theory Expected total reward Fairness |
| url | http://hdl.handle.net/11086/546743 https://doi.org/10.1007/978-3-031-13188-2_3 |
| work_keys_str_mv | AT castropablofrancisco playingagainstfairadversariesinstochasticgameswithtotalrewards AT dargeniopedroruben playingagainstfairadversariesinstochasticgameswithtotalrewards AT demasiramiroadrian playingagainstfairadversariesinstochasticgameswithtotalrewards AT putrueleluciano playingagainstfairadversariesinstochasticgameswithtotalrewards |