Hansen, Kristoffer Arnsfelt, Ibsen-Jensen, Rasmus and Koucky, Michal
(2016)
The Big Match in Small Space (Extended Abstract).
.
Text
BigMatchSmallSpace.pdf - Submitted version Download (523kB) |
Abstract
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].
Item Type: | Conference or Workshop Item (Unspecified) |
---|---|
Depositing User: | Symplectic Admin |
Date Deposited: | 06 Dec 2018 09:19 |
Last Modified: | 19 Jan 2023 01:09 |
DOI: | 10.1007/978-3-662-53354-3_6 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3029577 |