Fair division among groups


Fair division among groups 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 consume 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. 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.

Results for divisible resources

In the context of fair cake-cutting, the following results are known.
  • 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 components are always sufficient for a unanimous-proportional allocation, and O 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. 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, 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 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. 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+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, 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 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 or or. 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 or, but might not exist if the group sizes are or or. In general, an EFc allocation might not exist if the group sizes are. 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 ; this is in contrast to the situation with individual agents, that is, group sizes, 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 unanimously-EF1 balanced allocation exists if the group sizes are. If a certain conjecture on Kneser graphs is true, then a unanimously-EF1 balanced allocation exists also for group sizes, and arbitrary monotone valuations. A unanimously-EFX allocation might not exist if the group sizes are.
  • 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. The same is true for proportionality up to c items. For consensus division the bounds are. 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, 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, 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 -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 is. For, 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.