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. 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 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 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 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 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. Cheze 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 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 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 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 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 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 have initiated the study of the food bank problem. They study two simple mechanisms for this setting:
… excerpt ends here. Continue reading the full article.
