Abstract
This paper presents a theoretical extension of Yao’s Minimax Theorem specifically tailored for the analysis of robust algorithms and competitive ratios. By introducing the Ratio-of-Expectations (ROE) Minimax Lemma, the authors demonstrate that the mathematically complex Expectation-over-Ratios (EOR) can be replaced with a more tractable ROE objective without loss of generality in worst-case settings. This decoupling allows for the linearization of fractional optimization problems, facilitating the derivation of lower bounds in complex algorithmic environments where standard Minimax applications are algebraically prohibitive.
Introduction
In theoretical computer science, establishing the absolute limits of algorithmic performance—known as lower bounds—is essential for understanding problem complexity. A primary tool for this task is Yao’s Minimax Theorem, which frames the search for a lower bound as a zero-sum game between an algorithm designer and an adversary. By analyzing the performance of a deterministic algorithm against a worst-case distribution of inputs, researchers can infer the performance limits of any randomized algorithm.
However, a significant challenge arises when the performance metric is a ratio, such as the competitive ratio used in online analysis. In these scenarios, the standard Minimax framework requires calculating the Expectation-over-Ratios (EOR):
$$\mathbb{E} \left[ \frac{\text{Benchmark}(\omega)}{\text{Algorithm}(\omega)} \right]$$
Algebraically, EOR is difficult to manage because the numerator and denominator are coupled within the expectation. This coupling prevents researchers from analyzing the benchmark and the algorithm independently, often making tight lower bounds for complex problems nearly impossible to derive.
The Ratio-of-Expectations (ROE) Framework
The authors propose a new analytical tool to bypass this complexity: the Ratio-of-Expectations (ROE) Minimax Lemma. The core technical innovation is the Randomized-state Relaxation Lemma. In a worst-case minimization setting, the authors prove that one can relax the adversary’s constraints, allowing them to choose a distribution over states (rather than a single deterministic state) while simultaneously switching the objective from EOR to ROE:
$$\frac{\mathbb{E}[\text{Benchmark}(\omega)]}{\mathbb{E}[\text{Algorithm}(\omega)]}$$
By decoupling the numerator and denominator, the "Benchmark" becomes a fixed constant (the expected optimal value over a distribution), and the "Algorithm" component can be solved as a standard maximization problem. The paper demonstrates that this relaxation does not change the fundamental value of the optimization for the adversary, providing a valid and simpler path to lower bounds.
Key Theoretical Insights
Decoupling Complexity
The primary advantage of the ROE approach is the realization that researchers do not need to track how the ratio behaves in every individual state simultaneously. By moving to ROE, the analysis shifts to the aggregate performance of the benchmark versus the aggregate performance of the algorithm over a distribution of states.
The Power of the Adversary
Intuitively, allowing an adversary to use a mixture of states (randomization) might seem to increase their power. However, the paper shows that for ratio objectives in an inf-sup (worst-case) setting, a worst-case mixture is no more powerful than the single worst-case element within that mixture. This equivalence is what justifies the relaxation.
Linearization
ROE is significantly easier to manipulate because it allows for "multiplying through" by the denominator $\mathbb{E}[A(\cdot)]$. This transforms what was originally a fractional optimization problem into a linear one. Such problems are far more tractable using standard mathematical tools like linear programming.
Main Results
- Lemma 2 (The Main Result): The authors formally prove that the standard competitive ratio (the infimum-supremum of the ratio) is lower-bounded by the supremum-infimum of the Ratio-of-Expectations.
- Equivalence in "Weak" Settings: The authors demonstrate that in settings where the min-max value is well-defined (not requiring limits or infimums), the original ratio objective, the EOR objective, and the ROE objective all yield the exact same optimal value.
- Generalization: The result is shown to hold for general Hilbert spaces, indicating that the ROE Minimax Lemma is applicable to a wide range of continuous and discrete optimization problems beyond simple online algorithms.
Limitations and Scope
While the ROE Minimax Lemma is a powerful tool, it is subject to specific functional restrictions. To avoid division by zero, the authors require that there exists at least one design choice where the denominator is strictly positive for all states. Additionally, the current proof assumes non-negative costs, which is standard for competitive analysis but may require further extension for economic models involving negative costs or subsidies.
Conclusion
This work provides the mathematical machinery necessary to simplify the derivation of lower bounds in robust algorithm design. By proving the validity of the Ratio-of-Expectations as a proxy for the Expectation-over-Ratios, the authors offer a path to solving previously intractable lower bound problems through linearization and decoupling.
Summary updated