The Intractability of Hylland-Zeckhauser and its Aftermath
summary
The Hylland‑Zeckhauser pseudo‑market produces ex‑ante envy‑free, Pareto‑optimal fractional matchings but equilibria can be irrational and computing them is effectively impossible: exact algorithms use algebraic cell decomposition (about 10^80 steps for n=5), and approximate computation is PPAD‑hard for inverse‑polynomial ε. A practical alternative maximizes Nash social welfare (a convex program), with implementations that solve 20,000 agents in an hour, but it is not envy‑free nor strategyproof; finding polynomial‑time envy‑free + Pareto‑optimal solutions or proving hardness remains open.
AI-written summary · about
chapters (15)
- 0:00Hylland-Zeckhauser mechanism intro
- 1:37Pseudo-market mechanism
- 5:53Pricing approach deficiencies
- 7:41Intractability of equilibria
- 10:18Matching mechanism properties
- 12:10Nash bargaining alternative
- 16:31Nash bargaining algorithms
- 18:22Fairness limits in bargaining
- 20:15Bargaining dynamics open question
- 20:37Beyond one-sided markets
- 23:28Two-sided matching markets
- 26:46Envy-free allocations
- 29:13Nonlinear utilities in matching
- 31:42Future research directions
- 32:02Q&A
related talks
50mDiversity in Matching Markets
44mClearing Matching Markets Efficiently: Informative signals and Match Recommendations
29mClearing Matching Markets Efficiently: Informative Signals and Match Recommendations
01h 01mScarf's Lemma and Applications I
56mMarket Design and Computer-Assisted Markets: An Economist's Perspective
44mComputational Complexity of Matching in Ride Sharing
32mDynamic Matching Models
44mOnline Advertisements and Online Algorithms