[{"intvolume":" 9928","status":"public","_id":"1340","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","alternative_title":[],"type":"conference","abstract":[{"lang":"eng"}],"page":"64 - 76","citation":{"chicago":"Hansen, Kristoffer, Rasmus Ibsen-Jensen, and Michal Koucký. “The Big Match in Small Space,” 9928:64–76. Springer, 2016. https://doi.org/10.1007/978-3-662-53354-3_6.","short":"K. Hansen, R. Ibsen-Jensen, M. Koucký, in:, Springer, 2016, pp. 64–76.","mla":"Hansen, Kristoffer, et al. The Big Match in Small Space. Vol. 9928, Springer, 2016, pp. 64–76, doi:10.1007/978-3-662-53354-3_6.","apa":"Hansen, K., Ibsen-Jensen, R., & Koucký, M. (2016). The big match in small space (Vol. 9928, pp. 64–76). Presented at the SAGT: Symposium on Algorithmic Game Theory, Liverpool, United Kingdom: Springer. https://doi.org/10.1007/978-3-662-53354-3_6","ieee":"K. Hansen, R. Ibsen-Jensen, and M. Koucký, “The big match in small space,” presented at the SAGT: Symposium on Algorithmic Game Theory, Liverpool, United Kingdom, 2016, vol. 9928, pp. 64–76.","ista":"Hansen K, Ibsen-Jensen R, Koucký M. 2016. The big match in small space. SAGT: Symposium on Algorithmic Game Theory, LNCS, vol. 9928, 64–76."},"date_published":"2016-09-01T00:00:00Z","dc":{"source":["Hansen K, Ibsen-Jensen R, Koucký M. The big match in small space. In: Vol 9928. Springer; 2016:64-76. doi:10.1007/978-3-662-53354-3_6"],"rights":["info:eu-repo/semantics/openAccess"],"title":["The big match in small space","LNCS"],"relation":["info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-662-53354-3_6","info:eu-repo/grantAgreement/FWF//S 11407_N23","info:eu-repo/grantAgreement/FWF//ICT15-003","info:eu-repo/grantAgreement/EC/FP7/279307"],"publisher":["Springer"],"date":["2016"],"language":["eng"],"type":["info:eu-repo/semantics/conferenceObject","doc-type:conferenceObject","text","http://purl.org/coar/resource_type/c_5794"],"identifier":["https://research-explorer.ista.ac.at/record/1340"],"description":["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]."],"creator":["Hansen, Kristoffer","Ibsen-Jensen, Rasmus","Koucký, Michal"]},"scopus_import":1,"uri_base":"https://research-explorer.ista.ac.at","day":"01","department":[{"_id":"KrCh","tree":[{"_id":"ResearchGroups"},{"_id":"IST"}]}],"publication_status":"published","volume":9928,"date_updated":"2021-01-12T06:50:00Z","dini_type":"doc-type:conferenceObject","date_created":"2018-12-11T11:51:28Z","author":[{"first_name":"Kristoffer","last_name":"Hansen"},{"orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87","last_name":"Ibsen-Jensen","first_name":"Rasmus"},{"last_name":"Koucký","first_name":"Michal"}],"creator":{"id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","login":"kschuh"},"ec_funded":1,"publist_id":"5927","project":[{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Rigorous Systems Engineering"},{"name":"Efficient Algorithms for Computer Aided Verification","_id":"25892FC0-B435-11E9-9278-68D0E5697425"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications"}],"quality_controlled":"1","oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1604.07634","open_access":"1"}],"language":[{}],"conference":{"location":"Liverpool, United Kingdom","start_date":"2016-09-19","end_date":"2016-09-21","name":"SAGT: Symposium on Algorithmic Game Theory"},"month":"09"}]