Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review
Final published version
We study repeated games with absorbing states, a type of two-player, zero-sum concurrent mean-payoff games with the prototypical example being the Big Match of Gillete (1957). These games may not allow optimal strategies but they always have ε-optimal strategies. In this paper we design ε-optimal strategies for Player 1 in these games that use only O(log log T) space. Furthermore, we construct strategies for Player 1 that use space s(T), for an arbitrary small unbounded non-decreasing function s, and which guarantee an ε-optimal value for Player 1 in the limit superior sense. The previously known strategies use space Ω(log T) and it was known that no strategy can use constant space if it is ε-optimal even in the limit superior sense. We also give a complementary lower bound. Furthermore, we also show that no Markov strategy, even extended with finite memory, can ensure value greater than 0 in the Big Match, answering a question posed by Neyman [11].
Original language | English |
---|---|
Title of host publication | Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings |
Editors | Martin Gairing, Rahul Savani |
Number of pages | 13 |
Volume | 9928 |
Publisher | Springer VS |
Publication year | 2016 |
Pages | 64-76 |
ISBN (print) | 9783662533536 |
ISBN (Electronic) | 978-3-662-53354-3 |
DOIs | |
Publication status | Published - 2016 |
Event | 9th International Symposium on Algorithmic Game Theory, SAGT 2016 - Liverpool, United Kingdom Duration: 19 Sept 2016 → 21 Sept 2016 |
Conference | 9th International Symposium on Algorithmic Game Theory, SAGT 2016 |
---|---|
Land | United Kingdom |
By | Liverpool |
Periode | 19/09/2016 → 21/09/2016 |
Series | Lecture Notes in Computer Science |
---|---|
Volume | 9928 |
ISSN | 0302-9743 |
See relations at Aarhus University Citationformats
ID: 108448739