Temporal Fair Division of Indivisible Goods with Scheduling
This work addresses fairness in sequential resource allocation for multi-agent systems, but it is incremental as it builds on known impossibilities and explores restricted settings.
The paper tackled the problem of achieving temporal fairness in dividing indivisible goods over multiple rounds, proving that while strict fairness notions like TEFX and TMMS are largely impossible, approximations such as a 1/2-approximation for α-TEFX in specific cases and TEF1 with a scheduling buffer of at least n/2 for identical days are achievable.
We study temporal fair division, where agents receive goods over multiple rounds and cumulative fairness is required. We investigate Temporal Envy-Freeness Up to One Good (TEF1) and Up to Any Good (TEFX), its approximation $α$-TEFX, and Temporal Maximin Share (TMMS). Motivated by known impossibilities in standard settings, we consider the model in various restricted settings and extend it by introducing scheduling. Our main contributions draw the boundary between possibility and impossibility. First, regarding temporal fair division without scheduling, we prove that while constant-factor $α$-TEFX is impossible in general, a $1/2$-approximation is achievable for generalized binary valuations and identical days with two agents. Second, regarding temporal fair division with scheduling, we demonstrate that a scheduling buffer of size at least $n/2$ enables TEF1 for identical days. However, we establish that TEFX and TMMS remain largely impossible even with scheduling or restricted domains. These results highlight the inherent difficulty of strict temporal fairness and quantify the trade-offs required to achieve approximation guarantees.