Imagine you are dividing a collection of items among a group of friends. If you receive a left shoe, it is virtually worthless to you unless you also receive the right shoe—a classic example of complementary goods. Conversely, if you are allocated a sleek sedan, receiving a second identical sedan adds very little extra utility—a case of substitutable goods.
Yet, for decades, the mathematical bedrock of fair division and algorithmic resource allocation rested on the additive valuation assumption. Under this assumption, an agent's total utility for a bundle of items is simply the sum of the individual items' values:
$$V(S) = \sum_{i \in S} v(i)$$
As noted by John P Dickerson et al. in The Computational Rise and Fall of Fairness, this abstraction makes the mathematics beautifully tractable. It allows algorithms to rely on fixed item weights, linear programming, and straightforward greedy strategies. However, as Sanath Kumar Krishnamurthy et al. point out in Finding Fair and Efficient Allocations, this assumption completely fails to capture real-world scenarios where items interact. When preferences are non-additive, traditional fairness and efficiency guarantees quickly fall apart.
Why Non-Additivity Breaks Traditional Fair Division
To understand why moving beyond additivity is so difficult, we have to look at how fair division algorithms actually bound envy. Consider a classic fairness metric: Envy-Freeness up to One Good (EF1) or the stricter Envy-Freeness up to Any Good (EFX). These metrics guarantee that an agent will not envy another agent's bundle once a single item is removed from the equation.
In an additive world, if we remove item $g$ from your bundle, my valuation of your remaining bundle drops by exactly the standalone value of $g$. The impact of removing an item is predictable, localized, and entirely independent of what else you hold.
But what happens when preferences are submodular (exhibiting diminishing marginal returns) or XOS (fractionally subadditive)? As Jugal Garg et al. explain in Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings, under submodular valuations, the value of an item is not a fixed constant; it depends dynamically on the context of the bundle.
$$\text{Marginal Value: } \Delta(g \mid S) = V(S \cup \{g\}) - V(S)$$
If you remove an item from a bundle, the marginal value of the remaining items might suddenly shoot up or drop drastically. This fluid nature of utility breaks our combinatorial tools. For instance, Alireza Farhadi et al. note in Almost Envy-freeness, Envy-rank, and Nash Social Welfare Matchings that the mathematical properties used to bound envy do not easily generalize because bundle values do not scale linearly. Algorithms like envy-cycle elimination, which seamlessly guarantee fair allocations under additive preferences (Georgios Amanatidis et al. in Multiple Birds with One Stone: Beating 1/2 for EFX and GMMS via Envy Cycle Elimination), lose their guarantees when applied to complex preference profiles (Alkmini Sgouritsa et al. in Pushing the Frontier on Approximate EFX Allocations).
The Spectrum of Non-Additivity
To navigate this complexity, researchers map out non-additive preferences along a spectrum of structural constraints:
- Submodular Valuations: These model diminishing marginal utility. If an agent already holds a large bundle, adding one more item yields less additional satisfaction than if they held a smaller bundle. Monika Henzinger et al. demonstrate in Leximax Approximations and Representative Cohort Selection how this naturally captures representation in cohort selection, where the marginal value of adding more members from the same demographic group diminishes as their presence increases.
- XOS (Fractionally Subadditive) Valuations: A broader class where an agent’s valuation is defined as the maximum over a set of additive functions. This represents scenarios where items act purely as substitutes but never as complements (Anand Krishna et al. in Sublinear Approximation Algorithm for Nash Social Welfare with XOS Valuations).
- Supermodular / Complementary Valuations: Here, items exhibit positive synergies ($V(A \cup B) > V(A) + V(B)$). Moshe Tennenholtz shows in Some Tractable Combinatorial Auctions that while general superadditivity is computationally daunting, specific structures—like network-based bundles—can be solved efficiently using graph theory.
Rethinking Optimization and Welfare
The breakdown of additivity is particularly evident when trying to maximize Nash Social Welfare (NSW)—the geometric mean of agents' utilities ($\prod_{i=1}^n V_i(A_i)^{1/n}$). NSW is highly prized because maximizing it simultaneously optimizes for both efficiency and fairness.
Under additive utilities, NSW maximization can be elegantly solved or closely approximated using convex programming duality, where dual variables are interpreted as market-clearing prices (Richard Cole et al. in Convex Program Duality, Fisher Markets, and Nash Social Welfare).
When valuations are submodular or XOS, this underlying convex structure vanishes. Standard algorithmic frameworks based on repeated bipartite matching fail because they cannot handle dynamically shifting marginal utilities (Jugal Garg et al.). To bypass this, researchers utilize demand oracles. Instead of forcing an algorithm to explicitly compute an exponentially large preference space, the algorithm queries an oracle to find an agent's preferred bundle given a set of item prices, breaking long-standing approximation barriers (Anand Krishna et al.).
Designing Robust Mechanisms
When exact fairness guarantees like EFX or perfect equitability become impossible or computationally intractable due to non-additive preferences (Mithun Chakraborty et al. in Weighted Envy-freeness in Indivisible Item Allocation), how do we design mechanisms that still work?
One powerful approach is to introduce continuous resources or monetary transfers to absorb the "shocks" of non-additive item interactions. Haris Aziz et al. demonstrate in Achieving Envy-freeness and Equitability with Monetary Transfers that establishing a property called transfer-stability allows distributed algorithms to guide agents to perfectly envy-free and equitable states, even when their bundle valuations are highly complex and non-linear.
Another modern frontier is learning-augmented mechanism design. Rather than requiring an algorithm to perfectly calculate allocations over complex valuation functions, mechanisms can leverage machine learning predictions. In Plant-and-Steal: Truthful Fair Allocations via Predictions, Ilan Reuven Cohen et al. introduce a framework that uses predictions of agent preferences to achieve strong approximate fairness guarantees when the predictions are accurate, while maintaining a provable safety net if the non-linear synergies of the agents' preferences are mispredicted.
By shifting from rigid additive assumptions to flexible, oracle-based, and learning-augmented frameworks, algorithmic social choice is building resource allocation tools equipped for the messy, interdependent reality of human preferences.