This paper investigates the online fair division of indivisible mixed resources among agents with additive valuation functions. In the standard online model, an indivisible item arrives at each time step; each agent may assign it a positive, negative, or zero value, and it must be irrevocably allocated before the arrival of the next item.
We aim to maintain some fairness guarantees, focusing on envy-freeness (EF) and one of its prominent relaxations, envy-freeness up to one item (EF1). Given the strong negative and scarce positive results for this problem without additional assumptions, we enhance our algorithms with buffers that can store and rearrange a limited number of items.
This setting naturally interpolates 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, where each agent assigns at most $k$ distinct values to items.
Specifically, 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 the number of agents. Our approach relies on novel combinatorial arguments and constructing a sequence of envy-free matchings to allocate most items.
Finally, we extend our results to general additive valuation functions with dependence on the largest per-agent ratio between two values of the same sign, and we identify limitations of our approach via impossibility results on the use of smaller-sized buffers.
Blogger's Review: This study innovatively combines online fair division with reordering buffers, exploring how to maintain fairness in complex resource allocation scenarios. This approach not only enhances the capabilities of traditional online algorithms but also provides new insights for future research, especially in handling indivisible resources with flexibility and efficiency. The combination of fairness theory and practical algorithms presented here is noteworthy and deserves close attention.