CS Paper Radar

Online Fair Division under an Oblivious Adversary

Saar Cohen, Nicholas Teh, Michael Wooldridge

cs.GT ·submitted 2026-09-23 16:11 UTC · v2
benchmarkhighly cited

Abstract

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 (DA) algorithm, which improves the previously known high-probability approximation to PROP1 from inverse-logarithmic to inverse-doubly-logarithmic in $n/δ$, where $δ$ is the failure probability. DA does not require $δ$ as input. With probability at least $1-δ$, a refined variant achieves an arbitrarily close approximation to proportionality when no single item is too valuable relative to an agent's proportional share; without any restriction on item values, it obtains an arbitrarily close approximation to PROP$k$ for $k$ doubly logarithmic in $n/δ$. For $n2^{-2n}\leδ\le1/2$, our bounds on the approximation factor and $k$ are asymptotically tight for the stronger fractional benchmark that divides each item equally among the agents who value it positively. We also prove that algorithms that use only which agents value each item positively, but not by how much, cannot improve upon the logarithmic dependence of uniformly random allocation. However, other fairness notions admit weaker guarantees. For EF1, every randomized online algorithm has an input on which any positive approximation succeeds with probability at most $e^{-Ω(n)}$. For EFX, this probability is at most $1/n!$ with only $n+1$ items, tight within a factor of $(n+1)/2$; for MMS, it can be at most $5/6$. Finally, allocating each item uniformly among the agents who value it positively gives, with probability at least $1-δ$, an arbitrarily close approximation to EF$k$ for $k$ logarithmic in $n/δ$, and this dependence is necessary for this rule.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.GT ·2026-09-20 ·Tianqi Chen, Jingxiao Long
similarity 0.82
Abstract · 22 pages. Improved high-probability and expected realized PROP1 guarantees; revised proofs and exposition

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 achievable, while no positive ex-post approximation is possible for the fairness notions considered here, we study the intermediate notions of high-probability fairness and expected realized fairness. Against a non-adaptive adversary, we give a randomized algorithm for proportionality up to one good (PROP1) whose parameter depends only on $n$ and that preserves exact ex-ante envy-freeness and proportionality. At confidence $1-δ$, its PROP1 guarantee improves on independent uniform allocation (Rand) by a factor of $Ω(\log n)$, uniformly over $δ\in(0,1/2]$. As $n\to\infty$, its expected realized PROP1 factor is at least $\frac{3-\sqrt5}{2}-o(1)$. We also show that the expected realized PROP1 factor of Rand is $(1+o(1))/\log n$, yielding an improvement of at least $\bigl(\frac{3-\sqrt5}{2}-o(1)\bigr)\log n$ for our algorithm. For every randomized online algorithm and every positive approximation factor, the success probability can be made arbitrarily small for envy freeness up to any good (EFX) and at most $\frac{n+1}{2n}$ for envy freeness up to one good (EF1). Consequently, every randomized fully online algorithm has an expected realized EFX guarantee of zero and an expected realized EF1 guarantee of at most $\frac{n+1}{2n}$.

0.43

Closing Gaps in Online Fair Division

cs.GT ·2026-09-04 ·Tzeh Yuan Neoh, Nicholas Teh
theoryhighly cited similarity 0.81
Abstract

We study the online fair division of indivisible items, where items arrive one at a time and must be allocated immediately and irrevocably. We address three central open questions in the literature. First, we show that for every $n\ge 2$ agents, every fixed $k\ge 1$, and every $α\in(0,1]$, no online algorithm can guarantee $α$-PROP$k$ against an adaptive adversary. This remains true even when the total number of goods is known in advance, all values lie in $[0,1]$, and every good is positively valued by at most two agents. The impossibility extends to a broad range of standard envy-based, proportionality-based, and share-based fairness notions. We also establish an analogous impossibility for chores. Second, in the setting with predictions, a lightweight form of future information, the maximum item value, was previously known to guarantee only $1/n$-PROP1, leaving open whether the dependence on $n$ is necessary. We give a deterministic $19/30$-PROP1 algorithm against adaptive adversaries that does not require knowing the total number of goods. Given an additional upper bound $κ\in[2,n]$ on the number of agents who value any good positively, the guarantee improves to $\max \{ 19/30, n/(n+κ) \}$. The guarantee remains a positive constant under any fixed one-sided prediction error below one. When predictions are exact and the total number of goods $m\ge n\log n$ is known in advance, a deterministic algorithm achieves the same $19/30$-PROP1 factor together with $O(\sqrt{m\log n/n})$ maximum additive envy after normalizing each agent's values by their maximum item value. Third, against a non-adaptive adversary, we determine the tight high-probability PROP1 guarantee of the classical Like rule, which assigns each good uniformly among the agents who value it positively. Its guarantee improves when fewer agents value the same good, unlike uniform random allocation.

