{"ID":2922231,"CreatedAt":"2026-06-02T02:42:49.606572591Z","UpdatedAt":"2026-06-03T00:47:32.987482086Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.00951","arxiv_id":"2606.00951","title":"Hardness of Approximate Hylland-Zeckhauser Equilibria","abstract":"In this paper, we investigate the computational hardness of finding fractional allocations to unit-demand players using competitive equilibria from equal incomes (CEEI), where we allow a small constant error in players' response to market prices (also known as an approximate Hylland-Zeckhauser equilibrium). We show that assuming the $\\mathbf{(\\varepsilon,δ)}$-Generalized Circuits problem is PPAD-hard (the \"PCP for PPAD\" conjecture), finding an approximate HZ equilibrium is also PPAD-hard. This result provides additional motivation for trying to prove the PCP for PPAD conjecture as a tool for obtaining robust computational hardness results about markets. Further, we introduce a natural restriction on approximate HZ equilibria, where players' bundles may still only be approximately optimal given the prices, but may not contain positive-price items for which the player has zero utility. We show unconditionally that there exists a constant $ε$ such that finding a restricted $ε$-HZ equilibrium is PPAD-hard.","short_abstract":"In this paper, we investigate the computational hardness of finding fractional allocations to unit-demand players using competitive equilibria from equal incomes (CEEI), where we allow a small constant error in players' response to market prices (also known as an approximate Hylland-Zeckhauser equilibrium). We show tha...","url_abs":"https://arxiv.org/abs/2606.00951","url_pdf":"https://arxiv.org/pdf/2606.00951v1","authors":"[\"Mark Braverman\",\"Jingyi Liu\",\"Eric Xue\",\"Chenghan Zhou\"]","published":"2026-05-31T02:05:21Z","proceeding":"cs.GT","tasks":"[\"cs.GT\",\"cs.CC\"]","methods":"[]","has_code":false}