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.
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.