Fair division among groups

Several siblings inherited some houses from their parents and have to divide them. Each sibling has a family, whose members may have different opinions regarding which house is better.
A partnership is dissolved, and its assets should be divided among the partners. The partners are firms; each firm has several stockholders, who might disagree regarding which asset is more important.
The university management wants to allocate some meeting-rooms among its departments. In each department there are several faculty members, with differing opinions about which rooms are better.
Two neighboring countries want to divide a disputed region among them. The citizens in each country differ on which parts of the region are more important. This is a common obstacle to resolving international disputes.
The "group of agents" may also represent different conflicting preferences of a single person. As observed in behavioral economics, people often change their preferences according to different frames of mind or different moods. Such people can be represented as a group of agents, each of whom has a different preference.

In all the above examples, the groups are fixed in advance. In some settings, the groups can be determined ad-hoc, that is, people can be grouped based on their preferences. An example of such a setting is:

Some 30 people want to use the local basketball court. Each game involves 10 players with different preferences regarding which time is better. It is required to partition the time of day into 3 parts and partition the players into 3 groups and assign a group to each time-slot.

Fairness criteria

Common fairness criteria, such as proportionality and envy-freeness, judge the division from the point-of-view of a single agent, with a single preference relation. There are several ways to extend these criteria to fair division among groups.

Unanimous fairness requires that the allocation be considered fair in the eyes of all agents in all groups. For example:

A division is called unanimously-proportional if every agent in every group values his/her group's share as at least 1/k of the total value, where k is the number of groups.
A division is called unanimously-envy-free if every agent in every group values his/her group's share at least as much as the share of any other group.

Unanimous fairness is a strong requirement, and often cannot be satisfied.

Aggregate fairness assigns to each group a certain aggregate function, such as: sum, product, arithmetic mean or geometric mean. It requires that the allocation be considered fair according to this aggregate function. For example:

A division is called average-proportional if, for each group, the arithmetic mean of the agents' values to the group share is at least 1/k of the total value.
A division is called product-envy-free if, for each group, the product of agents' values of the group share is at least the product of their values of the share of any other group.

Democratic fairness requires that, in each group, a certain fraction of the agents agree that the division is fair; preferredly this fraction should be at least 1/2. A practical situation in which such requirement may be useful is when two democratic countries agree to divide a certain disputed land among them, and the agreement should be approved by a referendum in both countries.

Unanimous-fairness implies both aggregate-fairness and democratic-fairness. Aggregate-fairness and democratic fairness are independent - none of them implies the other.

Pareto efficiency is another important criterion that is required in addition to fairness. It is defined in the usual way: no allocation is better for at least one individual agent and at least as good for all individual agents.

5 more chapters are free with a Lably account.

Results for divisible resources

In the context of fair cake-cutting, the following results are known (where k is the number of groups, and n is the number of agents in all groups together).

Unanimous fairness: Unanimous-proportional and unanimous-envy-free allocations always exist. However, they may be disconnected: at least n connected components might be required. With two groups, n components are always sufficient. With k>2 groups, O(n log k) components are always sufficient for a unanimous-proportional allocation, and O(n k) components are always sufficient for a unanimous-envy-free allocation. It is an open question whether or not n components are always sufficient.
Aggregate fairness: Average-proportional and average-envy-free allocations always exist, and require only k connected components (that is, each group may get a connected piece). However, they cannot be found using a finite algorithm in the Robertson–Webb query model.
Democratic fairness: 1/2-democratic proportional and 1/2-democratic envy-free allocations always exist. With two groups, there exist such allocations that are also connected, and they can be found in polynomial time. With k>2 groups, connected 1/2-democratic fair allocations might not exist, but the number of required components is smaller than for unanimous-proportional allocations.
Fairness and efficiency: All three variants of proportionality are compatible with Pareto-efficiency for any number of groups. Unanimous-envy-freeness is compatible with Pareto-efficiency for 2 groups, but not for 3 or more groups. 1/2-democratic envy-freeness is compatible with Pareto-efficiency for 2 groups, but not for 5 or more groups. It is open whether they are compatible for 3 or 4 groups.