0.43

Online Fair Division: Pushing the Frontier of Approximate Proportionality

cs.GT ·2026-09-12 ·Yingjian Du, Ankang Sun
theoryhighly cited similarity 0.80
Abstract · In this updated version, we add a discussion of an independent work that studies related results. We also add a new section that presents a …

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 deterministic online allocation among $n$ agents with nonnegative additive valuations, where the number of goods is unknown and the adversary can adapt to previous allocation decisions. We focus on proportionality up to one good (PROP1) and examine how advance information affects the achievable guarantees. Without additional future information, we give a deterministic algorithm that guarantees $Ω(\frac{1}{\log(nm)})$-PROP1 after every round, where $m$ is the number of goods at termination. We complement this result by showing that, for every $n$ and sufficiently large $m$, every deterministic algorithm has an adaptive instance with $m$ goods on which its allocation has PROP1 approximation guarantee $O(\frac{\log \log m}{\log m})$. Thus, when the number of agents is fixed, our upper and lower bounds on the competitive ratio differ by at most an $O(\log\log m)$ factor. These results answer an open question proposed by Choo et al. on whether a nontrivial deterministic approximation for PROP1 can be obtained. We also study the setting where the algorithm knows the predictions of the maximum item value for every agent. When the predictions are accurate, we give a deterministic $\frac{1}{2}$-PROP1 algorithm, improving the $\frac{1}{n}$ guarantee of Choo et al. to a constant. We further establish an explicit upper bound below one on the competitive ratio, even for two agents with accurate predictions. Finally, we give a single deterministic algorithm that guarantees $\frac{1}{2}$-PROP1 when predictions are accurate and $Ω(\frac{1}{\log (nm)})$-PROP1 for arbitrary predictions.

0.40

Randomized Algorithm for MMS Allocation of Chores with Online Agent Arrivals

cs.GT ·2026-10-11 ·Haolong Li, Fangxiao Wang, Xiaowei Wu
similarity 0.75
Abstract

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 irrevocably assign her a subset of the unallocated chores. We focus on the notion of maximin share (MMS) and measure the fairness of the realized allocation $X$ by the ex-post MMS approximation ratio $ρ(X)$. We measure an algorithm's performance by its expected ratio, and also the guarantees that hold with high probability. For binary additive costs, we achieve an expected ex-post MMS ratio of $3/2+o(1)$, and show that every randomized online algorithm has an expected ratio of at least $3/2-o(1)$. For every $n$, the expected ratio is at most $1.755$. A variant of our algorithm guarantees an approximation ratio of $2$ with high probability, which is optimal. % For general additive costs, we present a weighted-rounding algorithm that achieves an expected ratio of $2+o(1)$, which also holds with high probability. The expected ratio is at most $2.594$ for every $n$. We also show that similar algorithms extend to additive goods, achieving a constant expected ex-post MMS ratio and guaranteeing every agent an $x$-fraction of her MMS with probability at least $1-85x^2$ for every $x\le1/15$.

0.39

Improved Impossibility Bounds for Maximin Share Allocations

cs.GT ·2026-09-14 ·Tomer Ezra, Tamar Garbuz
benchmarkhighly cited similarity 0.73
Abstract

The maximin share (MMS) is a central fairness benchmark for allocating indivisible items, but it need not be simultaneously attainable even under additive preferences. While extensive work has developed approximation guarantees, quantitative impossibility bounds have received comparatively little attention. We establish improved asymptotic and constant impossibility bounds for both goods and chores. For every sufficiently large number $n$ of agents, we construct additive goods instances in which every allocation gives some agent at most a $1-Ω((\log n)^{-2})$ fraction of her MMS. This strengthens the $1/n^4$ shortfall of Feige, Sapir, and Tauber (2021) to an inverse-polylogarithmic shortfall. For chores, we construct instances in which every allocation gives some agent cost at least a $1+Ω((\log n)^{-2})$ factor of her MMS. Consequently, for every fixed $\varepsilon>0$, guarantees of $1-O(n^{-\varepsilon})$ for goods and $1+O(n^{-\varepsilon})$ for chores are impossible. Both asymptotic constructions use $n+O(\log n)$ items. Together with concurrent existence results of Feige (2026), this determines the threshold $n+Θ(\log n)$ for guaranteed MMS existence under additive preferences, for both goods and chores. We also give four-agent, eleven-item instances that improve the universal impossibility bounds from $39/40$ to $20/21$ for goods and from $44/43$ to $31/30$ for chores.

0.40

Online Fair Division with Frequency Predictions

cs.GT cs.MA ·2026-10-25 ·Tzeh Yuan Neoh, Nicholas Teh
similarity 0.71
Abstract

