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 (or set of resources) 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 (EF), envy-freeness up to one item (EF1), proportionality (PROP), and so on. F can be generalized to temporal fair division in three different ways:
Local ("per-day" or "per-round") - for each day t, the allocation in day t should satisfy F; Cumulative ("up-to each day" or "temporal") - 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 (non-temporal) 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 (essentially "split" each day into k consecutive days), 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 (maximizing the sum of utilities) is NP-hard for T ≥ 3, by reduction from 3-dimensional matching (for T=1 it is equivalent to maximum-weight perfect matching, which is polynomial). However, when the valuations are monotone w.r.t. time (i.e., vi(g,t) either increases with t or decreases with t), 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 {0, 1, 2, n-1}, 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(min(n1/3 T)), 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 {0, 1, 2, n-2, n-1}, 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 (which they call "repeated house allocation"). 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 (not just at the end). 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 (in addition to any number of past steps), then deciding whether a mirror-EF and PO allocation exists is polynomial. The same holds if there are at most two future steps (in addition to any number of past steps), and the agents have the same preferences. But if there are two or more future steps (even with no past steps), and agents have different preferences, then the decision problem is NP-complete, by reduction from exact-3-cover. Equal treatment of equals (ETE): 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 (by reduction from the partition problem). 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(T/2). We can find it by running round robin item allocation for ceiling(T/2) rounds in one order, and for floor(T/2) 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(T/2) rounds. Deciding if there exists an allocation with max number of envious rounds at most T/3 is NP-hard (in particular, if there are 3 future rounds, then deciding if there exists an allocation with max number of envious rounds at most 1 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 (local) fairness. They consider two settings: the number of rounds can be either fixed in advance, or variable (can be chosen by the algorithm). The prove that:
When the number of rounds is fixed (T), if T is a multiple of n, then there is always a sequence that is overall envy-free (EF), and a sequence that is overall proportional and Pareto-efficient (PROP+PE). In contrast, if T is not a multiple of n, then there might not exist an overall-PROP sequence (this holds in particular for the one-shot division setting T=1). 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 (can be chosen by the algorithm), for any n, there always exists a sequence that is overall EF+PO and per-round PROP[1,1] (if there are only goods or only chores, then PROP[1,1] becomes PROP1). They do not give an upper bound on the number of rounds required. Cookson, Ebadian and Shah strengthen their results to ordinal fairness (fairness that holds for any utility functions compatible with the rankings). 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 (cumulative ordinal-EF1 cannot be guaranteed even with identical preferences.)
Different days The more general case of temporal division is when the items in each day may be different (but it still known in advance what items are coming). 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.