Online fair division

Online fair division is a class of fair division problems in which the resources, or the people to whom they should be allocated, or both, are not all available when the allocation decision is made.^[1] Some situations in which not all resources are available include:

• Allocating food donations to charities (the "food bank" problem). Each donation must be allocated immediately when it arrives, before future donations arrive.
• Allocating donated blood or organs to patients. Again, each donation must be allocated immediately, and it is not known when and what future donations will be.

Some situations in which not all participants are available include:

• Dividing a cake among people in a party. Some people come early and want to get a piece of cake when they arrive, but other people may come later.
• Dividing the rent and rooms among tenants in a rented apartment, when one or more of them are not available during the allocation.

The online nature of the problem requires different techniques and fairness criteria than in the classic, offline fair division.

Online arrival of people

The party cake-cutting problem

Walsh^[2] studies an online variant of fair cake-cutting, in which agents arrive and depart during the division process, like in a party. Well-known fair division procedures like divide and choose and the Dubins-Spanier moving-knife procedure can be adapted to this setting. They guarantee online variants of proportionality and envy-freeness. The online version of divide-and-choose is more robust to collusion, and has better empirical performance.

The sequential fair allocation problem

Sinclair, Jain, Bannerjee and Yu^[3][4] study allocation of divisible resources when individuals arrive randomly over time. They present an algorithm that attains the optimal fairness-efficiency threshold.

The secretive agent problem

Several authors studied fair division problems in which one agent is "secretive", i.e., unavailable during the division process. When this agent arrives, he is allowed to choose any part of the resource, and the remaining n-1 parts should be divided among the remaining n-1 agents such that the division is fair. Note that divide and choose satisfies these requirements for n=2 agents, but extending this to 3 or more agents is non-trivial. The following extensions are known:

• Meunier and Su^[5] show that there always exists an envy-free cake-cutting among any number of agents, when there is a single secretive agent.
• Frick, Houston-Edwards and Meunier^[6] show that there always exists an envy-free allocation of rooms and rent (also called rental harmony) when there is a single secretive agent. The result holds for very general class of the tenants' preferences, including quasilinear valuations, "miserly tenants", and more.^[7]
• Cheze^[8] shows a polynomial-time algorithm for connected proportional cake-cutting among any number of agents, when there is a single secretive agent. The algorithm is based on the Even–Paz protocol and uses O(n log n) queries.
• Arunachaleswaran, Barman and Rathi^[9] show a polynomial-time algorithm for rental harmony when there are n-1 agents with quasilinear utilities, and the n-th agent is secretive. They also show efficient algorithms for almost envy-free (EF1) item allocation and ε-approximate envy-free cake-cutting.

The cake redivision problem

The cake redivision problem^[10] is a variant of fair cake-cutting in which the cake is already divided in an unfair way (e.g. among a subset of the agents), and it should be re-divided in a fair way (among all the agents) while letting the incumbent owners keep a substantial fraction of their present value. The model problem is land reform.

Online arrival of resources

When resources arrive online, we have an online variant of fair allocation of indivisible goods. Each time, a single item arrives; each agent declares his/her value for this item; and the mechanism should decide which of the agents should receive it.

Identical valuations

A special case of online item allocation is when all agents have identical valuations. When the valuations are negative (e.g. costs or processing times), this case is equivalent to the online version of min-max identical-machines scheduling; see Online job scheduling.

When the valuations are positive, this case is equivalent to the online version of the max-min job scheduling, often called machine covering. Tan and Wu^[11] present optimal algorithms for three semi-online machine covering problems. They prove that:

• If either the total value or the largest value is known in advance, then the approximation ratio of all algorithms is 1/(n-1).
• If both the total value and the largest value is known in advance, then the approximation ratio of all algorithms is 2/3 when n=3, and 1/(n-2) when n≥4.

These results imply approximation algorithms for maximin-share fair allocation of goods.

Elkind, Lam, Latifian, Neoh and Teh^{[12]: Sec.3.2} present an algorithm that guarantees EF1 for generalized-binary valuations; which generalize both binary and identical valuations. Although their paper assumes that all information on future items is available, this specific does not need future information (it is based on the Envy-graph procedure).

Neoh, Peters and Teh^{[13]: Sec.6} present semi-online algorithms for other fairness notions besides max-min and min-max:

• With identical valuations and information on the sum of valuations, when n=2 it is possible guarantee a multiplicative approximation of to (sqrt(5)-1)/2 EFx, and it is tight; when n≥3 no positive approximation is possible.
• Without any future information, it is impossible to guarantee any positive multiplicative approximation of EFx.

Binary valuations: the Food Bank problem

The Food Bank problem is a special case of online item allocation, in which all agents have binary valuations {0,1}, that is, for each arriving item, every agent states whether he likes the item or not. The model application is a central food bank, which receives food donations and has to allocate each donation to one of the charities who want it. The donations are consumed immediately, and it is not known what donations are going to come next, so the decision must be made based only on the previous donations.

Working with Foodbank Australia, Aleksandrov, Aziz, Gaspers and Walsh^[14] have initiated the study of the food bank problem. They study two simple mechanisms for this setting:

