The big match in small space

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

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 languageEnglish
Title of host publicationAlgorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings
EditorsMartin Gairing, Rahul Savani
Number of pages13
Volume9928
PublisherSpringer VS
Publication year2016
Pages64-76
ISBN (print)9783662533536
ISBN (Electronic)978-3-662-53354-3
DOIs
Publication statusPublished - 2016
Event9th International Symposium on Algorithmic Game Theory, SAGT 2016 - Liverpool, United Kingdom
Duration: 19 Sep 201621 Sep 2016

Conference

Conference9th International Symposium on Algorithmic Game Theory, SAGT 2016
LandUnited Kingdom
ByLiverpool
Periode19/09/201621/09/2016
SeriesLecture Notes in Computer Science
Volume 9928
ISSN0302-9743

See relations at Aarhus University Citationformats

ID: 108448739