Four Discrepancies

Paul selects n vectors in n-space, all coordinates one or minus one. Carole is a balancer, assigning signs to each vector yielding a signed vector sum P. The value V, which Carole attempts to minimize, is the maximal absolute value of the coordinates of P.

We consider four variants of this problem. Paul may play randomly (then Carole minimizes the expectation of V) or adversarially. Carole may play On-Line, selecting each sign immediately upon seeing its vector; or Off-Line, waiting until Paul has given all the vectors before deciding on the signs.

All four variants are interesting and will be discussed. The order of V is known in all variants, though the constants remain elusive. We emphasize new results, with Nikhil Bansal, for the random on-line variant.