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.

Uses your system voice; voice and rate in settings.

≈ 7 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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

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.

Jiang, Kulkarni and Singla 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 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 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. Identical independent agents: the adversary picks a probability distribution D 0 . On each round t, v it is drawn independently from D 0 .

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 . 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. Non-adaptive adversary: After seeing the algorithm code, the adversary picks the valuations of all n agents to all T items. 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 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 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 impossibility result for EF1, as for n=2 these notions are similar.

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.

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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1365862200 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001365862200 · captured 2026-07-24 · ledger · version history

Cite this page as: encyclopegia.org, “Online fair division”, snapshot enwiki-001365862200. https://encyclopegia.org/a/online-fair-division

Sources cited in this revision

20 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.