Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2606.00951 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918533846269952 |
|---|---|
| author | Braverman, Mark Liu, Jingyi Xue, Eric Zhou, Chenghan |
| author_facet | Braverman, Mark Liu, Jingyi Xue, Eric Zhou, Chenghan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2606_00951 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Hardness of Approximate Hylland-Zeckhauser Equilibria Braverman, Mark Liu, Jingyi Xue, Eric Zhou, Chenghan Computer Science and Game Theory Computational Complexity 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. |
| title | Hardness of Approximate Hylland-Zeckhauser Equilibria |
| topic | Computer Science and Game Theory Computational Complexity |
| url | https://arxiv.org/abs/2606.00951 |