Constant Approximation for Hylland--Zeckhauser Equilibria
This provides the first efficient approximation guarantee for a fundamental equilibrium concept in market design, addressing a long-standing open problem.
The paper presents the first polynomial-time algorithm achieving a 1/e-approximation for Hylland-Zeckhauser equilibria in multi-valued utility settings, using a novel utility stratification technique.
We present a polynomial-time algorithm for computing a $1/e$-approximate Hylland--Zeckhauser (HZ) equilibrium. This establishes the \emph{first} efficient approximation guarantee for HZ equilibria in settings with multi-valued utilities. Our main technical contribution is a novel utility stratification technique that reduces the original multi-valued market to a structured bi-valued instance. This reduction allows us to efficiently compute the approximation by leveraging the exact algorithm of Vazirani and Yannakakis.