Optimal Restart Games: General Theory and Near-Optimal Strategies for Rivest's Coin Game

Abstract

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.