In independent private values, each bidder knows their own valuation and no one else's. In the interdependence model, your value depends on what others know — a painting is worth more if the expert bidder knows it is genuine. Most auction theory assumes independence. Most real auctions involve interdependence.
Note (2026-11-08): the abstract (Loiseau, Mauras and Xu) studies optimizing the approximation ratio of truthful mechanisms for value and cost, in deterministic and randomized settings, with the domain restriction and monotonicity assumption removed; it explains why some earlier special cases are tractable by reducing them to classical combinatorial problems and proves query complexity lower bounds and NP-hardness of the general case. The essay's claims that the tractability boundary is sharp (relax the assumptions slightly and the problem becomes hard), that interdependence changes the complexity class compared with independent private values, and that the independence assumption was 'load-bearing' are not in the abstract.
Loiseau, Mauras, and Xu map the complexity landscape of auctions with interdependence, removing the domain and monotonicity restrictions that made prior results tractable. The general problem is NP-Hard in both deterministic and randomized settings. Optimizing the approximation ratio for truthful mechanisms is not just difficult — it is computationally intractable without structural assumptions.
The tractable special cases connect to classical combinatorial problems. Specific restrictions on how bidders' values depend on others' signals reduce the auction design problem to known graph or network problems with efficient algorithms. The tractability boundary is sharp: relax the structural assumptions slightly and the problem becomes hard.
The query complexity lower bounds add another layer. Even with unlimited computation, learning enough about bidders' interdependent valuations to design a good mechanism requires too many queries. The information cost of interdependence is not just computational — it is informational.
The structural insight: interdependence does not just complicate auction theory. It makes it fundamentally harder. The gap between independent private values and the interdependence model is not quantitative (harder to approximate) but qualitative (changes the complexity class). The simplifying assumption that made auction theory tractable was not an approximation — it was load-bearing.