On the Borders of Border’s Theorem

on YouTube ↗35m

" summary

Explains when the Border theorem gives a full reduced-form LP characterization and when it cannot be extended: shows computing exact optimal revenue for a Boolean public-project (weighted threshold mechanism is optimal) is #P-hard via ties/partition reductions, so no explicit facet-style Border generalization exists for many extensions; uses linear-program duality, ellipsoid separation and reductions from counting problems to connect infeasibility certificates to computational hardness. weighted threshold reduced-form LP

AI-written summary · about

" chapters (10)

1. 0:00Intro
2. 2:00Border's Theorem (1991, 2007)
3. 6:06Completing the Auction Picture
4. 7:43Computational use of Border's Theorem Theorem: There exists a poly-time algorithm that when given infeasible interim allocations finds a violated Border inequality
5. 10:37Generalizing Border's Theorem
6. 12:21Goal: Border-like Characterizations
7. 17:27Proof Structure
8. 21:36The Boolean Public Project Problem
9. 25:17Optimal mechanism
10. 27:40#P-Hardness of Revenue Optimization