Vector Balancing Games with Aging

In this article we study an extension of the vector balancing game investigated by Spencer and Olson (which corresponds to the on-line version of the discrepancy problem for matrices). We assume that decisions in earlier rounds become less and less important as the game continues. For an aging parameter q ≥ 1 we define the current move to be q times more important than the previous one. We consider two variants of this problem: First, the objective is a balanced partition at the end of the game, and second, it is to ensure a balanced partition throughout the game. We concentrate on the case q ≥ 2. We give an optimal solution for the first problem and a nearly optimal one for the second.