Temporal Fair Division of Indivisible Items
This addresses fair division challenges in dynamic resource allocation for applications like scheduling or online platforms, though it is incremental as it builds on prior online fair division models by adding future knowledge assumptions.
The paper tackles the problem of fairly allocating indivisible items that arrive sequentially, with immediate and irrevocable decisions, by introducing temporal envy-freeness up to one item (TEF1) for settings with complete future knowledge. It shows that TEF1 allocations exist in special cases like two agents or unimodal preferences, with polynomial-time algorithms, but proves NP-hardness for general existence and incompatibility with Pareto-optimality.
We study a fair division model where indivisible items arrive sequentially, and must be allocated immediately and irrevocably. Previous work on online fair division has shown impossibility results in achieving approximate envy-freeness under these constraints. In contrast, we consider an informed setting where the algorithm has complete knowledge of future items, and aim to ensure that the cumulative allocation at each round satisfies approximate envy-freeness -- which we define as temporal envy-freeness up to one item (TEF1). We focus on settings where items can be exclusively goods or exclusively chores. For goods, while TEF1 allocations may not always exist, we identify several special cases where they do -- two agents, two item types, generalized binary valuations, unimodal preferences -- and provide polynomial-time algorithms for these cases. We also prove that determining the existence of a TEF1 allocation is NP-hard. For chores, we establish analogous results for the special cases, but present a slightly weaker intractability result. We also establish the incompatibility between TEF1 and Pareto-optimality, with the implication that it is intractable to find a TEF1 allocation that maximizes any $p$-mean welfare, even for two agents.