Temporal fair division

Temporal fair division^[1][2] 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 rooms and equipment between departments in a university, where the rooms and 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:^[1]

• 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 impies 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:

1. Guarantee Local-F and Overall-F simultaneously;
2. Guarantee Cumulative-F alone or in combination with Local-F;
3. 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.^{[2]: Lem.3.1}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^[3] 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^[4] 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,^[4]: 6 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.^[5]

Time-dependent valuations and Overall-EF1

Caragiannis and Narang^[4] 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., v_i(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.^[4]: Sec.3
• For agents with identical non-negative valuations, there is a polytime algorithm that computes an overall-EF1 allocation.^[4]: Alg.1
• 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.^{[4]: Alg.2,3} 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(n^1/3 T)), by reduction from maximum independent set.^[4]: Sec.5
• 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.^[4]: Sec.6

Past allocations, Cumulative-EF1 and Pareto-efficiency

Micheel and Wilczynski^[6] 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:^[6]: Sec.4 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):^[6]: Sec.5 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^[6]: Sec.6: 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.^{[2]: Thm.5.2}

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^[3] 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^[1] 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.^{[1]: Sec.4.3}
• For n agents: per-day ordinal-EF1 and overall ordinal-PROP1^[1]: Sec.6 (cumulative ordinal-EF1 cannot be guaranteed even with identical preferences.^[1]: App.E)

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.^{[clarification needed]} Still, the envy-graph procedure works when agents have identical valuations, as in this case no envy-cycles are formed.

He, Procaccia and Psomas^[7] show a polytime algorithm that attains cumulative-EF1 for two agents with positive valuations (goods). 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 (chores).^{[2]: Sec.3.1}

With three or more agents, it may be impossible to attain cumulative-EF1 without reallocating previously-allocating items (moreover, Ω(T) reallocations might be required).^[7] 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.^[2]: App.A

Elkind, Lam, Latifian, Neoh and Teh^{[2]: Sec.3.2} show some more cases (in addition to the case of two agents) in which a cumulative-EF1 (TEF1) allocation always exists, and can be found in polytime:

• There are two types of items (goods or chores).
• All agents have generalized binary valuations (goods or chores); 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 (as in the envy-graph algorithm). 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 (for goods) or single-dipped (for chores). This means that, over time, the values of goods for every agent increases and then decreases (for chores it decreases and then increases). The algorithm is round-robin item allocation.
• There are two rounds (with possibly multiple items per round).^{[2]: Thm.5.1}

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 (for goods) or decreasing with time (for chores).^{[2]: Sec.3.1}

For the general case, they prove several hardness results regarding cumulative-EF1:^{[2]: Sec.3.3}

• 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 (up to some time t) 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:^[2]: Sec.4

• 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^[1] study temporal fair division with an additional requirements of ordinal fairness (which means that the fairness notion should hold for any additive utility function that is compatible with the ranking). They show polytime algorithms for the following combinations of features:

• Overall PROP1 and Per-day ordinal-EF1.^[1]: Sec.3 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.^[1]: Sec.4(even for two agents, it is impossible to guarantee cumulative ordinal-EF1, and impossible to guarantee simultaneously per-day EF1 and overall ordinal-EF1).
• Overall ordinal-EF1 and Per-day ordinal-EF1 for n agents with identical rankings.^[1]: Sec.5 (even with identical preferences and identical days, cumulative ordinal-EF1 cannot be guaranteed)

Related problems

• Reachability:^[8] Sometimes it is required to move from one fair allocation to another one (e.g. a company redistributes its employees between departments, or a museum reallocates its exhibits among its branches). It is required to do the move gradually, one item at a time, such that the intermediate allocations are fair too.
• Temporal fairness in multiwinner voting:^[9] study notions similar to cumulative-fairness, but in the context of Multiwinner voting. See also Multi-issue voting.
• Fair resource allocation over time:^[10] focuses on max-min fairness.
• Sequential fair allocation:^[11] focuses on the fairness-efficiency curve.
• Dynamic fair division with minimal disruptions.^[12]
• Fair allocation with Latin square constraints.^[13]

Summary of results

The following table summarizes results for indivisible item allocation. Results are presented by the characteristics of the single-day problem (what is done each day), and the temporal aspects (what relates problems solved in different days).

Information on future can be:

• 0 None - totally uninformed algorithm (the online fair division setting).
• 1 Max value - algorithm has minimal information - only the maximum value of an item for an agent (this maximum value is usually normalized to 1); this setting is also sometimes called online fair division.
• 1 Sum values - algorithm knows the sum of values for each agent (equivalently, the sum of values for each agent is normalized to 1);
• 2 Multiset - algorithm knows the multiset of values for each agent (but not their order).
• 3 Complete - algorithm has complete information (the "temporal fair division" setting; if the days are identical, then it is called "repeated fair division").

