Temporal fair division

Temporal fair division is a sequence of fair division instances among the same set of agents. Some examples are:

A group of housemates that have to divide the house-chores among them, day after day.
Dividing equipment between departments in a university, where various pieces of equipment arrive at different times.

The standard fair division setting considers a one-shot division; but in reality, the same set of agents usually participate in several consecutive fair division instances. This adds more complexity to the fairness requirements.
In some cases, the resources to allocate are not known in advance. Each day, a new resource arrives, and must be immediately and irrevocably allocated. Fairness becomes much harder to attain, as the allocator might make an allocation decision that will in hindsight appear very unfair. This setting is explained in the page on online fair division.
This article focuses on the setting in which the resources to allocate are all known in advance: we know exactly what is going to arrive and when. The challenge here is that, in a sequence of fair division instances, people have higher fairness expectations. While they agree to tolerate a slightly unfair allocation in a single day, they expect the fairness to be restored in following days. This gives rise to stronger fairness notions, that take the temporal nature of the problem into consideration.

Terminology

Rounds

It is common to call each instance in the sequence a "round" or a "day", though of course it is possible that the instances occur at different time-intervals.

Fairness notions

Fairness notions. Let F be any fairness notion defined for a one-shot division setting. For example, F can be envy-freeness, envy-freeness up to one item, proportionality, and so on. F can be generalized to temporal fair division in three different ways:Local - for each day t, the allocation in day t should satisfy F;Cumulative - for each day t, the combined allocation in days 1,...,t should satisfy F;Overall - the combined allocation in days 1,...,T should satisfy F.
Note that Cumulative-F implies Overall-F. However, Local-F is independent of these two. Local-F alone and Overall-F alone can be obtained by any standard allocation that obtains F; the challenges are threefold:

Guarantee Local-F and Overall-F simultaneously;
Guarantee Cumulative-F alone or in combination with Local-F;
Guarantee Overall-F when F itself cannot be attained.

Remark. When studying cumulative fairness, it is usually assumed that there is a single item per day.This is because, for any instance with e.g. k items per day, one can create an instance with a single item per day, and if the new instance admits a cumulative-F allocation, then so does the original instance.

Identical days: Repeated fair division

Repeated fair division is a special case of temporal fair division in which the items are the same in each period. This setting allows for stronger fairness guarantees.

Repeated matching

Repeated matching is a special case of repeated fair division in which there are n items in each round, and each agent should exactly one item per round. An example of this setting is housechore allocation: each day, each housemate must do exactly one chore, and the chores are the same each day. Some fairness notions are easy to attain in this setting:

Local-EF1 is trivially attained by any matching, as each agent only gets one item.
Overall-EF1 can be found by creating T copies of each item and using the Biswas-Barman algorithm for fair allocation with partition matroid constraints, or simply by round-robin item allocation. This guarantees that each agent receives exactly T item-copies. This allocation can then be converted to a sequence of T matchings using an edge-coloring algorithm.

Time-dependent valuations and Overall-EF1

Caragiannis and Narang study a generalized repeated matching setting in which the value of an agent for an item may depend on the number of rounds the item was previously used by the same agent. In this setting, attaining overall-EF1 becomes more challenging, and the round-robin technique does not work. For example, suppose there are two agents, two items and three rounds. Suppose that:

Alice always values x at 2; she values the first use of y at 1, and the second and third uses at 10.
George always values y at 2; he values the first use of x at 1, and the second and third uses at 10.

In round-robin, Alice will choose three copies of x and George will choose three copies of y; both agents end up envying each other, and the overall allocation is not even EF1. They show that:

