The Random Order Model for Online Resource Allocation

This direction is merged into another direction: adversarial arrival order. Its last version stays readable and citable here.

Version 1 of 127 papers32 conceptsfrozen 2026-10-04

In traditional online algorithms, we assume an "adversary" controls the sequence of inputs. This adversary knows our algorithm and presents items in the worst possible order to minimize our performance. While this provides robust guarantees, it is often overly pessimistic. In many real-world scenarios—from ad auctions to cloud scheduling—items don't arrive in a malicious sequence; they arrive in a way that is effectively random.

The Random-Order Model (ROM) bridges the gap between worst-case adversarial analysis and purely stochastic models. By assuming that the input set is fixed but its arrival order is a uniform random permutation, researchers have found they can break through long-standing theoretical "barriers" that were previously thought to be insurmountable.

The Power of the Representative Sample

The core intuition behind the Random-Order Model is the representative sample. If $n$ items arrive in a random order, the first small fraction of those items (say, the first 10%) likely contains a proportional distribution of high-value and low-value items.

In A Dynamic Near-Optimal Algorithm for Online Linear Programming, Shipra Agrawal and Yinyu Ye demonstrate how to use this sample to solve the "threshold price" problem. In online linear programming, you must decide whether to accept a request (like an ad bid) without knowing future bids. By observing the first few arrivals, the algorithm learns a "dual price" for resources. If a future bid exceeds this learned price, it is accepted. Because the order is random, the prices learned from the beginning of the sequence remain valid for the end, allowing the algorithm to achieve a performance nearly identical to the optimal offline solution.

Breaking the One-Half Barrier

For decades, many online problems were stuck at a competitive ratio of $1/2$ (or 0.5). This means that in the worst case, an online algorithm could only guarantee half the value of an offline algorithm that sees everything in advance.

The Random-Order Model shatters this limit. In the context of Submodular Welfare Maximization—where the goal is to allocate items to agents with diminishing returns—Nitish Korula and Vahab Mirrokni proved in Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order that a simple greedy algorithm achieves a ratio of at least $0.5052$. While the numerical improvement seems small, it represents a fundamental shift: it proves that the $1/2$ limit is a product of adversarial ordering, not the sequential nature of the problem itself. Later work by Niv Buchbinder and Mohit Garg further simplified this result, pushing the bound to $0.5096$ using symmetry and expectation rather than complex linear programming (Online Submodular Maximization: Beating 1/2 Made Simple).

Secretaries and Prophets

The Random-Order Model also resolves tensions between two classic stopping problems: the Secretary Problem (where you know nothing about values but arrivals are random) and the Prophet Inequality (where you know the distributions of values but arrivals are adversarial).

In Prophet Secretary, Hossein Esfandiari and MohammadTaghi Hajiaghayi combined these settings. They showed that when you have both distributional knowledge and a random arrival order, you can achieve a competitive ratio of $1 - 1/e \approx 0.63$. This suggests that temporal randomness acts as a buffer, preventing an adversary from "hiding" the best items at the very end of a sequence to force a premature commitment.

Fairness through Randomness

Random arrival orders are particularly transformative for fair division. In the "Santa Claus problem," the goal is to distribute items so that the least-fortunate person is as well-off as possible. Under adversarial arrivals, this is nearly impossible because the adversary can starve specific agents.

However, Max Springer and Debmalya Panigrahi show in Online Algorithms for the Santa Claus Problem that a random order allows for a $1-\epsilon$ competitive ratio. The intuition is that in a random sequence, the resources needed by different agents are likely to be interleaved. No single agent is forced to wait too long for a compatible item, allowing the algorithm to maintain balance throughout the process.

Beyond Simple Selection

The benefits of the Random-Order Model extend to complex combinatorial problems:

By shifting the focus from "what is the worst that can happen?" to "what happens on average?", the Random-Order Model provides a more realistic and optimistic framework for designing the algorithms that power modern digital marketplaces and resource schedulers.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_the_random_order_model_for_online_resour_4e2a2870,
  title = {The Random Order Model for Online Resource Allocation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-random-order-model-for-online-resource-allocation/rdr_4e2a287029614229ac4f094022cf4be5},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_the_random_order_model_for_online_resour_4e2a2870_v1,
  title = {The Random Order Model for Online Resource Allocation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-random-order-model-for-online-resource-allocation/rdr_4e2a287029614229ac4f094022cf4be5/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}