Theory Day Session 1

Noam Nisan – On the borders of Border’s Theorem

Border’s theorem characterizes the possible (interim) allocation probabilities in a single item auction. It has received much interest lately in Algorithmic Mechanism Design as it allows optimization in Mechanism Design using polynomial-size linear programs rather than the natural exponential-size ones. Known Generalizations of Border’s theorem beyond the simple case of single item auctions are either very limited or are only approximate. This talk will explain why significant extensions of Border’s theorem are impossible, assuming standard Computational Complexity assumption. Our proof will take us on a journey from simple questions regarding marginal probabilities in probability spaces, to Revenue maximization in Mechanism Design, to Boolean function Analysis, to #P, and back. Joint work with Parikshit Gopalan and Tim Roughgarden.