cs.GTOct 7, 2026

Minimizing Cumulative Envy in Allocating a Sequence of Items

Authors: Paul W. Goldberg, Isaac Robinson, Nicholas Teh

Organizations: University of Oxford, UK

Abstract

We study temporal fair division with indivisible goods that arrive sequentially and must be allocated irrevocably. In contrast to the usual online model, we assume that valuations and future arrivals are known in advance, and ask how unfairness evolves during the process. We introduce \emph{cumulative maximum envy}: the sum, over all rounds, of the maximum pairwise envy at that round. Equivalently, this is the area under the worst-envy curve, and it captures both the magnitude and the duration of envy. For a fixed arrival order, we show that the corresponding decision problem is strongly NP-complete and that minimizing this objective admits no constant-factor approximation unless P = NP, even under identical valuations and even under binary valuations. We complement these hardness results with a dynamic program that gives pseudopolynomial-time solvability for a constant number of agents, polynomial-time algorithms in further restricted settings, and an FPTAS for fixed nn under identical integer valuations. We then study a sequencing variant where the algorithm may choose the arrival order. This variant remains NP-complete even for two agents with identical valuations; however, a simple greedy algorithm achieves a 3/23/2-approximation for n=2n=2 agents, an n/(n−1)n/(n-1)-approximation for any number of agents, and an additive guarantee depending on the maximum value of any good.

Explore similar work

CardsList
  1. Simultaneous Envy and Equitability Guarantees

    Aug 26, 2026Hadi Hosseini, Shraddha Pathak, Lirong Xia +1Algorithmic Fairness

  2. Online Fair Division with Budget Constraints

    Jul 25, 2026Saar Cohen, Nicholas Teh, Paul W. Goldberg +1Algorithmic FairnessFirst-Price Auctions