Overcoming the Additive Valuation Assumption in Resource Allocation

30 concepts29 papers1 proposal

Imagine you are valuing a meal. A burger is worth \$5 to you, and a soda is worth \$2. If you are offered both together, is the bundle worth exactly \$7?

In classical economic theory and algorithmic mechanism design, the answer is frequently assumed to be yes. This is known as the additive valuation assumption (or additively separable utility). It posits that the total utility or cost of a bundle of items is simply the sum of the values of its individual parts.

Mathematically, additivity is exceptionally convenient. It allows complex multi-item problems to be decoupled into independent, single-item problems, making optimization tractable. However, this assumption fundamentally fails to capture real-world relationships between items: synergies (complements, where items are worth more together) and substitutability (diminishing returns, where items cannibalize each other's value).

A growing body of research across algorithmic game theory, fair division, and online learning focuses on breaking free from this constraint to model realistic, interdependent preferences.

The Mathematical Convenience and Its Limits

For decades, foundational frameworks in computational economics have relied on additivity to guarantee the existence and computability of stable states. For example, the classic Arrow-Debreu market equilibrium model assumes additively separable utilities to prove market clearance, as explored by Decheng Dai et al. in Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities. Similarly, extensions of Fisher markets to infinite-dimensional spaces, such as those analyzed by Christian Kroer et al. in Infinite-Dimensional Fisher Markets: Equilibrium, Duality and Optimization, leverage linear additive structures to maintain computational tractability.

Yet, human neurobiology does not calculate value this way. As demonstrated by Ryan Webb et al. in Is the whole the sum of its parts? Neural computation of consumer bundle valuation in humans, the human brain processes bundle valuations non-additively, scaling signals based on the functional relationships and interdependencies between items. When algorithms ignore these cognitive and practical realities, the systems they govern begin to break down.

Where Additivity Distorts Fairness

In fair division—the problem of allocating indivisible goods or chores among multiple agents—the additive assumption leads to allocations that look fair on paper but leave participants deeply unsatisfied.

Consider standard fairness criteria like Competitive Equilibrium with Equal Incomes (CEEI) or Max-Min Share (MMS). As Haris Aziz et al. observe in Competitive Equilibrium with Equal Incomes for Allocation of Indivisible Objects, when frameworks assume additive utilities, they fail to recognize that an agent might receive a bundle of high individual values that are completely useless when combined. This discrepancy is quantified by Andrew Searns et al. in Fairness Does Not Imply Satisfaction (Student Abstract), who show that "optimal" MMS allocations under additive assumptions can still leave the vast majority of agents entirely unsatisfied if their true preferences contain synergies.

This limitation is equally severe when allocating negative utility items, such as household tasks. In Algorithms for Max-Min Share Fair Allocation of Indivisible Chores, Haris Aziz et al. point out that the cost of chores is rarely additive; cooking and washing dishes have a shared setup cost, making them more efficient to perform together. Ignoring these combinatorial effects leads to highly inefficient allocations, a problem that practical applications like the chore-division app designed by Ayumi Igarashi 0001 et al. in Kajibuntan: A House Chore Division App must explicitly address.

When we introduce structural constraints—such as matroids (Arpita Biswas in Matroid Constrained Fair Allocation Problem), partial preference information (Daniel Halpern et al. in Fair and Efficient Resource Allocation with Partial Information), or sequential item swaps (Ayumi Igarashi 0001 et al. in Reachability of Fair Allocations via Sequential Exchanges)—the mathematical complexity of finding fair allocations skyrockets precisely because dropping the additive assumption forces us to evaluate the power set of all possible item combinations.

The Auction and Pricing Dilemma

In mechanism design and auction theory, assuming additivity allows sellers to optimize revenue by simply pricing each item independently. For instance, Napat Rujeerapaiboon et al. in Regret Minimization and Separation in Multi-Bidder, Multi-Item Auctions show that under strict additivity, selling items via separate second-price auctions is optimal for minimizing seller regret. Similarly, Ophir Friedler et al. in 99% Revenue via Enhanced Competition demonstrate that simple separate or bundled auctions capture nearly all potential revenue when bidders have additive preferences.

However, real-world markets are rarely additive. In spectrum auctions, a telecom company values a license for New York and a license for New Jersey far more if they win both, creating intense synergies. As Nicolas Bousquet et al. argue in Welfare and Rationality Guarantees for the Simultaneous Multiple-Round Ascending Auction, traditional auction models rely on the "gross substitutes" property, which breaks down entirely when items are complementary.

When bidders exhibit sharp demands (wanting an exact bundle or nothing) or combinatorial preferences, standard reduction techniques—like the bidder reductions proposed by Andrew C Yao et al. in An n-to-1 Bidder Reduction for Multi-item Auctions and its Applications—and pricing models (Gianpiero Monaco et al. in Approximating the Revenue Maximization Problem with Sharp Demands) struggle to find optimal prices because the value of an item is fundamentally coupled with the rest of the allocation.

Blind Spots in Online Learning and Bandits

The additive assumption also introduces severe blind spots in sequential decision-making and online learning. In multi-item recommendation systems, modeled as "slate" bandit problems, a learner selects a list of items to display. If the system assumes the total reward is the sum of individual item rewards, it will recommend highly redundant items (e.g., five identical news stories), ignoring the fact that similar items cannibalize each other's value. This challenge is central to the algorithms developed by Satyen Kale et al. in Non-Stochastic Bandit Slate Problems.

Additive Model:
[Item A ($5)] + [Item B ($4)] + [Item C ($4)] = Total Value: $13
(Fails if Items B and C are redundant substitutes)

Synergistic/Combinatorial Model:
f({Item A, Item B, Item C}) = $8 
(Accurately captures diminishing returns or positive complementarities)

Whether designing adaptive stochastic optimization algorithms for resource allocation (Xavier Fontaine et al. in An adaptive stochastic optimization algorithm for resource allocation) or online fair division protocols (Ariel D. Procaccia et al. in Honor Among Bandits: No-Regret Learning for Online Fair Division), algorithms must navigate a massive explosion in the state space when rewards depend on the specific combination of resources rather than independent, linear sums.

Algorithmic Paths Beyond Additivity

To bridge the gap between mathematical tractability and real-world complexity, researchers are developing new frameworks that explicitly model non-additive interactions.

1. Submodularity and Proportional Complementarities

One approach relaxes additivity by adopting structured non-linear functions. For example, Jing Yuan et al. in Submodular Participatory Budgeting replace additive utility with submodular functions to naturally model diminishing returns in public spending (e.g., building a second park nearby yields less incremental utility).

To capture positive synergies, Yang Cai et al. in Simple and Approximately Optimal Pricing for Proportional Complementarities introduce models where the value of an add-on or upgrade scales proportionally with the quality of the base item, moving away from treating synergy as a flat, independent bonus.

2. Deep Learning and Attention Mechanisms

Instead of hardcoding specific mathematical structures to replace additivity, recent work leverages deep learning to discover combinatorial relationships directly from data.

Traditional Auction Model:
Fixed Additive Inputs ──> Separate Pricing ──> Linear Revenue

Neural Auction Model (RegretFormer):
Combinatorial Bids ──> Attention Layers (Learns Synergies) ──> Optimized Non-Linear Revenue

In Optimal-er Auctions through Attention, Dmitry Ivanov et al. introduce RegretFormer, a Transformer-based architecture. By utilizing attention mechanisms, the network dynamically learns the complex, non-additive interactions between different items and bidder preferences, designing revenue-maximizing mechanisms that bypass the limitations of traditional additive auction theory.

By moving beyond simple sums, these diverse research directions are shifting economic and algorithmic design toward a more accurate representation of value—one where the whole is fundamentally distinct from the sum of its parts.

Key Foundational Work

Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities (2009) — contributed 2 concept elements to this direction.
Non-Stochastic Bandit Slate Problems (2010) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 29 papers
  2. Version 1 · 2026-10-04 · 51 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_additive_valuation_assumption_41dcb94b,
  title = {additive valuation assumption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/additive-valuation-assumption/rdr_41dcb94b91504dc59e08ebe3278a5296},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_additive_valuation_assumption_41dcb94b_v2,
  title = {additive valuation assumption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/additive-valuation-assumption/rdr_41dcb94b91504dc59e08ebe3278a5296/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake