First constant approximation for Hylland-Zeckhauser market equilibria

A new paper from researchers Yonglei Yan and Zhengyang Liu introduces the first constant-factor approximation algorithm for Hylland-Zeckhauser (HZ) equilibria in markets with multi-valued utilities. The HZ equilibrium is a foundational concept in economic theory that describes how to allocate indivisible goods (like houses or courses) to agents with complex preferences, ensuring both fairness and efficiency. Until now, no efficient algorithm existed for the multi-valued case, limiting practical applications. The authors achieve a 1/e approximation (roughly 36.8% of optimal welfare) using a polynomial-time method.

The key technical innovation is a utility stratification technique that converts the original multi-valued market into a structured bi-valued instance. This reduction allows the team to apply the exact algorithm of Vazirani and Yannakakis, originally designed for simpler settings. The result is the first rigorous efficiency guarantee for HZ equilibria in realistic scenarios where agents have multiple utility levels. This work has immediate implications for algorithmic game theory and market design, potentially enabling better course allocation systems and housing markets with provable fairness and computational tractability.