The division problem is easier when the agents can be grouped ad-hoc based on their preferences. In this case, there exists a unanimous envy-free connected allocation for any number of groups and any number of agents in each group.

Unanimous proportionality and exact division

In an exact division (also called consensus division), there are n agents, and the goal is to partition the cake into k pieces such that all agents value all pieces at exactly 1/k. It is known that an exact division with n(k-1) always exists. However, even for k=2, finding an exact division with n cuts is FIXP-hard, and finding an approximate exact division with n cuts is PPA-complete (see exact division for more information). It can be proved that unanimous-proportionality is equivalent to consensus division in the following sense:

For every n and k, a solution to unanimous-proportional division among n(k-1)+1 agents grouped into k families implies a solution to consensus division among n agents with k pieces. In particular, it implies that unanimous-proportional division requires at least n-1 cuts (n components), finding a unanimous-proportional division with n-1 cuts is FIXP-hard, and finding an approximate unanimous-proportional division with n-1 cuts is PPA-hard.
For every n and k, a solution to exact-division among n agents and k pieces implies a solution to unanimous-proportional division among n+1 agents grouped into k families. In particular, it implies that exact unanimous-proportional division can be done with (n-1)(k-1) cuts, and that finding an approximate unanimous-proportional division is in PPA. The number of cuts is tight for k=2 families but not for k>2.

Results for indivisible items

In the context of fair item allocation, the following results are known.

Unanimous approximate maximin-share fairness:

When there are two groups, a positive multiplicative approximation to MMS-fairness can be guaranteed if-and-only-if the numbers of agents in the groups are (1,n-1) or (2,2) or (2,3). The positive results are attainable by polynomial-time algorithms. In all other cases, there are instances in which at least one agent with a positive MMS gets a zero value in all allocations.
When there are three or more groups, a positive multiplicative approximation to MMS-fairness can be attained if k-1 groups contain a single agent; in contrast, if all groups contain 2 agents and one group contains at least 5 agents, then no positive approximation is possible.
Results on ordinal approximation of maximin-share are more positive.

Unanimous approximate envy-freeness:

When there are two groups of agents with binary additive valuations, a unanimously-EF1 allocation exists if the group sizes are (1,5) or (2,3), but might not exist if the group sizes are (1,6) or (2,4) or (3,3). In general, an EFc allocation might not exist if the group sizes are ((2c+1c+1),(2c+1c+1)). Note that, with binary valuations, EF1 is equivalent to EFX, but weaker than EFX0. A unanimously-EFX0 allocation might not exist if the group sizes are (1,2); this is in contrast to the situation with individual agents, that is, group sizes (1,1), where an EFX0 allocation always exists even for monotone valuations.
- It is NP-hard to decide if a given instance admits a unanimously-EF1 allocation.
When there are two groups of agents with responsive valuations (a superset of additive valuations), a unanimously-EF1 balanced allocation exists if the group sizes are (1,2). If a certain conjecture on Kneser graphs is true, then a unanimously-EF1 balanced allocation exists also for group sizes (1,4), (2,3) and arbitrary monotone valuations. A unanimously-EFX allocation might not exist if the group sizes are (1,2).
For two ad-hoc groups, with any number of agents with arbitrary monotone valuations, there exists a unanimously-EF1 allocation. There also exists a balanced partition of the agents and a unanimously-EF1 balanced allocation of the goods. The EF1 cannot be strengthened to EFX even with additive valuations.
For k ad-hoc groups, with any number of agents with additive valuations, there exists a unanimously-PROP*1 allocation.
For n agents partitioned arbitrarily into k groups, there always exists an allocation that is envy-free up to c items, where $O (\sqrt{n}) \geq c \geq Ω (\sqrt{n / k^{3}})$ . The same is true for proportionality up to c items. For consensus division the bounds are $O (\sqrt{n}) \geq c \geq Ω (\sqrt{n / k})$ . All bounds are asymptotically tight when the number of groups is constant. The proofs use discrepancy theory.

Unanimous envy-freeness with high probability:

When all k groups contain the same number of agents, and their valuations are drawn at random, an envy-free allocation exists with high probability if the number of goods is in Ω(nlog⁡n), and can be attained by a greedy algorithm that maximizes the sum of utilities.
- The results can be extended to two groups with different sizes.
- There is also a truthful mechanism that attains an approximately-envy-free allocation with high probability.
If the number of goods is in less than n, then with high probability, an envy-free allocation does not exist.

Democratic fairness:

For two groups with binary additive valuations (with any number of agents), there always exists a 1/2-democratic envy-free-except-1 allocation. The constant 1/2 is tight even if we allow envy-free-except-c allocation for any constant c. The same is true also for proportionality-except-c. A different fairness notion, that can be guaranteed to more than 1/2 of the agents in each group, is the ordinal maximin-share approximation. For every integer c, there exists a (1−1/2c−1)-democratic 1-out-of-c MMS-fair allocation. These allocations can be found efficiently using a variant of round-robin item allocation, with weighted approval voting inside each group. The upper bound on the fraction of agents that can be guaranteed 1 of their best c items (a property weaker than 1-out-of-c MMS) is (1−1/2c). For c=2, the lower bound for 1-out-of-best-c allocation can be improved from 1/2 to 3/5; it is an open question whether the upper bound of 3/4 can always be attained.
- It is NP-hard to decide if a given instance admits an allocation that gives each agent a positive utility.
For two groups with general monotone valuations, there always exists a 1/2-democratic envy-free-except-1 allocation, and it can be found by an efficient algorithm.
For three or more groups with binary additive valuations, there always exists a 1/k-democratic envy-free-except-1 allocation; with general monotone valuations, there always exists a 1/k-democratic envy-free-except-2 allocation. The factor 1/k is tight for envy-free-except-c allocation for any constant c. If envy-freeness is relaxed to proportionality or maximin-share, then similar guarantees can be attained using a polynomial-time algorithm. For groups with additive valuations, a variant of round-robin item allocation can be used to find a 1/3-democratic 1-out-of-best-k allocation.

Group fair division of items and money

In the context of rental harmony (envy-free division of rooms and rent), the following results are known.

Unanimous envy-freeness (called strong envy-freeness in the paper) may not exist when the cost-sharing policy is equal or proportional, but always exists with free cost-sharing policy. Moreover, a unanimously-envy-free allocation with free cost-sharing that maximizes the total rent can be found in polynomial time.
- With ad-hoc groups, unanimous envy-freeness exists even with equal cost-sharing policy.
Average envy-freeness (called aggregate envy-freeness in the paper) always exists when the cost-sharing policy is equal or proportional or free.

Fair division of ticket lotteries

A practical application of fair division among groups is dividing tickets to parks or other experiences with limited capacity. Often, tickets are divided at random. When people arrive on their own, a simple uniformly-random lottery among all candidates is a fair solution. But people often come in families or groups of friends, who want to enter together. This leads to various considerations in how exactly to design the lottery. The following results are known:

For the setting in which all group members are identified in advance, the Group Lottery mechanism orders groups uniformly at random, and processes them sequentially as long as there is available capacity. This natural mechanism might be unfair and inefficient; there are some better alternatives.
If agents may request multiple tickets without identifying members of their group, the Individual Lottery mechanism orders agents uniformly at random and awards each their request as long as there is available capacity. This common mechanism might yield arbitrarily unfair and inefficient outcomes. The Weighted Individual Lottery is an alternative mechanism in which the processing order is biased to favor agents with smaller requests. It is approximately fair and approximately efficient.
The Iterative Probability Maximization algorithm finds a lottery that maximizes the smallest utility (based on the egalitarian rule and the leximin order). It is group strategyproof, and attains a 1/2-factor approximation of the maximum utilization. It is also Pareto-efficient, envy-free and anonymous. Its properties are maximal in the sense that it is impossible to improve one property without harming another one.

Group envy-freeness is a fairness criterion for fair division among individual agents. It says that, after each individual agent gets his private share, no coalition of agents envies another coalition of the same size.
Club good is a resource that is consumed simultaneously by all members in a single group ("club"), but is excluded from members of other groups. In the group fair division problem, all allocated goods are club goods in the group they are allocated to.
Agreeable subset is a subset of items that is considered, by all people in a certain group, to be at least as good as its complement.