Computing a utilitarian item allocation is NP-hard for T ≥ 3, by reduction from 3-dimensional matching. However, when the valuations are monotone w.r.t. time, it can be solved in polynomial time, even with mixtures of goods and bads, by reduction to b-matching.'
For agents with identical non-negative valuations, there is a polytime algorithm that computes an overall-EF1 allocation.'
For agents with general non-negative valuations, when T mod n is in, there is a polytime algorithm that computes an overall-EF1 allocation.' In particular, this holds for every instance with at most 4 agents. The existence of overall-EF1 allocations for n≥5 agents remains open.
Even with constant valuations, it is NP-hard to approximate the optimal utilitarian welfare of overall-EF1 allocations to a factor better than O, by reduction from maximum independent set.'
WIth a mixture of goods and bads, EF1 might be impossible to satisfy in a matching, so they relax it to swap-envy-freeness. They prove that, with identical valuations, their Algorithm 1 compues an overall-swapEF allocation. For general valuations, when T mod n is in, there is a polytime algorithm that computes an overall-swapEF allocation. In particular, this holds for every instance with at most 5 agents. The existence of overall-swapEF allocations for n≥6 agents remains open.''''''

Past allocations, Cumulative-EF1 and Pareto-efficiency

Micheel and Wilczynski also study repeated matching. They assume that agents have ordinal preferences over the houses, which do not change between rounds. They measure the cumulative envy - the envy after each time-step. They also require that the allocation at each round be Pareto efficient. They also take into account past rounds - rounds that occurred before the algorithm starts. They study three fairness notions:Mirrored envy: if some agent envies another agent a certain number of times, then the latter envied them the same number of times. They prove that, if there is only one future step, then deciding whether a mirror-EF and PO allocation exists is polynomial. The same holds if there are at most two future steps, and the agents have the same preferences. But if there are two or more future steps, and agents have different preferences, then the decision problem is NP-complete, by reduction from exact-3-cover.Equal treatment of equals : agents with the same preferences get exactly the same received objects. They prove that an ETE and PO allocation always exists when the past is empty and the size of every equivalence class of agents divides the number of future rounds. In that case, a solution can be found in polytime. But in general, deciding whether an ETE allocation exists, even with no past, is NP-complete. But if there is no past, and the number of equivalence classes, then the problem can be solved in pseudo-polynomial time.Minimizing the number of times an agent is envious: If there are T future rounds, then there is always an allocation in which the maximum number of times each agent is envious is at most ceiling. We can find it by running round robin item allocation for ceiling rounds in one order, and for floor rounds in the opposite order. This bound is tight, as if agents have identical strict preferences, for every pair of agents there is one agent who envies the other one for at least ceiling rounds. Deciding if there exists an allocation with max number of envious rounds at most T/3 is NP-hard, by reduction from exact-3-cover.
It remains open whether a cumulative-EF1 allocation always exists. Interestingly, in some cases there exists a cumulative-EF1 allocation but no repetitive cumulative-EF1 allocation. For any n≥3, it is NP-hard to decide whether there exists a repetitive cumulative-EF1 allocation, even for T=2 rounds, by reduction from Multiway number partitioning.

Repeated allocation

In the more general repeated allocation setting, there can be more or fewer than n items each day, and every agent may receive any number of items each day.
Igarashi, Lackner, Nardi and Novaro study both overall fairness and per-round fairness. They consider two settings: the number of rounds can be either fixed in advance, or variable. The prove that:

When the number of rounds is fixed, if T is a multiple of n, then there is always a sequence that is overall envy-free, and a sequence that is overall proportional and Pareto-efficient. In contrast, if T is not a multiple of n, then there might not exist an overall-PROP sequence. Moreover, for any T and any n>2, there might not exist an overall EF+PO sequence.
For n=2 agents and any even T, there always exists a sequence which is overall EF+PO and per-day weak EF1.
For n=2 agents and T=2 rounds, there always exists a sequence that is overall EF+PO and per-round EF1; and we can always find a sequence that is overall EF and per-round EF1. But for T>2, there may be no sequence that is overall EF+PO and per-round EF1.
When the number of rounds is variable, for any n, there always exists a sequence that is overall EF+PO and per-round PROP. They do not give an upper bound on the number of rounds required.

Cookson, Ebadian and Shah' strengthen their results to ordinal fairness. They show polynomial time algorithms that guarantee the following combinations:

