Fair division among groups

Fair division among groups (or families) is a class of fair division problems, in which the resources are allocated among groups of agents, rather than among individual agents. After the division, all members in each group enjoy the same share, but they may have different preferences; therefore, different members in the same group might disagree on whether the allocation is fair or not. Some examples of group fair division settings are:

• 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. For example:

• 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 acccording 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 sum 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.

Group fair division of 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 not known whether n components are 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 not known whether it is 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.

Group fair division of indivisible items

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

• Unanimous maximin-share fairness: when there are two groups, a positive multiplicative approximation to MMS-fairness can be attained 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 on positive approximation is possible.
• Asymptotic unanimous envy-freeness: 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 $\Omega (n\log 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. However, 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/2^{c-1})$-democratic 1-out-of-c MMS-fair allocation. These allocations can be found efficiently using a variant of round-robin item allocation.
  • 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.

See also

• Agreeable subset