In classical economics, "fair division" often assumes resources are like cake: infinitely divisible. If two people want the same piece, you simply cut it in half. However, as Haris Aziz and Haris Aziz 0001 point out in Developments in Multi-Agent Fair Allocation, real-world resources—houses, cars, or specific work shifts—are indivisible.
When items cannot be split, perfect envy-freeness (where no one prefers another's bundle) is often mathematically impossible. If there is one diamond and two people, someone will inevitably be envious. To solve this, researchers have developed a hierarchy of "relaxed" fairness criteria that provide meaningful guarantees while respecting the discrete nature of the goods.
The Intuition of "Up to One Item"
The most influential breakthrough in this field is the shift from absolute envy-freeness to Envy-Freeness up to one item (EF1). The intuition is simple: an allocation is fair if any envy an agent feels could be eliminated by hypothetically removing a single item from the envied person's bundle.
As explained in The Price of Fairness for Indivisible Goods by Xiaohui Bei and Warut Suksompong, EF1 is a powerful standard because it is guaranteed to exist for any number of agents with additive preferences. It can be achieved through simple mechanisms like a Round-Robin procedure, where agents take turns picking their favorite remaining item. Justin Payan and Yair Zick demonstrate this in I Will Have Order! Optimizing Orders for Fair Reviewer Assignment, using a round-robin approach to ensure fairness in conference paper assignments.
The Holy Grail: EFX
While EF1 is easy to satisfy, it can sometimes feel "weak." If an agent envies a bundle only because of its most valuable item, EF1 is satisfied, but the envy might still feel significant. This led to a stricter relaxation: Envy-Freeness up to any item (EFX).
Under EFX, envy must vanish regardless of which item is removed from the envied bundle (provided the item has positive value). Hannaneh Akrami and colleagues describe EFX as the "holy grail" of the field in EFX Allocations: Simplifications and Improvements. Unlike EF1, it is not yet known if an EFX allocation always exists for more than three agents, making it a central focus of current research.
Mechanisms for Achieving Fairness
How do we actually find these allocations? Beyond round-robin, several key mechanisms have emerged:
- Envy Cycle Elimination: If Agent A envies B, and B envies C, and C envies A, we can simply "rotate" their bundles along this cycle. This reduces the total envy in the system without making anyone worse off. Georgios Amanatidis and Evangelos Markakis use this in Multiple Birds with One Stone to break approximation barriers for EFX.
- Maximum Nash Welfare (MNW): Instead of looking for fairness directly, we can maximize the product of all agents' utilities. Vincent Conitzer and Nisarg Shah show in Fair Public Decision Making that the MNW solution is remarkably robust, often automatically satisfying EF1 and providing high efficiency.
- Greedy with Budgets: When items have "costs" or agents have budgets, algorithms like DensestGreedy, proposed by Arindam Khan in Finding Fair Allocations under Budget Constraints, can guarantee an EF2 allocation (envy-free up to the removal of two items).
Expanding the Scope: Groups and Chores
The research direction has recently expanded from individual fairness to Group Fairness. In Group Fairness for the Allocation of Indivisible Goods, Vincent Conitzer and Nisarg Shah argue that we should ensure no group of agents (e.g., a department or a demographic) collectively envies another group. This leads to the concept of GEF1 (Group Envy-Freeness up to one item).
Furthermore, the field is moving toward "mixed manna"—scenarios involving both goods (which agents want) and chores (which agents want to avoid). Haris Aziz 0001 explores this in Almost Group Envy-free Allocation of Indivisible Goods and Chores, noting that chores introduce new mathematical complexities because agents now compete to receive fewer items rather than more.
Why This Works
The success of this research direction lies in its pragmatism. By acknowledging that perfect equality is impossible in a discrete world, researchers like Hadi Hosseini and Rohit Vaish have created a framework where fairness is a computable guarantee rather than an abstract ideal. Whether through withholding information (Fair Division through Information Withholding) or leveraging specific preference structures like lexicographic rankings (Fair and Efficient Allocations under Lexicographic Preferences), the goal is to find the "least unfair" way to divide a world that cannot be perfectly cut.