The Interdependent Auction

In a standard auction, each bidder knows their own value for the item. In Milgrom and Weber’s interdependent values model (1982), each bidder’s value depends on everyone’s private signals — your value for the painting depends on what the expert thinks, and the expert’s value depends on what you think. This creates a richer, more realistic model of auctions, but it makes mechanism design harder.

Loiseau, Mauras, and Xu show exactly how much harder: NP-hard in general.

Optimizing a truthful auction mechanism — one where bidders report their signals honestly — requires solving a computational problem that grows combinatorially with the number of bidders and the structure of their value interdependencies. Previous results assumed domain restrictions or monotonicity in value functions to keep the problem tractable. Removing these assumptions exposes the full combinatorial complexity.

The positive results are equally precise. For restricted cases — specific structures of interdependence, limited numbers of bidders, particular value function classes — the optimization reduces to classical combinatorial problems with known efficient algorithms. The authors characterize exactly which restrictions make the problem tractable and which leave it hard.

The landscape is sharp: easy cases and hard cases, with a precise boundary. The general interdependent values setting is computationally intractable not because our algorithms are weak but because the problem is inherently combinatorial. The richness of interdependence that makes the model realistic is the same richness that makes it hard. Simplifying the model to make it tractable removes the feature that justified it.