Online Fair Division Meets Reordering Buffers
2026-07-01 • Computer Science and Game Theory
Computer Science and Game TheoryDiscrete MathematicsData Structures and Algorithms
AI summaryⓘ
The authors study how to fairly divide items that can be good or bad (mixed manna) among people when items arrive one by one and must be given away immediately. They focus on fairness measures called envy-freeness (no one prefers someone else's share) and a relaxed version called EF1, which allows slight envy. To improve fairness, the authors let the algorithm temporarily store some items in a buffer before giving them out. They show that with a buffer sized based on the number of agents and value types, it's possible to keep allocations mostly envy-free or EF1 at all times. Their work also explores limits of this method and extends it beyond simple cases to more general value settings.
online fair divisionindivisible itemsmixed mannaadditive valuationsenvy-freeness (EF)envy-freeness up to one item (EF1)buffering in allocationpersonalized k-value instancescombinatorial algorithmsimpossibility results
Authors
Georgios Amanatidis, Giulio Giaconi, Evangelos Markakis, Nicos Protopapas
Abstract
We study the online fair division of indivisible mixed manna among agents with additive valuation functions. Under the standard online model, at each time step an indivisible item arrives; each agent may assign it a positive, negative, or zero value, and it must be irrevocably allocated, before the arrival of the next item. At the same time, we also wish to maintain some fairness guarantee, and in this work we focus on envy-freeness (EF) and one of its most prominent relaxations, envy-freeness up to one item (EF1). Given the strong negative and the scarce positive results for this problem without additional assumptions, we augment our algorithms with buffers that can store and rearrange a limited number of items. This setting interpolates naturally between the fully online case (no buffer) and the fully offline case (a buffer large enough to hold all items). We show that algorithms equipped with reasonably sized buffers can achieve strong guarantees for personalized $k$-value instances, i.e., instances in which each agent assigns at most $k$ distinct values to items. In particular, we construct allocations that are EF1 at every time step and EF at most time steps, using a buffer of size linear in $k$ and in the number of agents. Our approach relies on novel combinatorial arguments and on constructing a sequence of envy-free matchings that allocates most items. Finally, we extend our results to general additive valuation functions, with a dependence on the largest per-agent ratio between two values of the same sign, and we also identify limitations of our approach via impossibility results on the use of buffers with smaller size.