Randomized Cup Game Algorithms Against Strong Adversaries
Michael A. Bender, William Kuszmaul · Society for Industrial and Applied Mathematics eBooks · 2021
In each step of the cup game on n cups, a filler distributes up to 1 – ∊ water among the cups, and then an emptier removes 1 unit of water from a single cup. The emptier's goal is to minimize the height of the fullest cup, also known as the backlog. The cup emptying game has found extensive applications to processor scheduling, network-switch buffer management, quality of service guarantees, and data-structure deamortization. The greedy emptying algorithm (i.e., always remove from the fullest cup) is known to achieve backlog O(log n) and to be the optimal deterministic algorithm. Randomized algorithms can do significantly better, achieving backlog O (log log n) with high probability, as long as ∊ is not too small. In order to achieve these improvements, the known randomized algorithms require that the filler is an oblivious adversary, unaware of which cups the emptier chooses to empty out of at each step. Such randomized guarantees are known to be impossible against fully adaptive fillers. We show that, even when the filler is just “slightly” non-adaptive, randomized emptying algorithms can still guarantee a backlog of O (log log n). In particular, we give randomized randomized algorithms against an elevated adaptive filler, which is an adaptive filler that can see the precise fills of every cup containing more than 3 units of water, but not of the cups containing less than 3 units.