Fairness Does Not Imply Satisfaction (Student Abstract)

Andrew Searns, Hadi Hosseini

Introduction

In the field of fair division, the goal is to distribute a set of indivisible items—such as courses, heritage assets, or tasks—among multiple agents as equitably as possible. While "envy-freeness" is often considered the gold standard, it is frequently unattainable when items cannot be split. Consequently, researchers often turn to the Maximin Share Guarantee (MMS). An agent's MMS value is the maximum value they can guarantee themselves if they were to partition the items into $n$ bundles but were forced to choose their bundle last.

Because a perfect MMS allocation does not always exist, the standard relaxation is optimal-MMS. This approach seeks an allocation that maximizes the minimum fraction of the MMS value that every agent receives. While this egalitarian approach seems fair by "raising the floor," this research demonstrates a paradoxical outcome: in these optimal scenarios, the number of agents who actually receive their full (100%) MMS value can be surprisingly small.

The Egalitarian Trap

The core finding of this paper is that the pursuit of egalitarian fairness can lead to widespread dissatisfaction. By focusing on maximizing the share of the worst-off person (e.g., ensuring everyone gets at least 99% of their MMS), the algorithm may inadvertently prevent almost everyone from reaching 100%. This highlights a significant gap between mathematical fairness and human satisfaction; while an agent might be told the division is "optimal," they may still feel slighted if they do not receive the share they were theoretically guaranteed by the cut-and-choose logic.

Methodology: Tensor-Based Constructions

To prove these limits, the authors employ a theoretical framework using high-order tensors. They represent goods and their associated values as elements in a $d$-dimensional multi-dimensional array.

Visualization of the high-order tensor construction used to prove the limits of satisfied agents.

In this model, the values are structured such that an agent can only achieve their full MMS value by receiving a specific "slice" of the tensor. By carefully perturbing these values, the authors create a mathematical conflict: because there are a limited number of orthogonal slices and agents are grouped together, satisfying the 100% MMS requirement for one small group of agents makes it mathematically impossible for the remaining agents to reach that same threshold.

The construction utilizes orthogonal slices ($S_1, S_2, S_3$) within the tensor to create mathematical conflicts between agent groups.

Key Results

The paper establishes two primary theorems regarding the upper bounds of satisfied agents in an egalitarian optimal setting:

  • Theorem 1: For any number of agents $n$, there exists a scenario where an optimal-MMS allocation guarantees the full MMS value to at most $\lfloor n/d \rfloor + 1$ agents.
  • Theorem 2 (The Constant Result): In specific constructions, the authors show that there are instances where only 3 agents (or 4, if the total number of agents is odd) receive their full MMS value, regardless of how large the total population $n$ is. In a room of 1,000 people, an "optimal" algorithm might still leave 997 people technically unsatisfied.

Crucially, these "worst-case" scenarios do not require an infinite number of items; they can occur with a relatively small set of $O(n^2)$ goods.

Limitations and Future Outlook

While these results are striking, the study currently assumes additive valuations, where the value of a bundle is the simple sum of its parts. It does not yet account for synergies or dependencies between items. Additionally, the paper focuses on the distribution of desirable goods; future work is needed to determine if these satisfaction limits hold true for the distribution of "chores" (undesirable tasks).

One of the most promising avenues for future research is the "sacrifice trade-off": investigating whether we can significantly increase the number of satisfied agents if we are willing to allow the "worst-off" person's share to drop by a marginal amount.

Summary updated

Abstract

Fair division is a subfield of multiagent systems that is concerned with object distribution. When objects are indivisible, the Maximin Share Guarantee (MMS) is a desirable fairness notion; however, it is not guaranteed to exist. While MMS allocations may not always exist, a relaxation of MMS is guaranteed to exist. We show that there exists a family of instances for which this relaxation fails to guarantee the MMS value for all but a small constant number of agents.
BibTeX
@inproceedings{searns2020fairness,
  author = {Andrew Searns and Hadi Hosseini},
  title = {{Fairness Does Not Imply Satisfaction (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i10.7228},
}
Figure