• LIKE: each item is given uniformly at random to one of the agents who likes it. It is strategyproof and envy-free ex-ante, but does not guarantee even approximate envy-free ex-post. With binary valuations, it attains the optimal egalitarian and utilitarian social welfare. With additive valuations, its expected egalitarian and utilitarian social welfare are least 1/n of the optimal values attainable by an offline algorithm. The same is true whether the agents are sincere or strategic (i.e., its price of anarchy is n).
• BALANCED-LIKE: each item is given uniformly at random to one of the agents who likes it, from among those who received the least number of items so far. It is envy-free ex-ante, and guarantees EF1 ex-post when all agents have binary valuations. It is strategyproof for two agents with binary valuations, but not strategyproof for three or more agents even with binary valuations. When agents bid sincerely, with binary valuations, it attains the optimal egalitarian and utilitarian social welfare. With additive valuations, its expected egalitarian and utilitarian social welfare do not attain any constant-factor approximation of the offline optimal values, even with two agents. When agents bid strategically, even with binary valuations, its price of anarchy is n.

Additive valuations: Online Item Allocation

In a more general case of the food bank problem, agents can have additive valuations. Due to the online nature of the problem, it may be impossible to attain some fairness and efficiency guarantees that are possible in the offline setting. In particular, Kahana and Hazon^[15] prove that no online algorithm always finds a PROP1 (proportional up to at most one good) allocation, even for two agents with additive valuations. Moreover, no online algorithm always finds any positive approximation of RRS (round-robin share).

Benade, Kazachkov, Procaccia and Psomas^[16][17] study another fairness criterion – envy-freeness. Define the envy of agent i at agent j as the amount by which i believes that j's bundle is better, that is, ${\displaystyle \max(0,V_{i}(X_{j})-V_{i}(X_{i}))}$. The max-envy of an allocation is the maximum of the envy among all ordered agent pairs. They assume that the values of all items are normalized to [0,1]; equivalently, the highest value of an item to each agent is known in advance. In the offline setting, it is easy to attain an allocation in which the max-envy is at most 1, for example, by the round-robin item allocation (this condition is called EF1). However, in the online setting, the envy might grow with the number of items (T). Therefore, instead of EF1, they aim to attain vanishing envy—the expected value of the max-envy of the allocation of T items should be sublinear in T (assuming the value of every item is between 0 and 1). They show that:

• The LIKE algorithm (allocating each item uniformly at random) attains vanishing envy – the envy after T items is in ${\displaystyle O({\sqrt {T/n}})}$.
• There is a deterministic algorithm with a similar envy-bound, using the method of pessimistic estimators.
• For any n ≥ 2 and r < 1, there exists an adaptive adversary (an adversary who chooses the valuations of item t after seeing the allocation at time t-1) such that any algorithm must have envy after T rounds in Ω((T/n)^r/2). In particular, in contrast to the case of binary valuations, no algorithm can guarantee EF1.
• They also study a more general setting in which the items come in batches of m each time, rather than 1 at a time. In this case, there is a deterministic algorithm with envy in ${\displaystyle O({\sqrt {T/(mn)}})}$.

Jiang, Kulkarni and Singla^[18] improve the bound for the case of n=2 agents, when the values are random (rather than adversarial). They reduce the problem to the problem of Online Stripe Discrepancy, which is a special case of discrepancy of permutations, with two permutations and online item arrival. They show that their algorithm for Online Stripe Discrepancy attains envy in ${\displaystyle O(T^{c/\log \log T})}$, for some universal constant c, with high probability (that depends on c). Their algorithm even bounds a stronger notion of envy, which they call ordinal envy: it is the worst possible cardinal envy that is consistent with the item ranking.

Zeng and Psomas^[19][17] study the trade-off between efficiency and fairness under five adversary models, from weak to strong. Below, v_it denotes the value of the item arriving at time t to agent i.

1. Identical independent agents: the adversary picks a probability distribution D₀. On each round t, v_it is drawn independently from D₀.
2. Different independent agents: The adversary picks a probability distribution D_i for each agent i. On each round t, v_it is drawn independently from D_i.
3. Correlated agents: The adversary picks a joint probability distribution D. On each round t, the vector (v_1t, ..., v_nt) is drawn independently from D.
4. Non-adaptive adversary: After seeing the algorithm code, the adversary picks the valuations of all n agents to all T items.
5. Adaptive adversary: After seeing the algorithm code, and after seeing the allocation of the first t-1 items, the adversary picks the valuations of item t (In ^[16] this is the model).

For adversary 3 (hence also 2 and 1), they show an allocation strategy that guarantees, to each pair of agents, either EF1, or EF with high probability, and in addition, guarantees ex-post Pareto efficiency. They show that the "EF1 or EF w.h.p." guarantee cannot be improved even for adversary 1 (hence also for 2 and 3). For adversary 4 (hence also 5), they show that every algorithm attaining vanishing envy can be at most 1/n ex-ante Pareto-efficient.

Neoh, Peters and Teh^[13] study the effect of future information on the ability to attain a fair division. They prove:

