A New Approach to Drifting Games, Based on Asymptotically Optimal Potentials

This paper develops a fresh approach to the analysis of some drifting games. Our focus is on the identification of asymptotically optimal potential-based strategies for some versions of this repeated two-person game. Our approach involves (a) guessing an asymptotically optimal potential by solving an associated PDE (which is in general highly nonlinear); then (b) justifying the guess, by proving upper and lower bounds on the final-time loss whose difference scales like a negative power of the number of time steps. Our upper bounds are based on potential-based strategies for the player, and our lower bounds are similarly based on strategies for the adversary. Their proofs are rather elementary, using Taylor expansion and the explicit character of the potential. Most previous work on asymptotically optimal strategies has used potentials obtained by solving a discrete dynamic programming principle, which is complicated and sometimes intractable.