PaperlayerView exact revision on arXiv

Source-linked AI summary

Closing Gaps in Online Fair Division

Tzeh Yuan Neoh, Nicholas Teh

arXiv:2609.05310v1cs.GT

TL;DR

The paper asks whether online fair division's standard irrevocable-allocation model prevents meaningful fairness guarantees, and addresses this through impossibility results, prediction-based algorithms, and randomized analysis. It proves broad adaptive-adversary impossibilities, improves prediction-based PROP1 guarantees, and characterizes Like's non-adaptive guarantee.

  • Problem

    Online allocation makes ex post fairness difficult because indivisible goods arrive sequentially and must be allocated immediately without knowing the future, raising whether positive PROP1 approximations are possible.

  • Method

    The paper combines impossibility reductions and adversarial constructions with reciprocal-PROP1 and exponential pairwise-envy potentials, plus probabilistic analysis of the Like rule.

  • Results

    The paper proves no positive PROPk factor for goods against adaptive adversaries, improves prediction-based guarantees to 1/2-PROP1 and n/(n + κ), and establishes a tight Θ(min{1, n/(κ log(n/δ))}) guarantee for Like against non-adaptive adversaries.

  • Takeaways & Limitations

    Predictability enables online proportionality: maximum-item-value predictions support constant guarantees, while non-adaptive adversaries enable concentration; without either, adaptive adversaries rule out positive goods guarantees.

  • Takeaways & Limitations

    The paper leaves open the optimal PROP1 factor with exact maximum-item-value predictions, combining 1/2-PROP1 with its envy bound, and improving Rand's worst-case factor on unrestricted instances.

Abstract

