In algorithmic game theory and mechanism design, the "additive valuation" assumption is the ultimate mathematical convenience. If a bidder values a bundle of items as simply the sum of the individual items' values, the multi-item universe instantly simplifies. Items do not interact. A seller can run separate, parallel auctions for each item, or a fair-division algorithm can distribute goods one by one without worrying about what an agent has already won.
But the real world is rarely additive. Items can be substitutes (owning two sedans is not twice as valuable as owning one) or complements (a left shoe and a right shoe are worthless in isolation). When valuations are non-additive, items interact in complex ways, causing traditional mechanisms to break down.
A major frontier in algorithmic mechanism design focuses on generalizing allocation and pricing guarantees to broader, more realistic classes of valuation functions.
The Hierarchy of Valuation Complexity
To understand why generalizing valuation functions is difficult, we must look at the hierarchy of valuation classes, ordered from most restrictive to most general:
- Additive: The value of a bundle is exactly the sum of its parts: $V(A \cup B) = V(A) + V(B)$ for disjoint sets.
- Submodular: Bidders experience diminishing marginal returns. Adding an item to a small set provides more additional value than adding it to a larger set.
- XOS (Fractionally Subadditive): The valuation can be represented as the maximum over a family of additive valuations. This cleanly models complex substitute goods.
- Subadditive: The most general class without complements, defined simply by the triangle inequality: $V(A \cup B) \le V(A) + V(B)$.
When we move down this list, we lose the property of independence. In an additive world, an agent's demand for Item A is completely decoupled from whether they receive Item B. In a submodular or subadditive world, an agent's valuation is history-dependent: the mechanism must track the exact subset of items an agent has already accumulated to know how much they value the next one.
The Revenue Maximization Frontier
In multi-item auctions, maximizing revenue while maintaining simplicity is notoriously difficult. For additive buyers, simple strategies like selling items independently or bundling everything together into a single "grand bundle" are known to capture a constant fraction of optimal revenue.
However, as Constantinos Daskalakis et al. note in Simple, Credible, and Approximately-Optimal Auctions, extending these revenue guarantees to subadditive or XOS models remains an open challenge. The core obstacle is that sequential or simultaneous item auctions expose bidders to strategic risk; a bidder cannot safely bid on an item without knowing if they will successfully secure its complements or substitutes later in the mechanism.
To circumvent this, researchers have turned to sophisticated optimization frameworks. For instance, Yang Cai et al. developed a "lift-and-round" framework over marginal reduced forms in Computing Simple Mechanisms: Lift-and-Round over Marginal Reduced Forms. This approach successfully extends revenue-maximizing mechanisms to XOS valuations. Yet, moving fully to subadditive valuations remains a barrier because tracking the changing availability of arbitrary item subsets across sequential buyer arrivals introduces severe contention resolution issues, as highlighted by Shuchi Chawla et al. in Buy-Many Mechanisms for Many Unit-Demand Buyers.
Fair Division and the Resilience of Simple Rules
The challenge of non-additivity is equally acute in fair division, where the goal is to allocate indivisible goods to minimize envy. When agents are strategic and can lie about their preferences, achieving fair outcomes like Envy-Freeness up to one good (EF1) is typically proven under strict additive assumptions, as seen in the work of Federico Fusco et al. (Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness). Similarly, the algorithmic guarantees for finding integral market equilibria designed by Sanath Kumar Krishnamurthy (On the Proximity of Markets with Integral Equilibria) are bounded by the additive assumption.
Surprisingly, some simple mechanisms are remarkably resilient to valuation generalizations. Stefano Leonardi et al. demonstrated this in Round-Robin Beyond Additive Agents: Existence and Fairness of Approximate Equilibria. They proved that the classic, simple Round-Robin protocol—where agents take turns picking their favorite remaining item—retains its EF1 fairness guarantees even when agents have submodular valuations.
Why does Round-Robin work here? Because submodularity implies diminishing returns, an agent's marginal utility for their next chosen item is always bounded by the utility of what they could have chosen earlier. This mathematical structure prevents other agents from accumulating massive, envy-inducing bundles, even without the mechanism knowing the agents' true underlying valuation functions.
Overcoming Budgets and Interdependence
The problem compounds when non-additive valuations interact with other real-world constraints, such as hard budget limits or interdependent values (where an agent's value depends on private signals held by others).
When bidders have strict budgets, maximizing social welfare becomes a moving target because agents cannot bid beyond their financial capacity, regardless of how much they value a bundle. Nick Gravin et al. analyzed this via the "Liquid Price of Anarchy" framework in Liquid Price of Anarchy, establishing efficiency bounds for simple auctions under additive valuations. To push past additivity, Dimitris Fotakis et al. introduced a novel "budget-constrained demand query" in A Bridge between Liquid and Social Welfare in Combinatorial Auctions with Submodular Bidders. This query acts as an informational bridge, allowing mechanisms originally designed to maximize standard social welfare to effectively maximize liquid welfare for both submodular and XOS bidder classes.
Where do we hit a hard wall? When valuations exhibit both non-additivity and informational interdependence. As Alon Eden et al. demonstrate in PoA of Simple Auctions with Interdependent Values, while we can achieve positive welfare guarantees for unit-demand or additive bidders with interdependent values, extending these bounds to subadditive or XOS preferences remains an open problem. The combination of hidden information from other players and complex item synergies creates an informational gap that simple pricing mechanisms cannot easily bridge.
Key Foundational Work
The AND-OR Game: Equilibrium Characterization - (Working Paper) (2012) — contributed 1 concept elements to this direction.
From convex optimization to randomized mechanisms: toward optimal combinatorial auctions (2011) — contributed 1 concept elements to this direction.
JACK: A Java Auction Configuration Kit (2012) — contributed 1 concept elements to this direction.