Skip to content
Preprint

Single-or-Sample: Online Fair Allocation for Combinatorial Agents

Sep 2026 · 1 citation · 78 references
Computer Science

TL;DR

A new randomized online algorithm for additive and submodular valuations, called Single-or-Sample, is developed, that achieves a constant-factor approximation to MMS simultaneously for all agents, with constant probability, and establishes a fundamental tradeoff between approximation and success probability.

Abstract

We study the fair allocation of $m$ indivisible goods among $n$ heterogeneous agents arriving online, under maximin share (MMS) fairness. The key challenge lies in making allocation decisions in an adversarial setting without knowing future agents'valuations. No guarantees were known prior to our work in adversarial settings. Our main positive result is an online allocation algorithm for submodular agents that with probability at least $0.4$ guarantees a $1/24$-approximation to MMS to all agents simultaneously. Our algorithm intersperses a greedy-style adaptive sampling-without-replacement protocol with single-good reduction rounds. For XOS valuations, we adapt this single-or-sample approach to guarantee a $c$-MMS for all agents simultaneously with probability $1-O(c)$ for any parameter $c\in O(1/\log n)$. A key technical contribution of our work is in establishing Chernoff-style tail bounds on item allocation events for this adaptive sampling process despite strong positive correlations among the items, a result that may be of independent interest. The approximation versus success probability tradeoffs achieved by our algorithms are asymptotically tight. We show that even for binary additive valuations, no randomized algorithm can ensure $c$-MMS to all agents with probability exceeding $(1-c^2/5)$, for any $c\in (0,1]$. For XOS valuations, stronger lower bounds hold: no randomized algorithm can ensure $c$-MMS to all agents with probability exceeding $(1-c/3)$, for any $c\in (0,1]$. Furthermore, no algorithm can achieve $\omega(1/\log \log n)$-MMS with any constant probability. All our lower bounds hold even for simple binary instances whose MMS values and MMS partitions can be computed in linear time.

View source

Similar papers

Preprint Sep 2026

Online Fair Division: Pushing the Frontier of Approximate Proportionality

Online fair division captures allocation problems in which indivisible resources arrive over time and must be assigned before future resources are known. Understanding what fairness remains achievable when allocation decisions are immediate and irrevocable is a fundamental question in this setting. We study determinist...

Ying-Jian Du, An-Kang Sun · 4 citations · ⚡1
Preprint Sep 2026

Randomized Online Fair Division: High-Probability and Expected Realized Fairness

We study randomized algorithms for the fully online allocation of indivisible goods among $n\ge2$ agents with nonnegative additive valuations. Goods arrive sequentially and must be allocated immediately and irrevocably, with only $n$ known in advance. Since exact ex-ante envy freeness and proportionality are readily ac...

Tian-Qi Chen, Jing Long · 3 citations
Preprint Oct 2026

Randomized Algorithm for MMS Allocation of Chores with Online Agent Arrivals

We study the fair allocation of $m$ indivisible chores among $n$ agents in the agent-arrival model against an oblivious adversary. The chore set and the number of agents are known in advance. When agent $i$ arrives, her nonnegative additive cost function $c_i$ is revealed, and the algorithm must immediately and irrevoc...

Hao-Long Li, Fang-Xiao Wang, Xiao-Wei Wu · 0 citations
Preprint Sep 2026

Online Fair Division under an Oblivious Adversary

We study online fair division, where indivisible goods arrive one at a time and must be allocated immediately and irrevocably among $n\ge2$ agents. Against an oblivious adversary that fixes the input in advance, we ask what fairness guarantees randomized online algorithms can achieve. We present the Deficit Allocation...

Saar Cohen, Nicholas J. Teh, Michael Wooldridge · 3 citations
Review Sep 2026

Online Allocation using Few Samples

We study online allocation problems where $n$ requests over $m$ resources arrive in an adversarial order and must be served immediately and irrevocably. This framework captures both Online Resource Allocation, where the goal is to maximize value subject to resource budgets, and Online Load Balancing, where the goal is...

Matthew Faw, Sahil Singla, Yi-Fan Wang · 0 citations
Preprint Sep 2026

Closing Gaps in Online Fair Division

This work determines the tight high-probability PROP1 guarantee of the classical Like rule, which assigns each good uniformly among the agents who value it positively, and improves when fewer agents value the same good, unlike uniform random allocation.

Tzeh Yuan Neoh, Nicholas J. Teh · 9 citations · ⚡2

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.