Most classical models of resource allocation rely on a convenient but often false assumption: additivity. In an additive world, the value of a bundle of goods is simply the sum of the values of its individual parts. If a left shoe is worth $10 and a right shoe is worth $10, the pair is worth $20.
In reality, resources are rarely independent. A pair of shoes is worth far more than two left shoes; a team of engineers with complementary skills is more productive than the sum of their individual outputs; and a radio spectrum license is more valuable if it covers adjacent frequency bands. This research direction focuses on breaking the "additive assumption" to design auctions, fair division algorithms, and market mechanisms that account for synergies (where items are worth more together) and substitutabilities (where items are redundant).
The Failure of the Additive Assumption
When we assume additivity, we ignore the functional dependencies that define real-world value. As noted by Arpita Biswas in Matroid Constrained Fair Allocation Problem, this simplification prevents allocation logic from recognizing when a bundle's value is greater or less than its components.
This failure is particularly acute in "all-or-nothing" scenarios. In Pricing for Online Resource Allocation: Beyond Subadditive Values, J. Benjamin Miller and Shuchi Chawla 0001 highlight that traditional item-based pricing fails when buyers derive zero value from incomplete bundles, such as specific time intervals or network paths. Similarly, in labor markets, Equilibrium in Labor Markets with Few Firms demonstrates that worker synergies—like social influence or complementary technical skills—create non-linear values that standard economic models cannot capture.
Modeling Interdependency through k-wise Interactions
To move beyond simple sums, researchers have introduced more flexible valuation frameworks. One powerful approach is the use of k-wise item interactions. Vincent Conitzer, Tuomas Sandholm, and Paolo Santi explored this in Combinatorial Auctions with k-wise Dependent Valuations.
Instead of listing a value for every possible subset (which grows exponentially), this model captures synergies by looking at interactions between groups of $k$ items. This allows for the modeling of "costly disposal," where adding an item might actually decrease a bundle's value due to negative synergies or clashes. In strategic contexts, Adarsh Barik and Jean Honorio show in Provable Sample Complexity Guarantees for Learning of Continuous-Action Graphical Games with Nonparametric Utilities that failing to account for these higher-order synergies prevents us from understanding how one participant's actions are conditioned on the simultaneous actions of many others.
Fair Division in a Synergistic World
Fairness is usually measured by concepts like Maximin Share (MMS) (getting at least what you'd get if you divided the goods yourself) or Envy-Freeness (EF) (not preferring anyone else's bundle). However, synergies make these guarantees harder to achieve and perceive.
Andrew Searns and Hadi Hosseini prove in Fairness Does Not Imply Satisfaction (Student Abstract) that even "optimal" fair allocations can leave almost everyone unsatisfied if the underlying model ignores synergies. When items are complementary, a "fair" share of individual items might still result in a bundle that is functionally useless to the recipient.
This has practical implications for everyday problems. In Kajibuntan: A House Chore Division App, Ayumi Igarashi 0001 and Tomohiko Yokoyama apply fair division to household chores. They note that simple additive models fail to account for the "practical efficiencies" of grouping related tasks—performing two chores together might be easier than the sum of their individual efforts.
Pricing and Market Equilibria
How do you set prices when the value of item A depends on whether you also bought item B? Standard item-by-item pricing is insufficient.
- Bundle Pricing: Dimitris Fotakis 0001 and colleagues in Online Resource Allocation via Static Bundle Pricing suggest using fixed "price menus" for bundles. This bridges the gap between online uncertainty and optimal offline allocation for buyers with all-or-nothing demands.
- Spectrum Auctions: In Approximately Envy-Free Spectrum Allocation with Complementarities, Dengwang Tang and Vijay G Subramanian use dual variables from linear programming to set prices that reflect the synergistic value of adjacent frequency bands.
- Modular Marketplaces: As AI tasks are increasingly solved by "chaining" specialized modules, Kshipra Bhawalkar and Jeff Dean explore in Equilibria and Learning in Modular Marketplaces how market models must evolve when the combined utility of two specific services exceeds their independent contributions.
Computational Frontiers
The "double curse" of non-additive allocation is that it is both a communication nightmare (eliciting exponential preferences) and a computational nightmare (the Winner Determination Problem is NP-hard).
Recent work seeks to bypass these hurdles using modern optimization. Nils Kohring and Martin Bichler in Enabling First-Order Gradient-Based Learning for Equilibrium Computation in Markets introduce "smooth market" surrogates. By creating continuous, differentiable versions of discrete allocations, they enable the use of fast first-order policy gradients to find equilibria in complex auctions that were previously computationally unreachable.
Similarly, in the realm of sequential allocation, Xavier Fontaine and Vianney Perchet developed algorithms in An adaptive stochastic optimization algorithm for resource allocation that automatically adapt to the hidden complexity of reward functions, whether they exhibit linear returns or synergistic interactions.