acceptodds
Under review as a conference paper at ICLR 2027

Online Fair Division with Upgrade Recourse

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 , where is the -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 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.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
online fair division, recourse, learning-augmented algorithms

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_VM7UOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies online allocation of indivisible goods among agents with additive valuations. Each good's values are revealed on arrival, and it must be allocated immediately. Reassignments are allowed but must satisfy either item-level upgrades, where every old good is retained or replaced by a good worth at least as much, or bundle-level upgrades, where each agent's total utility must not decrease. Fairness is measured primarily by maximin share (MMS), the value an agent can secure by partitioning the goods into nn bundles and taking the least valuable one.

The authors show that, under item-level upgrades, fixed picking sequences achieve nearly 1/Hn1/H_n approximation of MMS, where HnH_n is the nn-th harmonic number. If further requiring envy-freeness up to one good (EF1), then the optimal approximation ratio is reduced to 1/n1/n. On the other hand, bundle-level upgrades permit an algorithm that achieves exact MMS, envy-freeness up to any good (EFX), and Pareto optimality for two agents. For n≥3n \geq 3, the authors give an algorithm that achieves (n−1)/(2n−3)(n-1)/(2n-3)-MMS together with EF1 and 1/21/2-EFX; they also show that no approximation ratio above 10/1110/11 is possible even with identical valuations. When item predictions are provided, the authors show how to achieve offline MMS guarantees with an additive loss bounded by prediction error, but they show that requiring exact MMS with correct predictions rules out any positive worst-case MMS approximation under item-level upgrades.

Critical strengths

This paper studies a trending and well-motivated problem, and the writing is generally clear. The online setting with upgrade recourse naturally generalizes prior recourse settings and is interesting to study. The authors establish a variety of results, covering different fairness concepts and the setting with predictions. In particular, it's good-to-know that a fixed picking sequence can achieve nearly optimal approximation factors for item-level upgrade.

Critical weaknesses

The concerned setting doesn't bring new technical insight to the fair-division literature: the proposed algorithms (such as using picking sequences) and analysis seem to largely follow existing ones, and is also too restricted for practical applications. Many gaps remain in the results (although I believe closing them could be difficult).

Questions for authors

No.

Reviewer_VLnSOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
3(+1)
Read review
Paper summary

The paper studies algorithms with upgrade recourse for online fair division. Indivisible items are allocated to agents immediately, but, unlike the usual irrevocable online setting, some reallocations are allowed. Under (1) item-based recourse, each item an agent loses must be exchanged for a distinct item that is at least as valuable to her. Under (2) bundle-based recourse, an agent can receive a new bundle as long as it does not decrease her value. The main goal of the paper is to approximate the maximin share (MMS), although it also considers other guarantees in some cases. The paper starts with (1) and shows that, under this type of recourse, a picking-sequence algorithm that gives later starters more picks and lets agents swap their items for newly arriving ones when beneficial (passing the dropped item on to later turns) achieves the optimal MMS approximation for every nn up to 33. Under bundle-based recourse the approximation improves. For two agents, exact MMS can be guaranteed. For more agents, they prove a guarantee of more than 1/2-MMS, which improves to more than 3/4 for identical valuations, and they show that no guarantee above 10/11 is possible, even for identical agents. Finally, they use frequency predictions to improve the MMS approximation of the final allocation.

Critical strengths

I like the paper. It proposes a natural but new idea. In online fair division the impossibility results are strong, so some relaxation is necessary, and this one makes sense: reallocations are allowed, but only with the agents’ implicit consent, i.e., no agent may be made worse off. The two variants (item-level and bundle-level) offer two levels of strictness for this consent. The motivation for the model could be developed further, though. The paper explores the new model in considerable depth for a paper introducing a new idea. Several results build on known techniques from the literature, but this is reasonable and does not diminish the contribution.

In particular, I find the item-level results especially interesting. They are nearly fully characterized: the paper derives the optimal MMS factor exactly for n≤33n \leq 33, and for larger nn the achievable factor approaches (asymptotically) the 1 over harmonic impossibility bound. The impossibility results are the highlight for me, as they hold even for algorithms that use the agents’ cardinal values. Also the contrast between the two recourse regimes is informative (although expected). Being strict on the allowed recourse to fix for any lost item pushes the MMS approximation towards 0, which allowing some worse items individually, but better in general allows for 1/2-MMS approximation in general, which compares reasonably with the best known offline factor of slightly above 3/4.

