The big match in small space Conference Paper

Author(s): Hansen, Kristoffer A; Ibsen-Jensen, Rasmus; Koucký, Michal
Title: The big match in small space
Title Series: LNCS
Affiliation IST Austria
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].
Keywords: Optimal strategies; Lower bounds; Finite memory; Mean payoff games; Optimal values; Absorbing state; Non-decreasing functions; Repeated games; Optimal systems
Conference Title: SAGT: Symposium on Algorithmic Game Theory
Volume: 9928
Conference Dates: September 19-21, 2016
Conference Location: Liverpool, United Kingdom
ISBN: 0302-9743
Publisher: Springer  
Date Published: 2016-09-01
Start Page: 64
End Page: 76
DOI: 10.1007/978-3-662-53354-3_6
Notes: The research leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement n. 616787. The first author acknowledges support from the Danish National Research Foundation and The National Science Foundation of China (under the grant 61361136003) for the Sino-Danish Center for the Theory of InteractiveComputation and from the Center for Research in Foundations of Electronic Markets (CFEM), supported by the Danish Strategic Research Council. The second author was partly supported by Austrian Science Fund (FWF) NFN Grant No S11407-N23 (RiSE/SHiNE), Vienna Science and Technology Fund (WWTF) through project ICT15-003, and ERC Start grant (279307: Graph Games). The third author was supported in part by grant from Neuron Fund for Support of Science, and by the Center of Excellence CE-ITI under the grant P202/12/G061 of GA ˇCR.
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work