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

• 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.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.

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., 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.
• 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(n^1/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 occured 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-round 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.

Non-repeated temporal division

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.

He, Procaccia and Psomas 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).

With three or more agents, it may be impossible to attain cumulative-EF1 without reallocating previously-allocating items (moreover, Ω(T) reallocations might be required). 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 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);
• 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). This condition generalizes the condition of identical rankings where the rankings are monotonically-increasing or monotonically-decreasing with time.
• There are two rounds (with possibly multiple items per round).

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).

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 (up to some time t) has a continuation that is cumulative-EF1, even for n=4 agents.

And 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.

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 called online fair division.
• 2 Distributional - algorithm knows the distribution from which the valuations are drawn.
• 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:

• 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		1	n	Binary	-		1 Max value	0 Different	5 Adaptive	ex-ante EF.			Truthful. Not ex-post EFc for any c.
BALANCED LIKE		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		1	n	Additive	-		1 Max value	0 Different	5 Adaptive	Envy ≤ sqrt(T/n).	-		Envy bound is tight.
Derandomized LIKE with batches		m	n	Additive	-		1 Max value	0 Different	5 Adaptive	Envy ≤ sqrt(T/(mn)).	-		Envy bound is tight.
Online Stripe Discrepancy		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		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]		1	n	Additive	-		1 Max value	0 Different	4 Non-adaptive (hence also 5)	Envy in o(T); 1/n-PE.	-		Impossible.
Envy Balancing		1	2	Additive	-		3 Complete	0 Different	5 Adaptive	EF1	-		Requires no adjustments.
Fractional Item Rounding		1	2	Additive	-		0 None	0 Different	5 Adaptive	EF1	-		Requires at most T adjustments.
Double Round Robin		1	n	Additive	-		0 None	0 Different	5 Adaptive	EF1	-		Requires O(T3/2) adjustments.
*** [Impossibility result]		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		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		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		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		n	n	Additive	EF1 (trivial)		3 Complete	1 Identical	-	EF1	None		Biswas-Barman algorithm for partition-matroid constraints