In the classic problem of fair division, we aim to distribute a set of items—like office spaces, tasks, or inheritance jewelry—among agents so that no one feels cheated. For indivisible items, the gold standard is Envy-Freeness up to One Item (EF1): I might envy your bundle, but if you removed your best item, I would no longer be jealous.
However, researchers have recently realized that satisfying every individual is not enough. Even if every person is individually satisfied, entire groups—defined by gender, department, or location—might still perceive that another group received a disproportionately better pool of resources. This "fairness gerrymandering" suggests that individual metrics can mask systemic disparities.
The Failure of Individual Metrics
Traditional fairness relaxations like EF1 are "local" and "pairwise." They only check if Agent A envies Agent B. As Hadi Hosseini, Sujoy Sikdar, and Lirong Xia argue in Fair Division through Information Withholding, these metrics can be deceptively weak. In a large system, an allocation might be EF1 for every pair of people, yet still require withholding a massive number of items from public view to achieve true, aggregate envy-freeness.
When we aggregate individuals into groups, the problem becomes more visible. Vincent Conitzer, Nisarg Shah, and their colleagues point out in Group Fairness for the Allocation of Indivisible Goods that an allocation can be fair to every individual while remaining unfair to collective segments. For example, in a university, every professor might be okay with their own lab equipment, but the Biology department as a whole might collectively envy the Engineering department’s resources.
Defining Group Envy-Freeness
To solve this, researchers have introduced Group Envy-Freeness (GEF). The intuition is a scaling of the individual definition: a group of agents envies another group if they could take the other group's items and reallocate them among themselves to make everyone in their own group better off.
In Almost Group Envy-free Allocation of Indivisible Goods and Chores, Haris Aziz and Simon Rey extend this to "mixed manna"—scenarios involving both goods (treats) and chores (tasks). They define GEF1, where group envy is eliminated if we can remove at most one item (a good from the envied group or a chore from the envying group).
Mechanisms for Collective Equity
How do we actually find these allocations? The research points to several robust mechanisms:
- Nash Welfare Optimization: One of the most powerful tools is the "Maximum Nash Welfare" (MNW) approach, which maximizes the product of agents' utilities. Vincent Conitzer and Nisarg Shah demonstrate that a "locally Nash-optimal" allocation—where no single-good swap can increase the utility product—guarantees group fairness up to one good.
- Typewise Allocation: In many real-world cases, agents belong to predefined "types." Nawal Benabbou, Edith Elkind, and Yair Zick explore Typewise Envy-Freeness (TEF1) in Fairness Towards Groups of Agents in the Allocation of Indivisible Items. They show that while finding the most efficient fair allocation is hard, specific algorithms can achieve TEF1 for binary preferences without wasting resources.
- Information Withholding: Hadi Hosseini and Lirong Xia propose a pragmatic alternative: HEF-k. Instead of complex reallocations, we can achieve envy-freeness by simply withholding a few items from the public view. This provides a more honest assessment of "aggregate" envy than checking every pair of agents individually.
Why Group Fairness Matters
The shift from individual to group fairness is not just a mathematical curiosity; it has significant policy implications. In Fair Equilibria in Sponsored Search Auctions, Andrea Celli and Stefano Leonardi apply these concepts to advertising. By treating small businesses as a collective group, platforms can ensure they aren't eclipsed by giants, maintaining a healthy market ecosystem.
Ultimately, group fairness provides a more tractable and socially relevant framework. As Pasin Manurangsi and Warut Suksompong suggest, the existence of fair allocations is often governed by the "divisibility" of items among agents. By aggregating agents into groups, we often find that achieving equity is not only more meaningful but also more mathematically achievable in complex, real-world markets.