The Big Match in Small Space (Extended Abstract)



Hansen, Kristoffer Arnsfelt, Ibsen-Jensen, Rasmus and Koucky, Michal
(2016) The Big Match in Small Space (Extended Abstract). .

[img] 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