Playing Stochastically in Weighted Timed Games to Emulate Memory
Weighted timed games are two-player zero-sum games played in a timed automaton equipped with integer weights. We consider optimal reachability objectives, in which one of the players, that we call Min, wants to reach a target location while minimising the cumulated weight. While knowing if Min has a...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2025-02-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | http://lmcs.episciences.org/10993/pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849344769024589824 |
|---|---|
| author | Benjamin Monmege Julie Parreaux Pierre-Alain Reynier |
| author_facet | Benjamin Monmege Julie Parreaux Pierre-Alain Reynier |
| author_sort | Benjamin Monmege |
| collection | DOAJ |
| description | Weighted timed games are two-player zero-sum games played in a timed automaton equipped with integer weights. We consider optimal reachability objectives, in which one of the players, that we call Min, wants to reach a target location while minimising the cumulated weight. While knowing if Min has a strategy to guarantee a value lower than a given threshold is known to be undecidable (with two or more clocks), several conditions, one of them being divergence, have been given to recover decidability. In such weighted timed games (like in untimed weighted games in the presence of negative weights), Min may need finite memory to play (close to) optimally. This is thus tempting to try to emulate this finite memory with other strategic capabilities. In this work, we allow the players to use stochastic decisions, both in the choice of transitions and of timing delays. We give a definition of the expected value in weighted timed games. We then show that, in divergent weighted timed games as well as in (untimed) weighted games (that we call shortest-path games in the following), the stochastic value is indeed equal to the classical (deterministic) value, thus proving that Min can guarantee the same value while only using stochastic choices, and no memory. |
| format | Article |
| id | doaj-art-e1a9a3bec1ae44f0aa579fd9be820352 |
| institution | Kabale University |
| issn | 1860-5974 |
| language | English |
| publishDate | 2025-02-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj-art-e1a9a3bec1ae44f0aa579fd9be8203522025-08-20T03:42:35ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742025-02-01Volume 21, Issue 110.46298/lmcs-21(1:19)202510993Playing Stochastically in Weighted Timed Games to Emulate MemoryBenjamin MonmegeJulie ParreauxPierre-Alain ReynierWeighted timed games are two-player zero-sum games played in a timed automaton equipped with integer weights. We consider optimal reachability objectives, in which one of the players, that we call Min, wants to reach a target location while minimising the cumulated weight. While knowing if Min has a strategy to guarantee a value lower than a given threshold is known to be undecidable (with two or more clocks), several conditions, one of them being divergence, have been given to recover decidability. In such weighted timed games (like in untimed weighted games in the presence of negative weights), Min may need finite memory to play (close to) optimally. This is thus tempting to try to emulate this finite memory with other strategic capabilities. In this work, we allow the players to use stochastic decisions, both in the choice of transitions and of timing delays. We give a definition of the expected value in weighted timed games. We then show that, in divergent weighted timed games as well as in (untimed) weighted games (that we call shortest-path games in the following), the stochastic value is indeed equal to the classical (deterministic) value, thus proving that Min can guarantee the same value while only using stochastic choices, and no memory.http://lmcs.episciences.org/10993/pdfcomputer science - computer science and game theory |
| spellingShingle | Benjamin Monmege Julie Parreaux Pierre-Alain Reynier Playing Stochastically in Weighted Timed Games to Emulate Memory Logical Methods in Computer Science computer science - computer science and game theory |
| title | Playing Stochastically in Weighted Timed Games to Emulate Memory |
| title_full | Playing Stochastically in Weighted Timed Games to Emulate Memory |
| title_fullStr | Playing Stochastically in Weighted Timed Games to Emulate Memory |
| title_full_unstemmed | Playing Stochastically in Weighted Timed Games to Emulate Memory |
| title_short | Playing Stochastically in Weighted Timed Games to Emulate Memory |
| title_sort | playing stochastically in weighted timed games to emulate memory |
| topic | computer science - computer science and game theory |
| url | http://lmcs.episciences.org/10993/pdf |
| work_keys_str_mv | AT benjaminmonmege playingstochasticallyinweightedtimedgamestoemulatememory AT julieparreaux playingstochasticallyinweightedtimedgamestoemulatememory AT pierrealainreynier playingstochasticallyinweightedtimedgamestoemulatememory |