Metraipolis › archive › dc_2f5c73d2c0da
Competitive Equilibrium for Linear Chores is CLS-complete — arXiv:2611.06589
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.06589
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-05T18:20:23.518Z
- SHA-256 of the archived text
17d1f06c8063da8b40a0ac173445ffdff7a8baab967c9ef83759066d1460502b- Stable URL of this page
https://metraipolis.com/documento/dc_2f5c73d2c0da
How to cite
Competitive Equilibrium for Linear Chores is CLS-complete — arXiv:2611.06589 — arXiv (en), https://arxiv.org/abs/2611.06589 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2f5c73d2c0da (Metraipolis archive dc_2f5c73d2c0da, sha256 17d1f06c8063da8b40a0ac173445ffdff7a8baab967c9ef83759066d1460502b)
BibTeX
@misc{dc2f5c73d2c0da,
title = {Competitive Equilibrium for Linear Chores is CLS-complete — arXiv:2611.06589},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.06589},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2f5c73d2c0da; sha256 17d1f06c8063da8b40a0ac173445ffdff7a8baab967c9ef83759066d1460502b},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.06589. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The competitive equilibrium (CE) is a fundamental concept for markets, with applications to efficient and fair allocation of resources. We consider the fundamental question of computing a CE in the most basic Fisher market model where agents have linear preferences. While it is known that we can compute a CE in strongly polynomial time with linear goods, there is no known polynomial-time algorithm for CE with linear chores. Computing a CE for linear chores is known to be in CLS with no hardness results. In this paper, we prove that computing an exact CE in Fisher markets with divisible chores and linear disutilities is CLS-hard and thus CLS-complete. To the best of our knowledge, this is the first CLS-completeness result for a market equilibrium problem. On the technical side, we use the nonconvex dual Eisenberg-Gale (EG) program whose Karush-Kuhn-Tucker (KKT) points are CE [Chaudhury, Kroer, Mehta, and Nan, 2024], and the CLS-complete problem of computing a KKT point of a quadratic program [Fearnley, Goldberg, Hollender, and Savani, 2024]. We show that from any exact equilibrium of the constructed market, we can recover in polynomial time an $\varepsilon$-KKT point of the input quadratic program over the unit box. Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno). Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Computational Complexity (cs.CC). Pagina del lavoro: https://arxiv.org/abs/2611.06589 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-11-05T18:14:18.994Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).