Complementarities and Externalities

on YouTube ↗44m

" summary

Proposes a relax-and-round method that converts fractional solutions (LP relaxations, lotteries) into integer outcomes with bounded violations, using Scarf's lemma, duality and a new geometric rounding. Claims: stable matchings with couples exist if capacities are allowed to increase by at most about 1 (or ≤2 with a different rounding), refugee-resettlement constraints incur worst-case sparsity-based gaps but simulations show max ~12% and average ~5% violations, and a delta-substitutes condition yields a 2δ−1 supply-violation bound; implementations and auctions with budgets follow the same framework and work much better in practice than worst-case.

AI-written summary · about

" chapters (12)

1. 0:00Complementarities and externalities
2. 1:10Greedy algorithms fail
3. 3:01Greedy in market design
4. 3:43Relax and round approach
5. 4:06Stable matching with couples
6. 12:48Relax and round for multibody
7. 13:50Refugee resettlement stability
8. 20:39Walrasian equilibrium
9. 30:20Pseudo markets without money
10. 38:28Auction with budget constraints
11. 41:39Advantages and drawbacks of relax and round
12. 43:10Q&A