For n=2 agents: per-day ordinal-EF1 and cumulative ordinal-EF1, as well as cumulative ordinal-EF for each even day.'
For n agents: per-day ordinal-EF1 and overall ordinal-PROP1''''''

Different days

The more general case of temporal division is when the items in each day may be different. Cumulative-EF1 is the main fairness notion.
A first solution that comes to mind is to use the envy-graph procedure, that is, each day, the daily item is allocated to an unenvied agent. The partial allocation is always EF1. However, in case there is envy-cycle, we must exchange bundles along the cycle, which destroys the cumulative-EF1 guarantee. Still, the envy-graph procedure works when agents have identical valuations, as in this case no envy-cycles are formed.
He, Procaccia and Psomas show a polytime algorithm that attains cumulative-EF1 for two agents with positive valuations. It is similar to the envy-graph algorithm except that, when envy-cycles occur, only partial bundles are exchanged, in a way that maintains the cumulative-EF1 guarantee. An analogous algorithm works with negative valuations.
With three or more agents, it may be impossible to attain cumulative-EF1 without reallocating previously-allocating items. There is an example with three agents and 23 goods; the example does not extend to chores, so the case of chores and 3 or more agents remains open.
Elkind, Lam, Latifian, Neoh and Teh show some more cases in which a cumulative-EF1 allocation always exists, and can be found in polytime:

There are two types of items.
All agents have generalized binary valuations ; this generalizes both identical valuations and binary valuations. The algorithm is greedy: the next item is given to an agent with the smallest value. They prove that this agent is always unenvied. Note that the algorithm does not require any information about the future, besides the information that the agents' valuations are identical.
The preferences are single-peaked or single-dipped. This means that, over time, the values of goods for every agent increases and then decreases. The algorithm is round-robin item allocation.
There are two rounds.

On the other hand, they show that a cumulative-EFx allocation might not exist for either goods or chores, even for two agents with identical valuations and two types of items, and even when the values are increasing with time or decreasing with time.
For the general case, they prove several hardness results regarding cumulative-EF1:

For goods, it is NP-hard to decide if a given instance has a cumulative-EF1 allocation, even for n=3 agents.
For chores, it is NP-hard to decide if a given instance with a given partial cumulative-EF1 allocation has a continuation that is cumulative-EF1, even for n=4 agents.

There are also several hardness results regarding combining cumulative-EF1 with Pareto-efficiency:

For either goods or chores, for any n ≥ 2, there might not exist an allocation that is both TEF1 and Pareto-efficient.
Determining the existence of such an allocation is NP-hard even for n=2 agents.
SImilarly, determining the existence of an allocation that is both TEF1 and utilitarian-optimal, or more generally, maximizes p-mean welfare, is NP-hard even for n=2 agents.

Cookson, Ebadian and Shah' study temporal fair division with an additional requirements of ordinal fairness. They show polytime algorithms for the following combinations of features:

Overall PROP1 and Per-day ordinal-EF1.' The algorithm first transforms the instance such that, in each day, all agents have the same ranking over the items; then they use the Biswas-Barman algorithm. They prove that the PROP1 guarantee is maintained under the identical-order transformation.
Cumulative EF1 and Per-day ordinal-EF1 for two agents..
Overall ordinal-EF1 and Per-day ordinal-EF1 for n agents with identical rankings.''''''

Summary of results

The following table summarizes results for indivisible item allocation. Results are presented by the characteristics of the single-day problem, and the temporal aspects.
Information on future can be:0 None - totally uninformed algorithm.1 Max value - algorithm has minimal information - only the maximum value of an item for an agent ; this setting is also sometimes called online fair division.1 Sum values - algorithm knows the sum of values for each agent ; 2 Multiset - algorithm knows the multiset of values for each agent.3 Complete - algorithm has complete information.
The Adversary models are based on Zeng and Psomas:1 IID - valuations are drawn independently at random from an identical distribution ;5 Adaptive - valuations are adversarial and the adversary at each day can see the algorithm decisions at previous days.