From 5G Spectrum Auctions to Nondeterministic Communication Complexity

A folklore belief in economics is that "simple auctions" should "perform well" if and only if the auction's participants view the items for sale as substitutes (as opposed to complements). How can this belief be formulated as a precise conjecture? What techniques might be used to prove it? To answer these questions, we show that certain lower bound arguments, traditionally used to prove limitations on polynomial-time algorithms or polynomial-communication protocols, apply equally well to auction equilibria.