Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.13933 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910835746537472 |
|---|---|
| author | Gimbert, Hugo Paul, Soumyajit Srivathsan, B. |
| author_facet | Gimbert, Hugo Paul, Soumyajit Srivathsan, B. |
| contents | In games with imperfect recall, players may forget the sequence of decisions they made in the past. When players also forget whether they have already encountered their current decision point, they are said to be absent-minded. Solving one-player imperfect recall games is known to be NP-hard, even when the players are not absent-minded. This motivates the search for polynomial-time solvable subclasses. A special type of imperfect recall, called A-loss recall, is amenable to efficient polynomial-time algorithms. In this work, we present novel techniques to simplify non-absent-minded imperfect recall games into equivalent A-loss recall games. The first idea involves shuffling the order of actions, and leads to a new polynomial-time solvable class of imperfect recall games that extends A-loss recall. The second idea generalises the first one, by constructing a new set of action sequences which can be "linearly combined" to give the original game. The equivalent game has a simplified information structure, but it could be exponentially bigger in size (in accordance with the NP-hardness). We present an algorithm to generate an equivalent A-loss recall game with the smallest size. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_13933 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Simplifying imperfect recall games Gimbert, Hugo Paul, Soumyajit Srivathsan, B. Computer Science and Game Theory In games with imperfect recall, players may forget the sequence of decisions they made in the past. When players also forget whether they have already encountered their current decision point, they are said to be absent-minded. Solving one-player imperfect recall games is known to be NP-hard, even when the players are not absent-minded. This motivates the search for polynomial-time solvable subclasses. A special type of imperfect recall, called A-loss recall, is amenable to efficient polynomial-time algorithms. In this work, we present novel techniques to simplify non-absent-minded imperfect recall games into equivalent A-loss recall games. The first idea involves shuffling the order of actions, and leads to a new polynomial-time solvable class of imperfect recall games that extends A-loss recall. The second idea generalises the first one, by constructing a new set of action sequences which can be "linearly combined" to give the original game. The equivalent game has a simplified information structure, but it could be exponentially bigger in size (in accordance with the NP-hardness). We present an algorithm to generate an equivalent A-loss recall game with the smallest size. |
| title | Simplifying imperfect recall games |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2502.13933 |