The big match in small space

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

Standard

The big match in small space. / Hansen, Kristoffer Arnsfelt; Ibsen-Jensen, Rasmus; Koucký, Michal.

Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings. ed. / Martin Gairing; Rahul Savani . Vol. 9928 Springer VS, 2016. p. 64-76 (Lecture Notes in Computer Science, Vol. 9928).

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

Harvard

Hansen, KA, Ibsen-Jensen, R & Koucký, M 2016, The big match in small space. in M Gairing & R Savani (eds), Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings. vol. 9928, Springer VS, Lecture Notes in Computer Science, vol. 9928, pp. 64-76, 9th International Symposium on Algorithmic Game Theory, SAGT 2016, Liverpool, United Kingdom, 19/09/2016. https://doi.org/10.1007/978-3-662-53354-3_6

APA

Hansen, K. A., Ibsen-Jensen, R., & Koucký, M. (2016). The big match in small space. In M. Gairing, & R. Savani (Eds.), Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings (Vol. 9928, pp. 64-76). Springer VS. Lecture Notes in Computer Science, Vol.. 9928 https://doi.org/10.1007/978-3-662-53354-3_6

CBE

Hansen KA, Ibsen-Jensen R, Koucký M. 2016. The big match in small space. Gairing M, Savani R, editors. In Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings. Springer VS. pp. 64-76. (Lecture Notes in Computer Science, Vol. 9928). https://doi.org/10.1007/978-3-662-53354-3_6

MLA

Hansen, Kristoffer Arnsfelt, Rasmus Ibsen-Jensen and Michal Koucký "The big match in small space". and Gairing, Martin Savani , Rahul (editors). Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings. Springer VS. (Lecture Notes in Computer Science, Vol. 9928). 2016, 64-76. https://doi.org/10.1007/978-3-662-53354-3_6

Vancouver

Hansen KA, Ibsen-Jensen R, Koucký M. The big match in small space. In Gairing M, Savani R, editors, Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings. Vol. 9928. Springer VS. 2016. p. 64-76. (Lecture Notes in Computer Science, Vol. 9928). https://doi.org/10.1007/978-3-662-53354-3_6

Author

Hansen, Kristoffer Arnsfelt ; Ibsen-Jensen, Rasmus ; Koucký, Michal. / The big match in small space. Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings. editor / Martin Gairing ; Rahul Savani . Vol. 9928 Springer VS, 2016. pp. 64-76 (Lecture Notes in Computer Science, Vol. 9928).

Bibtex

@inproceedings{e835df2815dd41b0a72ba460cfbd13c9,
title = "The big match in small space",
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].",
author = "Hansen, {Kristoffer Arnsfelt} and Rasmus Ibsen-Jensen and Michal Kouck{\'y}",
year = "2016",
doi = "10.1007/978-3-662-53354-3_6",
language = "English",
isbn = "9783662533536",
volume = "9928",
pages = "64--76",
editor = "Gairing, {Martin } and {Savani }, { Rahul }",
booktitle = "Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings",
publisher = "Springer VS",

}

RIS

TY - GEN

T1 - The big match in small space

AU - Hansen, Kristoffer Arnsfelt

AU - Ibsen-Jensen, Rasmus

AU - Koucký, Michal

PY - 2016

Y1 - 2016

N2 - 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].

AB - 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].

UR - http://www.scopus.com/inward/record.url?scp=84987941886&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-53354-3_6

DO - 10.1007/978-3-662-53354-3_6

M3 - Article in proceedings

SN - 9783662533536

VL - 9928

SP - 64

EP - 76

BT - Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings

A2 - Gairing, Martin

A2 - Savani , Rahul

PB - Springer VS

ER -