Robust Online Selection Under Adversarial and Random Arrivals

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2334 papers468 conceptsfrozen 2026-10-04

In the world of online decision-making, the order in which information arrives is often more important than the information itself. Whether you are allocating cloud computing resources, matching mentors to students, or selecting the best candidate in a "secretary problem," you must make irrevocable decisions without knowing what the future holds.

The central tension in this research area is the gap between adversarial arrivals—where a malicious actor sequences items to exploit your algorithm's weaknesses—and random arrivals, where items appear in a shuffled, unpredictable, but non-malicious order.

The Adversarial Wall

When we assume an adversarial arrival order, we are designing for the absolute worst case. In this regime, many fair division and allocation problems become theoretically "impossible" to solve well. For example, in the "Santa Claus problem"—where the goal is to maximize the minimum value any agent receives—Max Springer and Mohammadtaghi Hajiaghayi show in Online Algorithms for the Santa Claus Problem that an adversary can force a competitive ratio as poor as $1/n$ (where $n$ is the number of agents).

The adversary’s primary weapon is the irrevocable decision. As Tzeh Yuan Neoh and Nicholas Teh demonstrate in Online Fair Division with Additional Information, an adversary can present a sequence of mediocre items that force an algorithm to exhaust its budget or "fairness capacity" early. When a high-value item finally arrives at the very end, the algorithm has no resources left to give, leading to a catastrophic violation of fairness or efficiency.

Breaking Barriers with Randomness

The outlook changes dramatically when we assume a random arrival order. In this model, the items are the same, but their sequence is a random permutation. This prevents the adversary from "clustering" high-value items or strategically timing them to exploit the algorithm's state.

A landmark result in this space is the "Prophet Secretary" problem. Traditional "Prophet Inequalities" (where values are known but the order is adversarial) have a performance ceiling of $0.5$. However, Hossein Esfandiari and MohammadTaghi Hajiaghayi proved in Prophet Secretary that by simply assuming a random arrival order, an algorithm can achieve a ratio of $1 - 1/e \approx 0.63$.

This "randomness bonus" appears across the field:

Designing for Robustness

The most recent frontier in this research is the development of Best-of-Many-Worlds algorithms. These are strategies that perform optimally if the world is random but remain robust if an adversary intervenes.

One approach is Independent Sampling. Jose Correa and Andrés Cristi explore this in The Secretary Problem with Independent Sampling, showing that observing even a small sample of items before the sequence begins allows an algorithm to set thresholds that are resistant to adversarial manipulation.

Another approach is the use of Online Contention Resolution Schemes (OCRSs). As Ola Svensson and Rico Zenklusen describe in Online Contention Resolution Schemes, these schemes provide a way to "round" fractional solutions into real-time decisions that are guaranteed to be competitive even against an "almighty" adversary who knows the future.

Finally, the PACE algorithm, analyzed by Zongjun Yang in Greedy-Based Online Fair Allocation with Adversarial Input, represents the current state-of-the-art in robustness. It proves that algorithms designed for stochastic (random) environments can, with the right greedy-threshold logic, maintain strong fairness and efficiency guarantees even when the input is entirely adversarial.

Why It Works: The Threshold Intuition

The reason these algorithms work—whether in random or adversarial settings—usually boils down to thresholding.

  1. In random settings, the algorithm uses the first portion of the sequence to "learn" the distribution of values and set a price or quality threshold.
  2. In adversarial settings, the algorithm must use more conservative, often randomized, thresholds. Bo Sun and Xiaoqi Tan show in Posted Price Mechanisms for Online Allocation with Diseconomies of Scale that by randomizing the threshold for each unit of resource, you can prevent an adversary from knowing exactly when you will "stop" or "buy," effectively neutralizing their ability to sequence items maliciously.

Papers in this version

Showing 60 of 334 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 286 papers
  2. Version 1 · 2026-10-04 · 334 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_adversarial_arrival_order_3155a606,
  title = {adversarial arrival order},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adversarial-arrival-order/rdr_3155a60609754f2bb51106136bf4b5bd},
  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_robust_online_selection_under_adversaria_3155a606_v1,
  title = {Robust Online Selection Under Adversarial and Random Arrivals},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/robust-online-selection-under-adversarial-and-random-arrivals/rdr_3155a60609754f2bb51106136bf4b5bd/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}