Abstract
We consider metrical task systems (MTS) on general metric spaces with $n$ points and demonstrate that any fully randomized algorithm can be transformed into a randomized algorithm using only $2\log n$ random bits while maintaining the same competitive ratio up to a factor of 2. This result provides the first order-optimal "barely random" algorithms for MTS—algorithms where the number of random bits is independent of the number of requests. We further introduce the concept of collective metrical task systems, where a team of $k$ agents suffers the average cost of its members. Our findings show that such a team can achieve $O(\log^2 n)$-competitiveness with $k \geq n^2$ agents, a significant improvement over the $\Omega(n)$ lower bound for a single deterministic agent. These results have broad implications for distributed systems, advice complexity, and transaction costs in online decision-making.
Introduction
Metrical Task Systems (MTS) serve as a fundamental framework for studying online decision-making under uncertainty. In an MTS, an agent moves within a metric space of $n$ points. At each discrete time step, a task arrives in the form of a cost vector, assigning a service cost to each point. The agent must decide whether to remain at its current location or move to a new one, incurring a movement cost proportional to the distance traveled.
The performance of MTS algorithms is measured by the competitive ratio—the ratio between the algorithm's total cost and the cost of an optimal offline adversary. Historically, a wide gap has existed between deterministic and randomized approaches:
- Deterministic algorithms are limited to a competitive ratio of $2n-1$.
- Randomized algorithms can achieve a significantly better ratio of $O(\log^2 n)$.
However, state-of-the-art randomized algorithms typically assume access to an infinite stream of random bits to maintain continuous probability distributions over the metric space. This paper investigates whether such an infinite supply is necessary, or if order-optimal performance can be achieved with a strictly limited amount of randomness.
Methodology
The Collective Viewpoint
The authors bridge the gap between randomness and determinism by establishing a mathematical equivalence between a "barely random" algorithm (using $b$ random bits) and a collective metrical task system consisting of $k = 2^b$ deterministic agents. In this collective model, the total cost is defined as the average cost incurred by the team. This perspective allows the problem of reducing randomness to be reframed as a discretization problem: how can a continuous probability distribution be represented by a finite set of $k$ points?
Discrete First-Order Tracking
To convert a continuous randomized strategy into a discrete one, the authors propose a tracking algorithm based on a proximal operator. The core challenge is to ensure that the discrete configuration of agents accurately follows the ideal continuous distribution without excessive movement.
The authors utilize a potential function $D(x, y)$ based on Optimal Transport (Wasserstein-1 distance) to manage this tracking. A key innovation is the introduction of a "hysteresis" effect. By preventing agents from reacting to infinitesimal shifts in the target distribution, the algorithm avoids "jittering," which would otherwise lead to prohibitive movement costs. To ensure agents can move optimally without needing to be split into fractional parts, the authors apply the Birkhoff-von Neumann Theorem to decompose the required movement into a set of valid permutations.
Key Results
The Conversion Theorem
The central theoretical contribution is a conversion theorem: any $\alpha$-competitive randomized MTS algorithm can be transformed into a $(1+\epsilon)\alpha$-competitive algorithm using $k \ge n^2/\epsilon$ agents. In terms of randomness, this implies that approximately $2 \log n$ bits are sufficient to achieve order-optimal performance.
Performance Bounds
- General Metric Spaces: The paper proves that for any $n$-point metric, there exists an $O(\log^2 n)$-competitive algorithm using only $\lceil 2 \log n \rceil$ random bits.
- Uniform Metric Spaces: In the specific case of uniform metrics (where all distances are equal), the requirement is even lower: $\lceil \log n \rceil$ bits are sufficient to achieve $O(\log n)$-competitiveness.
- Lower Bounds: The authors demonstrate that their upper bound is nearly tight, proving that any $O(\log^2 n)$-competitive algorithm must use at least $\log n - O(\log \log n)$ random bits.
Implications and Discussion
Advice Complexity and Distributed Systems
The results suggest that a very small amount of "advice" about the future—only $2 \log n$ bits total for the entire duration of the process—is enough to break the linear lower bound of deterministic algorithms. Furthermore, the collective model suggests that "intelligence" in multi-agent systems can effectively mimic the benefits of randomness, provided the agents can coordinate their positions.
Transaction Costs
The discretization approach makes MTS more robust to fixed transaction costs. Because the hysteresis mechanism prevents unnecessary movement, the algorithm is naturally suited for environments where every move incurs a baseline fee, a common scenario in financial modeling and asset management.
Conclusion and Future Work
This work establishes that $2 \log n$ random bits are the "magic number" for Metrical Task Systems, providing a bridge between the $O(1)$ bits of deterministic systems and the infinite bits of continuous randomized models. While $n^2$ agents are sufficient for general metrics, future research may investigate if $O(n)$ agents (or $\log n$ bits) suffice for specific metric classes, such as weighted stars. Additionally, exploring "distributed collective MTS," where agents have limited communication or act selfishly, remains a promising avenue for future study.
Summary updated