from arXiv · show

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 no online algorithm can guarantee any positive multiplicative approximation to proportionality up to any $k$ goods (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. This impossibility extends to a broad range of standard envy-based, proportionality-based, and share-based notions currently studied in the literature. We also establish the analogous impossibility for chores. Second, in the setting with predictions, a lightweight prediction of the maximum item value was previously known to give $1/n$-PROP1, leaving open whether the dependence on $n$ is necessary. We give a deterministic $1/2$-PROP1 algorithm against adaptive adversaries. More generally, if the algorithm is given an upper bound $κ\in[2,n]$ on the number of agents who value any good positively, the guarantee improves to $n/(n+κ)$ and remains constant under one-sided prediction error. When the total number of goods ($m$) is known in advance and $m\ge n\log n$, we further give, for every fixed $β\in(0,1/2)$, a deterministic algorithm that simultaneously guarantees $β$-PROP1 and $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. Unlike uniform random allocation, its guarantee improves when fewer agents value the same good.

1 Introduction

The paper studies whether meaningful fairness guarantees are possible under irrevocable online allocation and answers three open questions about impossibility, predictions, and randomized rules.

  • Motivation: Online allocation must make immediate, irrevocable decisions while seeking final guarantees such as EF1, PROP1, and MMS.These guarantees can be achievable offline but become difficult or impossible to approximate online.
  • Impossibility: The paper proves that no positive approximation to PROPk is possible against adaptive adversaries, even with a known horizon, values in [0,1], and at most two positive-valuing agents per good.The impossibility extends to randomized algorithms, chores, and many standard envy-, proportionality-, and share-based notions.
  • Predictions: Maximum item value predictions improve the prior 1/n-PROP1 guarantee to deterministic 1/2-PROP1 and to n/(n+κ)-PROP1 when at most κ agents value each good positively.The guarantee remains positive under one-sided prediction error.
  • Predictions: When the horizon is known and T ≥ n log n, a deterministic algorithm simultaneously guarantees β-PROP1 and O(sqrt(T log n/n)) normalized maximum additive envy.This holds for every fixed β in (0,1/2).
  • Randomized rules: Against a non-adaptive adversary, Like has a tight Θ(min{1,n/(κ log(n/δ))}) PROP1 guarantee, while Rand remains Θ(1/log(n/δ)) even when each good has one positive-valuing agent.Restricting assignment to positive-valuing agents improves proportionality by about n/κ but increases envy-relevant variance.

2 Preliminaries

The preliminaries define the online allocation model, additive valuations, PROPk, maximum item value predictions, and the parameter κ controlling how many agents value a good positively.

  • Model: There are n agents and a finite sequence of m indivisible goods arriving in order, with nonnegative additive valuations.The horizon m need not be known unless explicitly assumed.
  • Parameters: κ is the maximum number of agents who value any single good positively.Formally, κ := max_g |N(g)|, where N(g) contains agents with positive value for g.
  • Fairness notions: An allocation is α-PROPk if each agent can add at most k unallocated goods to reach α times their proportional total value.For k=1, the condition is equivalent to the agent’s bundle value plus their best outside good reaching the target.
  • Online process: Goods arrive sequentially, must be assigned immediately and exactly once, and earlier assignments cannot be changed; fairness is evaluated on the final allocation.Adaptive adversaries may choose future valuation vectors after observing prior realized recipients.
  • Predictions: An exact maximum item value prediction gives each agent one number equal to their highest item value and reveals neither total value nor future order.With one-sided error ε, each prediction is an upper bound within factor 1/(1−ε) of the true maximum.

3 Inapproximability of PROPk in the Fully Online Setting

The fully online model cannot guarantee any positive PROPk approximation against adaptive adversaries, and the result persists under bounded values, known horizons, sparse positive valuations, and randomization.

  • Main theorem: No deterministic online algorithm guarantees α-PROPk for any α>0 against an adaptive adversary.The theorem holds for every n≥2 and k≥1.
  • Main theorem: The impossibility remains when the final number of goods is known, every value lies in [0,1], and each good is positively valued by at most two agents.A finite-history argument establishes a common horizon bound, and scaling preserves the allocation inequalities.
  • Proof strategy: The proof reduces PROPk to PROP1, reduces n agents to two agents, and constructs an adaptive two-agent strategy that defeats every recipient sequence.The two-agent strategy controls normalized PROP1 slacks until a final shared good creates a violation.
  • Proof strategy: The two-agent adversary repeatedly lowers one normalized slack while keeping the other below a controlled threshold, eventually forcing a final PROP1 violation.The construction first ensures both agents have positive outside-good maxima and then uses carefully chosen normalized goods.
  • Consequences: The same impossibility applies to randomized algorithms, because the adaptive construction reaches a violation for every realized sequence of recipients.It also rules out positive guarantees for numerous standard fairness notions and yields corresponding lower bounds for chores.

4 Constant PROP1 Approximation with MIV Predictions

With maximum item value predictions, the paper replaces the previous 1/n-PROP1 guarantee by a deterministic constant-factor guarantee against adaptive adversaries. The same potential-based rule extends to bounded positive support, one-sided prediction error, and—when the horizon is known—simultaneous PROP1 and normalized envy guarantees.

  • Potential-based allocation: The allocation rule assigns each arriving good to a recipient minimizing a reciprocal slack potential Ψt.An averaging argument shows that some deterministic recipient does not increase the potential, even against adaptive adversaries.
  • Constant-factor PROP1: 1/2-PROP1 is guaranteed deterministically against adaptive adversaries using perfect maximum item value predictions.The rule does not require access to the horizon.
  • Constant-factor PROP1: n/(n + κ)-PROP1 is guaranteed when every good is positively valued by at most κ agents.The guarantee specializes to 1/2-PROP1 for κ = n and improves as κ decreases.
  • Imperfect predictions: n(1−ε)/(n + κ−ε)-PROP1 remains guaranteed under one-sided prediction error ε.The factor stays positive for every fixed ε < 1.
  • PROP1 with additive envy: The joint guarantee combines the reciprocal PROP1 potential with exponential pairwise-envy potentials through an averaging distribution.The equal probability component balances first-order envy changes while preserving the reciprocal analysis.
  • PROP1 with additive envy: β-PROP1 and O(sqrt(T log n/n)) normalized maximum additive envy are achieved for every fixed β in (0, 1/2) when the horizon T is known.For T ≥ n log n, the envy bound is O(sqrt(T log n/n)); the normalized values divide each agent’s values by their predicted maximum item value.

5 Tight Guarantees for Like and Rand

Against a non-adaptive adversary, Like's PROP1 guarantee improves when each good has fewer positive-valuing agents, while Rand does not; both dependencies are tight up to constants. The section proves these results using concentration for Like and matching lower-bound constructions.

  • Rules and setting: Like assigns each good uniformly among agents valuing it positively, while Rand assigns uniformly among all n agents.For Like, an agent valuing a good receives it with probability 1/|N(g)| rather than 1/n under Rand.
  • Like's guarantee: Under the non-adaptive model, Like returns an α-PROP1 allocation with probability at least 1−δ for α = min{1, 3n/(32κ log(n/δ))}.The proof bounds each agent's lower-tail failure probability and applies a union bound over agents.
  • Like's guarantee: Like improves by a factor n/κ when fewer agents value each good, and achieves PROP1 with probability at least 1−δ when κ ≤ 3n/(32 log(n/δ)).When κ=n, the order matches Rand's Θ(1/log(n/δ)) guarantee.
  • Matching lower bound: The dependence on n, κ, and δ is tight up to constants for Like on fixed binary instances.The lower bound uses groups of κ agents and goods valued only within each group, showing that Like cannot guarantee a larger factor of order n/(κ log(n/δ)).
  • Comparison with Rand: Rand's worst-case PROP1 factor remains Θ(1/log(n/δ)) even when every good is positively valued by only one agent.Thus Rand does not benefit from small κ, unlike Like.
  • Proportionality versus envy: Like can have larger additive-envy fluctuations than Rand, because assigning goods among fewer agents increases pairwise variance.A lower bound for Like has square-root dependence on m/κ, matching the upper-bound dependence apart from a logarithmic simultaneous-guarantee factor.

6 Conclusion

The paper closes three online fair-division gaps: impossibility without predictions, constant PROP1 guarantees with maximum-item-value predictions, and tight non-adaptive guarantees for Like versus Rand. It also identifies remaining questions about combining guarantees and improving unrestricted-instance bounds.

  • Main conclusions: Without predictions, every positive PROPk factor is impossible for goods against adaptive adversaries, while every PROPk factor below n is impossible for chores.The goods impossibility persists with known horizon, values in [0,1], and at most two positive-valuing agents per good.
  • Main conclusions: Maximum item value predictions improve the adaptive-adversary guarantee from 1/n-PROP1 to 1/2-PROP1, and to n/(n+κ) when an upper bound κ is known.For known horizon T≥n log n, the paper also gives β-PROP1 with normalized maximum additive envy O(sqrt(T log n/n)) for fixed β∈(0,1/2).
  • Main conclusions: Against a non-adaptive adversary, Like has tight guarantee Θ(min{1,n/(κ log(n/δ))}), whereas Rand remains Θ(1/log(n/δ)) even when each good has one positive-valuing agent.The parameter κ improves Like's proportionality but can worsen pairwise envy fluctuations.
  • Interpretation: The paper explains that maximum-item-value predictions and non-adaptive randomness provide distinct forms of predictability enabling proportionality guarantees.Without either source of predictability, adaptive adversaries rule out the stated positive goods and chores guarantees.
  • Open questions: Open questions include the optimal PROP1 factor with exact MIV predictions, combining 1/2-PROP1 with normalized envy, and improving Rand's unrestricted-instance factor.These questions are stated as unresolved rather than as limitations of an established theorem.

A Definitions and Consequences for Other Fairness Notions

This section defines the paper's direct multiplicative fairness notions, including envy-based, share-based, and proportionality-based guarantees. It also gives the formal PROP, PROPX, and PROP1-related definitions used in subsequent implications.

  • Proportionality-based axioms: An allocation is α-PROP when each agent receives at least α·vi(G)/n.This is the direct proportionality benchmark from which PROP1-related variants are defined.
  • Proportionality-based axioms: An allocation is α-PROPX when adding any good outside an agent's bundle reaches α·vi(G)/n, with the condition automatic when the agent already owns all goods.The section additionally defines PROPm, PROPavg, and Avg-EFX through corrections based on the smallest or average removable values.
  • Notation: At α=1, the defined multiplicative notions reduce to their usual exact versions.The convention applies to the proportionality variants listed in this section.
  • Envy-based axioms: An allocation is α-EF when each agent values their bundle at least α times every other agent's bundle.The section also defines α-EFX and α-EF1 by permitting removal of one positively valued good or one good, respectively, from another bundle.
  • Share-based axioms: An allocation is α-MMS when each agent receives at least an α fraction of their maximin share over n bundles.The section also defines α-EEFX, α-MXS, and α-GMMS using EFX-compatible allocations and groupwise maximin shares.

A.2 Implications

The appendix shows that many standard fairness notions imply PROP1 or a related PROPk guarantee, so the paper's online impossibility for PROPk transfers to them. It also states the analogous chores limitation, where no universal factor below n is possible.

  • Implications to PROP1: Each condition covered by Lemma A.1 implies α-PROP1, including the relevant proportionality, envy, and share-based notions.The proof uses the maximum value hi of a good outside the agent's bundle to derive the PROP1 inequality.
  • Share-based implications: Because α-GMMS implies α-MMS, the implication chain also transfers GMMS guarantees to the corresponding PROP1 guarantee.The appendix derives this through the full-agent group in the GMMS definition.
  • EFc implication: Every α-EFc allocation is α-PROPc(n−1), converting removal of at most c goods from each other bundle into a proportionality guarantee.This implication is stated for any positive integer c.
  • PMMS implication: Every α-PMMS allocation is αn/(α+2(n−1))-PROP1.The proof uses a two-partition lower bound based on total value and the largest good, then relates pairwise maximin share to PROP1.
  • Online impossibility: No randomized online algorithm can guarantee any positive multiplicative approximation to the listed notions against an adaptive adversary.A positive guarantee for any listed notion would imply β-PROPk for fixed β>0 and k, contradicting the paper's randomized impossibility theorem.
  • Chores: For chores, every allocation is n-PROPk, and the appendix shows that no smaller universal factor is possible online even for fixed k.Chore guarantees use λ≥1, with smaller factors stronger than larger ones.

B.1 The PROPk Lower Bound

The section constructs an adaptive adversary showing that online allocations can fail PROPk by making one agent retain almost all of her observed cost even after removing k chores. The resulting impossibility persists under known horizons, bounded costs, and randomized algorithms.

  • Adversarial construction: The adversary ensures that, for every recipient sequence, some prefix and agent retain more than a (1−ε) fraction of total observed cost after removing up to k chores.The construction uses recursive agent induction and geometrically increasing costs for the additional agent.
  • Adversarial construction: The induction repeats an r-agent strategy in blocks while scaling costs and terminating blocks according to the additional agent’s recipient.Weights normalize prior costs, and every chore has positive cost for every agent.
  • Impossibility guarantee: The lower bound applies to every deterministic or randomized online algorithm, with randomized failure occurring with probability one.The adversary observes only realized recipients of earlier chores.
  • Impossibility guarantee: The adversary can reveal the final number of chores in advance and ensure every cost lies in [0,1].Zero-cost chores pad the instance to the known horizon, while common scaling preserves the inequalities.

B.2 Consequences for Proportionality and Envy

The PROP k lower bound transfers to broad envy- and proportionality-based notions for chores. In particular, no randomized online algorithm guarantees finite multiplicative envy approximations or any λ-approximation for the listed proportionality notions when 1≤λ<n.

  • Proportionality consequences: The chore definitions include λ-PROP1, λ-PROPX, λ-PROPm, and λ-PROPavg, with PROPm and PROPavg coinciding with PROPX under additive costs.The section states that the same lower-bound conclusion holds for λ-PROPm and λ-PROPavg.
  • Envy consequences: Every λ-EFc or epistemic λ-EFc allocation is θ_n(λ)-PROPc, and θ_n(λ)<n for finite λ≥1.The implication includes λ-EFX and λ-EEFX as the c=1 case.
  • Envy consequences: No randomized online algorithm guarantees any finite multiplicative approximation to EF, EF1, EFX, EEF, EEF1, EEFX, EFc, or epistemic EFc.This follows by combining the proportionality lower bound with the envy-to-proportionality implication.

B.3 Consequences for Share-Based Notions

The same adaptive lower bound extends to share-based chore notions through quantitative implications to PROP1. The resulting impossibility covers MMS-, APS-, and related shares, with separate factors for PMMS, PAPS, and PPROP.

  • Share implications: Every λ-MMS, λ-APS, λ-MXS, λ-M1S, λ-GMMS, or λ-GAPS allocation is ψ_n(λ)-PROP1, where ψ_n(λ)<n for 1≤λ<n.The bound uses auxiliary inequalities relating these shares to total chore cost.
  • Share lower bounds: No randomized online algorithm guarantees λ-MMS, λ-APS, λ-MXS, λ-M1S, λ-GMMS, or λ-GAPS for any 1≤λ<n.The conclusion also agrees with an independent (n−ε) online MMS lower bound.
  • Share lower bounds: For 1≤λ<2, no randomized online algorithm guarantees λ-PMMS, λ-PAPS, or λ-PPROP.The PMMS implication uses a separate two-bundle argument, while PAPS and PPROP follow from related share comparisons.
  • Combined consequence: Against an adaptive adversary, these impossibilities hold simultaneously with the envy and proportionality lower bounds, with probability one and under known horizons and bounded costs.The corollary covers all listed notions and any simultaneous guarantee containing one of them.
  • Scope boundary: The positive-cost-on-at-most-two-agents restriction has no chore analogue when n≥3, because every chore then has a zero-cost recipient.Assigning each chore to a zero-cost agent achieves exact proportionality and envy-freeness.

C.1 Proof of Lemma 4.3

The proof tracks how assignments update pairwise quantities and bounds their aggregate evolution. It handles both recipients and preserves well-defined reciprocal terms throughout the construction.

  • Invariant preservation: All reciprocal terms remain well-defined under every possible assignment because the current slacks stay positive.The proof uses 1/s_i≤Ψ_{t−1}<M_β.
  • Parameter setup: The construction chooses nonnegative q_i summing to one and defines the parameters used in the pairwise update analysis.For positive p_i, π_i is defined as ρ+u_i.
  • Potential updates: Assigning an item to agent j increases E_ij, assigning it to agent i decreases E_ij, and other assignments leave E_ij unchanged.The update magnitudes are proportional to b v_i(g_t).
  • Potential updates: The exponential update is bounded by a linear term in x and a quadratic remainder, yielding the needed per-step control.The displayed inequality bounds E_ij by 1 + 2x u_j + 3x^2.

D A Simpler Simultaneous Guarantee with MIV Predictions

With perfect maximum-item-value predictions and a known horizon of at least n log n goods, the joint allocation rule combines PROP1 and envy potentials to guarantee both properties simultaneously. Its PROP1 factor α_n is bounded between 1/(2 log(4n)) and 2 log(2n).

  • Proof idea: The proof maintains Ω_t below one because both component potentials satisfy the same averaging inequality and Ω_0 = Φ_0 + Γ_0 < 1.Since the component terms are nonnegative, the final bound implies each PROP1 and envy potential is individually below one.
  • Joint allocation rule: The joint allocation rule assigns each arriving good to a recipient minimizing the combined potential Ω_t := Φ_t + Γ_t.The two component potentials share an averaging inequality, so minimizing their sum keeps the combined potential from increasing.
  • Guarantee: Theorem D.3 assumes perfect MIV predictions, a known horizon T = m ≥ n log n, and an adaptive adversary.Under these conditions, the rule returns an allocation satisfying both guarantees simultaneously.
  • Guarantee: The resulting allocation is α_n-PROP1, with 1/(2 log(4n)) ≤ α_n ≤ 2 log(2n).The factor also satisfies 0 < α_n < 1.
  • Guarantee: The same allocation guarantees bounded maximum additive envy under valuations normalized by each agent’s maximum item value.The theorem states this second guarantee using the normalized valuations bvi and the maximum pairwise envy expression.
Loading 2609.05310v1…