Uploaded October 2026 | Updated November 2026, 2 days ago
Members' Colloquium
2:00pm|Simonyi 101 and Remote Access
Topic: From 5G Spectrum Auctions to Nondeterministic Communication Complexity
Speaker: Tim Roughgarden
Affiliation: Institute for Advanced Study
Date: October 5, 2026
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.
Members' Colloquium
2:00pm|Simonyi 101 and Remote Access
Topic: From 5G Spectrum Auctions to Nondeterministic Communication Complexity
Speaker: Tim Roughgarden
Affiliation: Institute for Advanced Study
Date: October 5, 2026
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.










