Minimizing overall envy when allocating items arriving over time
Minimizing Cumulative Envy in Allocating a Sequence of Items
Computer Science and Game TheoryMultiagent Systems
Summary
This paper looks at how to fairly give out items that arrive one after another without taking any back. Unlike usual methods, it assumes we know in advance what items will arrive and how much everyone values them. The authors introduce a way to measure unfairness by adding up the worst feelings of envy over time. They show that finding the absolutely fairest way is very hard in general, but provide some algorithms that work well in special cases or for a small number of people.
What this means in practice
- •For resource allocation system designers: Design allocation systems that minimize ongoing envy when distributing goods arriving over time with known values.
- •For workflow managers: Improve task or item sequencing in workflows to reduce overall dissatisfaction or perceived unfairness among participants.
A theory result. No direct application yet.
Authors
Paul W. Goldberg, Isaac Robinson, Nicholas Teh
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 $n$ 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/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.