We study online fair division of indivisible goods among $n$ agents with frequency predictions: before any good arrives, the algorithm learns the multiset of each agent's values for the goods, but neither the arrival order nor which values of different agents belong to the same good. Neoh et al. (ICML 2026) showed that such predictions allow every share-based guarantee that is achievable offline, and left open whether a positive approximation of envy-freeness up to one good (EF1) is possible. We show that deterministic online algorithms can guarantee $1/2$-EF1 for three agents and $(3-\sqrt5)/2$-EF1 for four agents, whereas for five or more agents, no online algorithm can guarantee any positive approximation of EF1, even with $n+1$ goods and identical predictions. Together with the known result for two agents, a positive approximation of EF1 is therefore possible if and only if $n\leq4$. We also rule out any positive approximation of EFX for three or more agents, even when the valuations take only two distinct positive values. Next, we use the meta-algorithm of Neoh et al. (ICML 2026) to compute an epistemic EFX (EEFX) allocation in polynomial time for any $n$, and hence a $1/(n-1)$-EF$(n-2)$ allocation for $n\geq3$, whereas algorithms that fix a picking sequence in advance can guarantee a positive approximation of EF$k$ if and only if $n\leq k+2$. Finally, for noisy predictions, we give algorithms that return EEFX allocations when the predictions are exact, and guarantee $(1-2\varepsilon+O(\varepsilon^2))$-EEFX under underestimates and, for $n\geq3$, $(1-2(n-1)\varepsilon+O(\varepsilon^2))$-EEFX under overestimates; the linear terms are the best possible, and larger overestimates rule out any positive approximation for such algorithms.

0.28

Online Fair Division with Upgrade Recourse

cs.GT ·2026-10-12 ·Yichen Huang, Nicholas Teh
highly cited similarity 0.70
Abstract

We study the online fair division of indivisible goods. In the standard model, where assignments are irrevocable, no algorithm can guarantee any positive fraction of the maximin share (MMS). Reassigning earlier goods can restore fairness, but it may take value away from agents who already hold them. We ask how much fairness can be maintained if every reassignment must leave each affected agent at least as well off. We consider two forms of such upgrade recourse. Under item-level upgrades, each good an agent holds must be kept or replaced by a distinct good she values at least as much; under bundle-level upgrades, only her total value must not decrease. For item-level upgrades, we show that the optimal MMS factor is essentially $1/H_n \approx 1/\ln n$, where $H_n$ is the $n$-th harmonic number, and that fixed picking sequences nearly attain it. Since these sequences use only the agents' rankings of individual goods, knowing the actual values cannot improve the optimal factor for up to 33 agents, and improves it by at most a vanishing margin as $n$ grows. Bundle-level upgrades allow substantially stronger guarantees. By permitting several-for-one exchanges, they turn this vanishing factor into a constant: we achieve exact MMS for two agents and more than half of MMS for any number of agents, in both cases together with relaxations of envy-freeness. Finally, we show that predictions about future goods let online algorithms inherit any offline MMS guarantee, losing only an additive term bounded by the prediction error. Under item-level upgrades, however, insisting on exact MMS when predictions are correct leaves no positive guarantee when they are wrong.

0.33

Online Fair Division under Eligibility Constraints

cs.GT ·2026-10-06 ·Joes Biburger, Nicole Megow, Golnoosh Shahkarami
theory similarity 0.70
Abstract

We study fair division of indivisible items under eligibility constraints: each item may be assigned only to a subset of eligible agents. This model coincides with restricted assignment in scheduling, with agents as machines and items as jobs, and captures settings where work or resources must be split among parties with different capabilities. Eligibility makes the usual fairness benchmarks inadequate, as agents should not be measured against items they could never receive. We therefore use eligibility-aware versions of proportionality and envy-freeness, where an agent's proportional share splits each item equally among its eligible agents, and envy comparisons discount items the agents are not eligible for. Our main finding is a sharp chore--goods separation for proportionality. We focus on identical valuations: under arbitrary valuations, no online algorithm can guarantee even an $o(m)$-approximation for chores. For chores, Prop1 is achievable offline, whereas exact proportionality and proportionality up to any item are not. For online chores, the optimal approximation factor for Prop1 for deterministic algorithms is $Θ(\sqrt m)$, with the lower bound holding even for unit-size jobs. For goods, Prop1 is again achievable offline, but the tight online bound drops to $Θ(\log m)$. For envy-based fairness, the picture is different. Goods and chores are equivalent under eligibility-aware envy notions, while the choice of notion is decisive. Strong EF1 may fail to exist even offline and cannot be approximated online. In contrast, weak EF1 can be maintained online, while weak EFX separates offline from online. Together, these results give a systematic study of online proportional and envy-based fairness in restricted assignment and show which fairness guarantees remain achievable under eligibility constraints.

0.35