Optimal Restart Games: General Theory and Near-Optimal Strategies for Rivest's Coin Game
Ladda ner
Typ
Examensarbete för masterexamen
Program
Complex adaptive systems (MPCAS), MSc
Publicerad
2019
Författare
Älgmyr, Anton
Martinsson, Björn
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
The purpose of this thesis was to analyze the Rivest coin game. To do this we formally introduced a type of game which we call restart games and built a theoretical framework for analysis of such games. Most of this theory was derived by connecting restart games to quitting games (optimal stopping problems) with ideas based on the paper “On Playing Golf With Two Balls”.
Through this framework we have developed two strategies for playing the Rivest coin game which we have shown to be constant-factor from optimal. These strategies seem to generalize well to other similar games, in particular we have shown them to be constant-factor from optimal in another related coin game.
The theoretical framework also provided means to analyze the Rivest coin game numerically and even construct an optimal strategy for any particular instance of the game. The constructed optimal strategy, along with some other simple strategies, was analyzed and reaffirms the optimality analysis while also highlighting some important differences between our strategies and an optimal strategy.
Beskrivning
Ämne/nyckelord
Rivest coin game, restart game, quitting game, optimal stopping, Markov decision process, dynamic programming, complexity analysis, speedrun