Temporal Fair Division

We study temporal fair division, whereby a set of agents are allocated a (possibly different) set of goods on each day for a period of days. We study this setting, as well as a number of its special cases formed by the restrictions to two agents, same goods on each day, identical preferences, or combinations thereof, and chart out the landscape of achieving two types of fairness guarantees simultaneously: fairness on each day (per day) and fairness over time (up to each day, or the weaker version, overall). In the most general setting, we prove that there always exists an allocation that is stochasticallydominant envy-free up to one good (SD-EF1) per day and proportional up to one good (PROP1) overall, and when all the agents have identical preferences, we show that SD-EF1 per day and SD-EF1 overall can be guaranteed. For the case of two agents, we prove that SD-EF1 per day and EF1 up to each day can be guaranteed using an envy balancing technique. We provide counterexamples for other combinations that establish our results as among the best guarantees possible, but also leaving open some tantalizing questions. * * ∅ X (Theorem 8) ? Related Work Our temporal fair division model is related to (but separate from) several fair division models studied in the literature. Repeated fair division. The repeated fair division model of Igarashi et al. [2024] , which is the case of identical days in our more general model, is the most closely related to our work (though they deal with mixed goods and chores rather than just goods). Some of their results are for two agents (still with identical days). In Appendix B, we show some results similar to their two agent results in our model, namely, that SD-EF1 per day and SD-EF1 up to each day can be achieved simultaneously, while also achieving SD-EF on every even day. This result is the only overlap between our works, and we present it again because we obtain a shorter proof with a much simpler algorithm when dealing with instances with only goods. The rest of their results with two or more agents seek exact fairness guarantees, such as (exact) envy-freeness overall, in limited cases such as when the number of days is a multiple of the number of agents. Online fair division. In the online fair division model, goods arrive one by one and must be irrevocably allocated to an agent upon arrival with no knowledge of agent preferences over the goods to arrive later. Typically, one seeks to maintain a certain level of fairness. Clearly, any online fair division algorithm can be simulated in our temporal fair division model to achieve the same guarantee up to each day. One online fair division paper of particular note is that of He et al. [2019]. They introduce the "Informed Model" of online fair division, where irrevocable allocation decisions must be made as goods arrive one at a time in adversarial order, but the allocation algorithm is given all goods and the order they will arrive in upfront. The main goal in the informed model is to achieve an allocation that remains EF1 after each good is allocated. Clearly, this is equivalent to achieving EF1 up to each day in temporal fair division when each day only contains a single good. He et al. conclude that it is impossible to allocate the goods in such a way that EF1 is always maintained. By corollary, EF1 up to each day is also infeasible. In another paper, Benadè et al. [2024] show that O( k log n) envy can be maintained up to k days, and also point out that randomized algorithms may have much greater power against a nonadaptive adversary, who sets the full instance before the algorithm starts making random choices, with no super-constant envy lower bound known for this case. Online fair division with a nonadaptive adversary is still a stronger model than temporal fair division due to the fact that the algorithm does not have knowledge of what goods will arrive in future time periods. Repeated (or many-to-many) matching. Our work is also inspired by the earlier work of Gollapudi et al. [2020] , who consider the repeated two-sided matching problem, where there are n agents on each side of a two-sided market with agents on each side having preferences over those on the other side, and the goal is to compute a perfect matching on each day over a period of days. They also seek guarantees such as EF1 up to each day. However, their positive results are only for binary valuations, and they leave achieving EF1 (for both sides) up to each day for general additive valuations as an open question. Finally, note that repeated perfect matching effectively produces a many-to-many matching. Freeman et al. [2021] study how to achieve EF1 (for both sides) in this setting, which can be viewed as an EF1 overall guarantee. They show how to achieve it when agents on each side have identical preferences, but leave it open for the case of general additive valuations. Note that unlike in fair division, EF1 overall is not straightforward in their case be