Cumulative Subtraction Games

Abstract

We study a variation of Nim-type subtraction games, called Cumulative Subtraction (CS). Two players alternate in removing pebbles out of a joint pile, and their actions add or remove points to a common score. We prove that the zero-sum outcome in optimal play of a CS with a finite number of possible actions is eventually periodic, with period $2s$, where $s$ is the size of the largest available action. This settles a conjecture by Stewart in his Ph.D. thesis (2011). Specifically, we find a quadratic bound, in the size of $s$, on when the outcome function must have become periodic. In case of exactly two possible actions, we give an explicit description of optimal play.