Search in Co-Wiki

Temporal fair division

game-theory 2093 tokens 6 outbound links

Temporal fair division

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:

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.

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:

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

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-freeness|envy-free]] (EF), and a sequence that is overall [[proportional-item-allocation|proportional]] and [[pareto-efficiency|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 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). 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: study notions similar to cumulative-fairness, but in the context of Multiwinner voting. See also Multi-issue voting. * Fair resource allocation over time: focuses on max-min fairness. * Sequential fair allocation: focuses on the fairness-efficiency curve. * Dynamic fair division with minimal disruptions**. * Fair allocation with Latin square constraints.

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:

The Adversary models are based on Zeng and Psomas:

References