Optimal Adaptive Strategies for Games of the Parrondo Type

Parrondo's paradox states that one can turn several losing strategies into a winning strategy by combining them in the right way. While there is in fact nothing paradoxical about this phenomenon, it gives rise to a number of algorithmic problems on Markovchains.We consider the problem of evaluating a strategy and the problem of finding an optimal one for three different types of strategies. Fixed strategies have to be specified completely before starting a sequence of games. Randomized strategies decide randomly in each step which game to play according to a specified probability distribution. Adaptive strategies make decisions on-line as the game proceeds. Different problems are obtained according to the considered time horizon: We are interested in both a finite sequence of games and in the asymptotic setting of an infinite sequence of games.Efficient algorithms exist for all six evaluation problems. However, only an optimal adaptive strategy for a finite game sequence can be found efficiently at this point; the remaining five optimization problems remain currently open