The big match in small space

Hansen, KA, Ibsen-Jensen, R ORCID: 0000-0003-4783-0389 and Koucký, M (2016) The big match in small space .

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 Item (Unspecified)
Uncontrolled Keywords:	46 Information and Computing Sciences
Depositing User:	Symplectic Admin
Date Deposited:	06 Dec 2018 09:19
Last Modified:	01 Mar 2026 03:28
DOI:	10.1007/978-3-662-53354-3_6
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3029577
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.