Fair division among groups
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 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.
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 <math>({2c+1\choose c+1}, {2c+1 \choose c+1})</math>. 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 <math>O(\sqrt{n})\geq c \geq \Omega(\sqrt{n/k^3})</math>. The same is true for proportionality up to c items. For consensus division the bounds are <math>O(\sqrt{n})\geq c \geq \Omega(\sqrt{n/k})</math>. 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 <math>\Omega(n \log n)</math>, 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 <math>(1-1/2^{c-1})</math>-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 <math>(1-1/2^{c})</math>. For <math>c=2</math>, 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.