Critical weaknesses

My main concern is the paper’s organization, which is a twofold issue. First, the nine-page main text is very densely written. There are missed opportunities to discuss the results and present them in a more accessible way. For example, Section 4.1 states Theorem 4.1 without any intuition, although a short sketch of the proof would give the reader very useful context. Other parts of the main text are also problematic in their density, e.g., lines 281–283, where several claims are packed into just three lines. Frankly, it would make sense to move Section 5 (predictions), which appears to be the weakest part of the paper, to a clearly organized appendix, and to use the freed space to highlight and explain the most important results.

Even more important is the organization of the appendix and the way the proofs are packaged. The appendix is hard to read linearly: connections between its sections are missing, and the reader has to move back and forth to the main text. This is not unusual in itself, but the appendix here is long, which makes it a real obstacle. More importantly, the packaging is unusual and several proofs are hard to trace; see, for example, Section B.7 and Theorem B.7 (details in Question 1 below). Section B.7 proves inequality (3), which is stated only inline in the proof of Lemma B.3 rather than as a self-contained lemma, and its hypotheses are split between the two places. This is problematic, especially since the same inequality is reused later as the hypothesis of Lemma B.15, connected only by a reference to the section. Similar roadmap issues appear in the proofs of the central Theorems 3.3 and 3.4. These can be followed, but only with some effort, since no part of the paper explains how the individual results combine into the proof of each theorem.

Questions for authors
  1. Can you please clarify the arguments behind the claims of Section 3.3? Theorem B.7 is not given a proof of its own. Its second part (the finite optimization) is derived in a remark at the end of the proof of Theorem B.9 (line 1229), i.e., from a result stated later. However, its first claim, “for every deterministic ordinal algorithm ... at least the same MMS factor,” is not proven anywhere, and the paper does not indicate where it would be. Parts of the proof of Theorem B.9 (lines 1181–1187) seem related, but they are not connected to Theorem B.7, and this claim does not follow from the statement of Theorem B.9. Moreover, since this is a statement about all ordinal algorithms, the class should be defined formally. Currently it is only described informally (“algorithms using only the agents’ rankings of individual goods”), without specifying, for example, what exactly the algorithm observes at each step or how ties are revealed.

  2. Can the authors elaborate on what do they mean with "full-tradeoff" for EF1 and α\alpha-MMS (lines 330-331)?

  3. Isn't Lemma B.1 well known? If yes, please provide appropriate attribution.

Reviewer_tGu9OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper considers the following fair division problem. Suppose mm items arrive online and have to be assigned to nn agents. For every agent, the goal is to attain their maximin share, which is the maximum value they can obtain by partitioning the items into nn parts and then receiving the least valuable part of this partition. If no reassignment is permitted, i.e., in the standard online setting, then no positive fraction of these benchmarks can be simultaneously attained for all agents. So, this paper considers two forms of reassignment. The more constrained one requires that for any agent, their later allocation should dominate their earlier allocation in value item for item. In this case, the first result of the paper shows that a 1/Hn1/H_n fraction of the maximin share can be attained by all agents using a fixed picking sequence, i.e., the allocation for any prefix of items is given by the agents going in a fixed order and picking the most lucrative available item. The second form of reassignment relaxes the condition to the later reassignment only needing to dominate an earlier assignment in aggregate value (rather than item for item). In this case, the fraction of maximin share that can be attained improves to 1/21/2. This latter model also allows various standard notions of approximately envy-free allocations while retaining the value approximation. A corresponding result is ruled out for the previous model, where the value approximation drops to 1/n1/n when enforcing approximate envy-freeness.

Critical strengths

The results in the paper are quite interesting. The two reassignment models are reasonable ways of getting around the impossibility of irrevocable allocations, and the paper essentially obtains tight results for both models for the maximin share benchmark.

Critical weaknesses

One weakness of the paper is that the presentation in the first 9 pages does not give any description of the algorithms. This means that the paper is essentially just a list of results, which does not make for interesting reading.

Questions for authors

No specific question, but perhaps you can say more about what precisely allows better algorithms in the second model over the first, giving a description of your algorithms for both settings. The learning-augmented results seem somewhat of an afterthought, so my suggestion would be to focus on the first two sets of results, but give the algorithms that would make the paper more interesting to read.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.