Temporal Fair Division of Indivisible Items

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 for achieving approximate envy-freeness under the assumption that agents have no information about future items. In contrast, we assume that the algorithm has complete knowledge of the future, and aim to ensure that the cumulative allocation at each round satises approximate envy-freeness, which we dene as temporal envy-freeness up to one item (TEF1). We focus on settings where items are exclusively goods or exclusively chores. For goods, while TEF1 allocations may fail to 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 obtain analogous results for the special cases, but present a slightly weaker intractability result. We also show that TEF1 is incompatible with Pareto optimality, with the implication that it is intractable tond a TEF1 allocation that maximizes any ?-mean welfare, even for two agents.