Vector balancing games with aging
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.
- A balancing strategy
- Balancing game with a buffer
- Balancing games
- Discrepancy of set-systems and matrices
- Geometric discrepancy. An illustrated guide
- scientific article; zbMATH DE number 4152425 (Why is no real title available?)
- scientific article; zbMATH DE number 863495 (Why is no real title available?)
- Integral approximation sequences
- Linear and hereditary discrepancy
- On a class of balancing games
- On some combinatorial questions in finite-dimensional spaces
- Randomization, derandomization and antirandomization: Three games
This page was built for publication: Vector balancing games with aging
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5947362)
