Abstract
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.
Joint work with Parikshit Gopalan and Tim Roughgarden.