Barely Random Algorithms and Collective Metrical Task Systems

We consider metrical task systems on general metric spaces with n points, and show that any fully randomized algorithm can be turned into a randomized algorithm that uses only 2log n random bits, and achieves the same competitive ratio up to a factor 2. This provides the first order-optimal barely random algorithms for metrical task systems, i.e., which use a number of random bits that does not depend on the number of requests addressed to the system. We discuss implications on various aspects of online decision-making such as: distributed systems, advice complexity, and transaction costs, suggesting broad applicability. We put forward an equivalent view that we call collective metrical task systems where k agents in a metrical task system team up, and suffer the average cost paid by each agent. Our results imply that such a team can be O(log2 n)-competitive as soon as k≥ n2. In comparison, a single agent is always Omega(n)-competitive.