Minimizing Cumulative Envy in Allocating a Sequence of Items

Key points

• We study temporal fair division with indivisible goods that arrive sequentially and must be allocated irrevocably.1
• 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.1
• 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 $n$ under identical integer valuations.1
• This variant remains NP-complete even for two agents with identical valuations; however, a simple greedy algorithm achieves a $3/2$-approximation for $n=2$ agents, an $n/(n-1)$-approximation for any number of agents, and an additive guarantee depending on the maximum value of any good.1

Sources (1)

• [1]Minimizing Cumulative Envy in Allocating a Sequence of Items
  arXiv (AI, ML, NLP, CV, robotics, multi-agent) · Oct 7, 11:04 AM

  We introduce cumulative maximum envy: the sum, over all rounds, of the maximum pairwise envy at that round.

  We study temporal fair division with indivisible goods that arrive sequentially and must be allocated irrevocably.

Extractive summary: sentences quoted from the sources.