The Adversary models are based on Zeng and Psomas:^[14]

• 1 IID - valuations are drawn independently at random from an identical distribution (easiest model);
• 5 Adaptive - valuations are adversarial and the adversary at each day can see the algorithm decisions at previous days (hardest model).

Name+Cite		Single-day problem					Temporal aspects						Comments
		#Items	#Agents	Valuations	Per-day fairness		Information on future	Identical days?	Adversary	Overall fairness at round T	Cumulative fairness
LIKE[15]		1	n	Binary	-		1 Max value	0 Different	5 Adaptive	ex-ante EF.			Truthful. Not ex-post EFc for any c.
BALANCED LIKE[15]		1	n	Binary	-		1 Max value	0 Different	5 Adaptive	ex-ante EF, ex-post EF1.			Truthful for n≥2 but not for n≥3.
Derandomized LIKE[16]		1	n	Additive	-		1 Max value	0 Different	5 Adaptive	Envy ≤ sqrt(T/n).	-		Envy bound is tight.
Derandomized LIKE with batches[16][17]: Sec.3.1-3.2		m	n	Additive	-		1 Max value	0 Different	5 Adaptive	Envy ≤ sqrt(T/(mn)).	-		Envy bound is tight.
Online Stripe Discrepancy[18]		1	2	Additive	-		1 Max value	0 Different	1 IID	Envy ≤ T^(const/log log T), w.h.p.	-		Holds even for ordinal envy.
Clique Rounding[14]: Alg.3 [17]: Sec.4		1	n	Additive	-		1 Max value	0 Different	3 Correlated (hence also 1,2)	Ex-post PE; every pair (i,j) satisfies either EF1, or EF w.h.p.	-		Fairness guarantee cannot be improved even for adversary 1 (IID).
*** [Incompatibility result][14]: Sec.5 [17]: Sec.3.3		1	n	Additive	-		1 Max value	0 Different	4 Non-adaptive (hence also 5)	Envy in o(T); 1/n-PE.	-		Impossible.
Envy Balancing[19]: Alg.2		1	2	Additive	-		3 Complete	0 Different	5 Adaptive	EF1	-		Requires no adjustments.
Fractional Item Rounding[19]: Alg.1		1	2	Additive	-		0 None	0 Different	5 Adaptive	EF1	-		Requires at most T adjustments.
Double Round Robin[19]: Alg.3		1	n	Additive	-		0 None	0 Different	5 Adaptive	EF1	-		Requires O(T3/2) adjustments.
*** [Impossibility result][19]: Thm.4.2		1	n	Additive	-		3 Complete (hence also 0,1,2)	0 Different	4 Non-adaptive (hence also 5)	EF1	-		Requires Omega(T) adjustments.
Repeated fair allocation for two agents[20]: Sec.4		m	2	Additive	Weak-EF1		3 Complete	1 Identical	-	EF+PE (when T is even).			Per-round EF1 for T=2 days
Repeated fair allocation for n agents[20]: Sec.3		m	n	Additive	None		3 Complete	1 Identical	-	EF or PROP+PE (when T is a multiple of n).			Impossible when T is not a multiple of n. EF+PE impossible for n>2.
Repeated matching - time-dependent valuations[21]		n	n	Additive; Item value for i can depend on number of times it is used by i.	EF1 (trivial)		3 Complete	1 Identical	-	EF1	None
Repeated matching[21]		n	n	Additive	EF1 (trivial)		3 Complete	1 Identical	-	EF1	None		Biswas-Barman algorithm for partition-matroid constraints
Envy-graph[2]: Sec.3.2		m	n	Additive, Generalized-binary	None		0 None (hence also 1, 2, 3)	0 Different	-	EF1			There is always an unenvied agent; no need to remove cycles.
*** [Impossibility result][22]: Sec.3		1	≥ 2	Additive	-		0 None	0 Different	5 Adaptive	EF1	-		Any multiplicative approximation of EF1 is impossible
*** [Impossibility result][22]: Sec.3		1	2	Additive	-		0 None	0 Different	5 Adaptive	PROP1	-		PROP1 is impossible
Satisficing algorithm[22]: Sec.4		1	n	Additive	-		1 Sum values	0 Different	5 Adaptive	PROP1; EF1 for n=2	-		EFx impossible for n≥2; EF1 impossible for n≥3.
Picking-sequence algorithm[22]: Sec.5		1	n	Additive	-		2 Multiset	0 Different	5 Adaptive	Every share-based notion; and EFx for n=2	-		Cannot guarantee EFx for n≥3.