• With no information at all (i.e., without knowing the highest value for each agent), no multiplicative approximation of EF1 is possible for n ≥ 2. Moreover, PROP1 is impossible for n = 2 even when knowing the highest value for each agent; this follows from the ^[16] impossibility result for EF1, as for n=2 these notions are similar.^{[13]: Sec.3}
• When the sum of all values for each agent is known (they call it "normalization information"), there is an algorithm that guarantees EF1 for n=2 agents and PROP1 for any number of agents. However, it is impossible to guarantee EFx or any multiplicative approximation of it for any n≥2, and impossible to guarantee EF1 or any n≥3.^{[13]: Sec.4}
• When the multiset of all values for each agent is known (they call it "frequency predictions"), there is a meta-algorithm that can guarantee every share-based fairness notion (e.g. approximate maximin-share, round-robin share) that can be guaranteed in the one-shot setting. The idea is that every share-based fairness notion can be attained by a picking sequence when all agents have the same ranking of the objects, and every such picking sequence can be implemented online if the multiset of all values is known. This algorithm can be adapted to guarantee EFx for n=2 agents. However, it is impossible to guarantee EFx for n ≥ 3.^{[13]: Sec.5}

The costly reallocation problem

In some cases, items that were previously allocated may be reallocated, but reallocation is costly, so the number of adjustments should be as small as possible. An example is the allocation of expensive scientific equipment among different university departments. Each piece of equipment is allocated as soon as it arrives, but some previously allocated equipment may be reallocated in order to attain a fairer overall allocation.

He, Procaccia and Psomas^[20] show that, with two agents, algorithms that are informed about values of future items can attain EF1 without any reallocations (this is actually an instance of temporal fair division), whereas uninformed algorithms require Θ(T) reallocations. With three or more agents, even informed algorithms must use Ω(T) reallocations, and there is an uninformed algorithm that attains EF1 with O(T^3/2) reallocations.

Uncertain supply

In many fair division problems, such as production of energy from solar cells, the exact amount of available resource may not be known at the time the allocation is decided. Buermann, Gerding and Rastegari^[21] study fair division of a homogeneous divisible resource, such as electricity, where the available amount is given by a probability distribution, and the agents' valuations are not linear (for example, each agent has a cap on the amount of the resource he can use; above this cap, his utility does not increase by getting more of the resource). They compare two fairness criteria: ex-post envy-freeness and ex-ante envy-freeness. The latter criterion is weaker (since envy-freeness holds only in expectation), but it allows a higher social welfare. The price of ex-ante envy-freeness is still high: it is at least Ø(n), where n is the number of agents. Moreover, maximizing ex-ante social welfare subject to ex-ante envy-freeness is strongly NP-hard, but there is an integer program to calculate the optimal ex-ante envy-free allocation for a special class of valuation functions – linear functions with a saturation cap.

Uncertain demand

In many fair division problems, there are agents or groups of agents whose demand for resources is not known when the resources are allocated. For example,^[22] suppose there are two villages who are susceptible to power outages. Each village has a different probability distribution over storms:

• In village A, with probability 40%, two houses are hit;
• In village B, with probability 70%, three houses are hit.

The government has two generators, each of which can supply electricity to a single house. It has to decide how to allocate the generators between the villages. Two important considerations are utilization and fairness:

• Utilization is defined as the expected number of houses who need a generator and get it. The utilization is maximized (at 1.4) when both generators are given to village B.
• Fairness is defined as equalizing the difference between the fraction of served houses between the two villages. Here, the fairest allocation is giving a single generator to each village; the fraction is 1/2 in village A and 1/3 in village B, so the difference is 1/6.

Donahue and Kleinberg^[22] prove upper and lower bounds on the price of fairness—the maximum possible utilization, divided by the maximum utilization of a fair allocation. The bounds are weak in general, but stronger bounds are possible for some specific probability distributions that are commonly used to model demand.

Other applications with uncertain demands are allocation of orders in service supply chains,^[23] allocation of aircraft to routes,^[24] allocation of doctors to surgeries,^[25] and more.^{[26][27][28][29]}

Uncertain value

Morgan^[30] studies a partnership dissolution setting, where the partnership assets have the same value for all partners, but this value is not known. Each partner has a noisy signal about the value, but the signals are different. He shows that Divide and choose is not fair – it favors the chooser. He presents another mechanism that can be considered fair in this setting.

See also

• Temporal fair division – similar to online fair division in that the items are allocated in different time-periods, but easier as the set of items arriving each day is known in advance, and the number of time periods (T) is known in advance. Repeated fair division is a special case in which the set of items is the same each day. The challenge comes from the fact that agents have higher expectations: while they are willing 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. That page contains a summary table for both the informed and uninformed settings.
• Resource monotonicity—a property of division rules, guaranteeing that if the same rule is applied to a larger cake and the same population, then all agents are better-off.
• Population monotonicity—a property of division rules, guaranteeing that if the same rule is applied to a smaller population and the same cake, then all agents are better-off.
• Fair resource allocation in a volatile marketplace.^[31]
• Fair allocation of a single object, where the valuations are random.^[32]