Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets
summary
Shows that computing exact HZ equilibria requires nonlinear fixed points by giving a unique irrational 4×4 instance (root of 17) and proves exact computation lies in FIXP membership via a Brouwer straight-line program, while an epsilon notion with exact fractional matching is in PPAD for approximate equilibria by polynomial continuity. Gives a combinatorial strongly polynomial algorithm for the special case of two-valued utilities algorithm and leaves hardness and the three-valued case open.
AI-written summary · about
chapters (13)
- 0:00Introduction
- 0:20Market mechanism properties
- 1:41Fractional perfect matching
- 4:02Fisher market setup
- 7:22Complexity and open questions
- 9:04Two-valued utility results
- 10:45Complexity class membership
- 13:20Algorithm for two-valued case
- 17:51Theoretical foundations
- 20:15Irrationality in equilibrium
- 23:46Membership in FIXP
- 26:55Approximate equilibria
- 29:59Conclusion and future work