𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Vector Balancing Games with Aging

✍ Scribed by Benjamin Doerr

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
151 KB
Volume
95
Category
Article
ISSN
0097-3165

No coin nor oath required. For personal study only.

✦ Synopsis

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.

πŸ“œ SIMILAR VOLUMES

Vector Balancing Games with Aging
Vector Balancing Games with Aging
✍ Benjamin Doerr πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 176 KB
Games with vector payoffs
Games with vector payoffs
✍ H. W. Corley πŸ“‚ Article πŸ“… 1985 πŸ› Springer 🌐 English βš– 351 KB
Balancing Game with a Buffer
Balancing Game with a Buffer
✍ Hua Peng; Catherine Huafei Yan πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 145 KB

We consider a two person perfect information game with a buffer. On each n < < < < round, Player I selects a vector Β¨g ‫ޒ‬ with Β¨F 1, where ΠΈ is the l -norm, and 2 Player II can either put the vector in the buffer or choose a sign β‘€ s "1 for a i given vector Β¨. There are no more than d vectors that

Equilibrium points in games with vector
Equilibrium points in games with vector payoffs
✍ L. S. Shapley; Fred D. Rigby πŸ“‚ Article πŸ“… 1959 πŸ› John Wiley and Sons 🌐 English βš– 308 KB

## Abstract Historical. The topic of games with vector payoffs is one which could be expected to attract attention on the basis of its intrinsic interest. However, the history of the particular problem treated in Dr. Shapley's paper was not of this kind and m a y have some interest of its own. Duri