The Big Match in Small Space (Extended Abstract)

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10331490" target="_blank" >RIV/00216208:11320/16:10331490 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-662-53354-3_6" target="_blank" >http://dx.doi.org/10.1007/978-3-662-53354-3_6</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-662-53354-3_6" target="_blank" >10.1007/978-3-662-53354-3_6</a>

Jazyk výsledku

angličtina

Název v původním jazyce

The Big Match in Small Space (Extended Abstract)

Popis výsledku v původním jazyce

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 epsilon-optimal strategies. In this paper we design epsilon-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 epsilon-optimal value for Player 1 in the limit superior sense. The previously known strategies use space Omega(log T) and it was known that no strategy can use constant space if it is epsilon-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].

Název v anglickém jazyce

The Big Match in Small Space (Extended Abstract)

Popis výsledku anglicky

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 epsilon-optimal strategies. In this paper we design epsilon-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 epsilon-optimal value for Player 1 in the limit superior sense. The previously known strategies use space Omega(log T) and it was known that no strategy can use constant space if it is epsilon-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].

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2016

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

ALGORITHMIC GAME THEORY, SAGT 2016

ISBN

978-3-662-53354-3

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

13

Strana od-do

64-76

Název nakladatele

SPRINGER INT PUBLISHING AG

Místo vydání

CHAM

Místo konání akce

Liverpool

Datum konání akce

19. 9. 2016

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000389020400006