In the classic "cake-cutting" problem, we imagine a divisible resource that can be sliced into infinitely small pieces. But in the real world, most things we care about—houses, shifts at a hospital, or seats in a classroom—are indivisible. For decades, the mathematical shortcut for dividing these items was to assume additive valuations: if you like a camera and a tripod, your value for the pair is simply the value of the camera plus the value of the tripod.
However, as Richard Cole and Vasilis Gkatzelis point out in Convex Program Duality, Fisher Markets, and Nash Social Welfare, this assumption is a "lie" of convenience. In reality, goods often exhibit diminishing marginal returns (submodularity) or synergies (superadditivity). A second umbrella is worth much less than the first; a left shoe is worthless without the right. Recent research has shifted toward finding fair and efficient allocations when these complex, non-linear preferences are the rule rather than the exception.
The Problem with Diminishing Returns
When valuations are additive, fairness is relatively easy to track because an item's value is constant regardless of what else you own. In a submodular setting, the value of an item depends on the context of your current bundle. This makes "envy" a moving target.
If Arpita Biswas and Sanath Kumar Krishnamurthy want to ensure a Groupwise Maximin Share (GMMS)—where every subgroup feels they got their fair portion of the collective pool—they must contend with the fact that the group's total value isn't just the sum of individual desires. As explored in Groupwise Maximin Fair Allocation of Indivisible Goods, submodularity means that as a group acquires more items, each additional item provides less "fairness" than the last, complicating the search for an equitable equilibrium.
Nash Social Welfare as a Fairness Engine
One of the most successful ways to bridge the gap between fairness and efficiency is through Maximum Nash Welfare (MNW). Instead of maximizing the sum of utilities (which favors the "strong") or the minimum utility (which can be inefficient), MNW maximizes the product of agents' utilities.
Sanath Kumar Krishnamurthy and Rohit Vaish demonstrated in Finding Fair and Efficient Allocations that MNW is a powerhouse for indivisible goods. It naturally produces allocations that are Envy-Free up to one item (EF1)—meaning if I envy you, I’d stop envying you if you just removed one item from your bundle.
The intuition is elegant: the product of utilities is maximized when values are balanced. If one person has very little, giving them an item creates a massive percentage increase in the total product, forcing the algorithm to prioritize the "poor" without ignoring overall efficiency (Pareto Optimality).
Moving Beyond Additivity with Cycle-Canceling
To handle the mathematical messiness of submodular functions, researchers have adapted tools from graph theory. In Cycle Cancellation for Submodular Fractional Allocations and Applications, Chandra Chekuri and Jan Vondrák introduce a "cycle-canceling" lemma.
Imagine a fractional allocation where items are partially shared. If there is a "cycle" of agents who each value a piece of the next person's bundle more than their own, we can "shift" the allocation along that cycle. In additive settings, this is simple arithmetic. In submodular settings, Chekuri and Vondrák show that you can still shift these values in a way that preserves the total "multilinear extension" of the utility, allowing us to round these fractional shares into whole items while maintaining fairness guarantees.
New Benchmarks for the "Unachievable"
Sometimes, the gold standard of fairness—Envy-Free up to any item (EFX)—is simply too hard to guarantee. EFX requires that I don't envy you even after you remove your least valuable item. Alexandros Hollender and Georgios Amanatidis showed in Maximum Nash welfare and other stories about EFX that even MNW fails to guarantee EFX once items have more than two distinct values.
This has led to a new frontier of "epistemic" fairness. Ioannis Caragiannis and Jugal Garg proposed Epistemic EFX (EEFX) in New Fairness Concepts for Allocating Indivisible Items. The intuition here is: an allocation is fair if there exists a way to distribute the remaining items such that everyone could be happy. By relaxing the requirement from "absolute certainty" to "plausible fairness," they found algorithms that work even for complex, non-additive preferences.
The Challenge of Chores
Finally, the field is expanding from "goods" to "chores" (items with negative value). As Bo Li explores in Fair Allocation of Indivisible Chores: Beyond Additive Valuations, chores are fundamentally different. If doing two chores together is easier than doing them separately (subadditive costs), the standard "I-cut-you-choose" logic breaks. The research direction now focuses on identifying specific cost structures—like those found in bin packing or job scheduling—where constant-factor fairness is still achievable despite the combinatorial explosion of possible assignments.