Single-Sample and Robust Online Resource Allocation

Rohan Ghuge, Sahil Singla, Yifan Wang

Abstract

Online Resource Allocation (ORA) is a fundamental challenge in computer science and economics, requiring providers to satisfy sequential requests under limited budgets. Traditional approaches typically rely on full distributional knowledge or identical arrival patterns. This paper introduces a novel Exponential Pricing algorithm that achieves a near-optimal $(1-\epsilon)$-approximation for ORA using only a single sample from each request distribution. The algorithm is uniquely robust, maintaining performance in the presence of adversarial outliers and "value augmentations" designed to trick the system into premature resource exhaustion.

Introduction

Online Resource Allocation powers critical infrastructure, from keyword ad auctions to cloud resource management. In these settings, a provider receives $n$ sequential requests and must decide whether to satisfy them using $m$ limited resource types. This creates a classic "explore-exploit" tradeoff: should a provider accept a current offer or reserve capacity for a potentially more valuable future request?

Existing state-of-the-art algorithms often rely on two restrictive assumptions: either full knowledge of the underlying distributions or the assumption that arrivals are Independent and Identically Distributed (I.I.D.). In practice, real-world distributions are often unknown, non-identical, and subject to adversarial noise. This research addresses these gaps by asking whether a near-optimal algorithm can be designed with minimal data (a single sample) while remaining resilient against adversarial manipulation.

The Exponential Pricing Mechanism

The core of the proposed solution is the Exponential Pricing algorithm. Unlike standard online learning approaches that maintain probability distributions over resources, this algorithm sets concrete, dynamic prices for each resource. The price of a resource $j$ at time $i$ is determined by the formula:

$$\lambda_{i,j} = \lambda^{INIT} \cdot \exp\left(\delta \cdot (\text{Actual Consumption} - \text{Expected Consumption})\right)$$

This rule ensures that if a resource is consumed faster than its expected rate, its price increases exponentially to prevent exhaustion. Conversely, if a resource is underutilized, the price remains low to encourage allocation. This mechanism allows the system to adapt in real-time to the actual flow of requests.

Learning from a Single Sample

A primary innovation of this work is the ability to operate effectively with only a single sample from each request distribution. To achieve this, the authors employ a Sample Partitioning technique. The algorithm takes the available samples and randomly partitions them into "mini-samples." By solving local versions of the resource allocation problem on these partitions, the algorithm can estimate the "Expected Consumption" required for the exponential pricing formula without needing a global view of the optimal solution.

Robustness and Adversarial Resilience

The algorithm was tested against two rigorous adversarial models:

  1. Byzantine Secretary Model: A fraction of the requests are adversarial outliers placed strategically to disrupt the allocation process.
  2. Value Augmentation: An adversary artificially inflates the value of specific requests to "bait" the algorithm into overspending its budget early in the sequence.

The research demonstrates that the Exponential Pricing algorithm is the first of its kind to be robust to both models simultaneously, resolving an open question in the field regarding the existence of a single pricing strategy that can handle both outliers and value-based attacks.

Key Theoretical Insights

  • Specialized No-Regret: While the exponential rule does not satisfy standard no-regret properties against all possible price vectors, the authors prove it satisfies a specialized no-regret property against the zero-price vector. This is sufficient to guarantee that the algorithm will not exhaust resources prematurely.
  • Error Tolerance: The algorithm is remarkably forgiving of estimation errors. The logarithmic nature of the exponential update ensures that even if initial price estimates or consumption expectations are off by polynomial factors, the impact on final welfare is negligible.
  • Incentive Compatibility: Because the algorithm utilizes "posted prices"—where the system sets a price and the user decides whether to accept—it is naturally truthful. Users have no incentive to misrepresent their valuations to the system.

Results and Conclusion

The Exponential Pricing algorithm achieves a $(1-\epsilon)$-approximation to the hindsight optimum for non-identical distributions, provided the resource budgets are sufficiently large (at least $\Omega(\text{poly}(1/\epsilon) \cdot \text{poly}(\log(nm)))$). This represents the first algorithm to achieve such welfare in a single-sample, non-identical setting.

While the algorithm requires large budgets to reach its $(1-\epsilon)$ guarantee—a limitation inherent to the problem's mathematical structure—it provides a robust and efficient framework for real-world resource management. Future work may extend these techniques to reusable resources, such as cloud VM rentals, or more complex combinatorial constraints.

Summary updated

BibTeX
@inproceedings{ghuge2025single,
  author = {Rohan Ghuge and Sahil Singla and Yifan Wang},
  title = {{Single-Sample and Robust Online Resource Allocation}},
  booktitle = {STOC},
  year = {2025},
  doi = {10.1145/3717823.3718246},
}
Figure