{"ID":3083637,"CreatedAt":"2026-06-05T06:46:15.197025399Z","UpdatedAt":"2026-06-07T07:23:37.79250861Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.06317","arxiv_id":"2606.06317","title":"Constant Approximation for Hylland--Zeckhauser Equilibria","abstract":"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.","short_abstract":"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 r...","url_abs":"https://arxiv.org/abs/2606.06317","url_pdf":"https://arxiv.org/pdf/2606.06317v1","authors":"[\"Yonglei Yan\",\"Zhengyang Liu\"]","published":"2026-06-04T15:54:58Z","proceeding":"cs.GT","tasks":"[\"cs.GT\"]","methods":"[]","has_code":false}