Vector balancing games with aging (Q5947362): Difference between revisions

A vector balancing problem consists of a finite set \(X\) of vectors to be partitioned into two classes \(X_1\) and \(X_2\) such that \(\|\sum_{x\in X_1}x - \sum_{x\in X_2}x\|\) is as small as possible in some suitable norm \(\|\cdot\|\). The problem is translated into a game where the first player, called the pusher, selects a vector \(x\) from \(X\) and the second player, called the chooser, chooses a sign \(\epsilon\in\{-1,1\}\), and the position vector \(p\), initially set to zero, is changed to \(p+\epsilon x\). The pusher's goal is to maximize \(\|p\|\), while the chooser tries to minimize it. A variant of the game is to allow a buffer of some size where the chooser can store some vectors and thus postpone the sign-choosing decision. Among vector balancing games previously solved are the discrete game, where \(X\) is finite, and the game on the unit ball with Euclidean norm. Some results on games with a buffer have been obtained as well. The present author restricts attention to the maximum norm \(\|\cdot\|_{\infty}\) unit ball game, and assumes a decision made in an earlier round of the game is less important than the current one. This is accomplished by the use of an ``aging'' parameter \(q>1\) and by modifying the update rule to \(p:={1\over q}p+\epsilon x\). The cases \(1<q<2\) and \(q\geq 2\) are quite different, and attention is restricted to \(q\geq 2\). Moreover, two versions are distinguished: In the fixed end version, the value of \(\|p\|\) after the last round is the pusher's payoff, whereas in the continuous version it is the maximum value of \(\|p\|\) in the course of the game. In the fixed end version the game value is found if sufficiently many rounds are played, and for the continuous version, lower bounds for the pusher's payoff and upper bounds for the chooser's are obtained.