Metraipolis › archive › dc_0aacca07e6cc

The Complexity of Computing a Competitive Equilibrium in Fisher Markets with Chores — arXiv:2611.11556

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.11556
License (as archived)
CC0-1.0
Archived
2026-11-10T18:47:18.513Z
SHA-256 of the archived text
baee6dce2cf6be0bdc0002c30fce39a64efd22a8f545f4547251b0750e65dfba
Stable URL of this page
https://metraipolis.com/documento/dc_0aacca07e6cc

How to cite

The Complexity of Computing a Competitive Equilibrium in Fisher Markets with Chores — arXiv:2611.11556 — arXiv (en), https://arxiv.org/abs/2611.11556 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0aacca07e6cc (Metraipolis archive dc_0aacca07e6cc, sha256 baee6dce2cf6be0bdc0002c30fce39a64efd22a8f545f4547251b0750e65dfba)
BibTeX
@misc{dc0aacca07e6cc,
  title = {The Complexity of Computing a Competitive Equilibrium in Fisher Markets with Chores — arXiv:2611.11556},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.11556},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0aacca07e6cc; sha256 baee6dce2cf6be0bdc0002c30fce39a64efd22a8f545f4547251b0750e65dfba},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.11556. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study the complexity of computing competitive equilibria in Fisher markets with divisible chores and positive rational disutility coefficients and earning requirements. For linear disutilities, we prove that exact equilibrium computation is CLS-complete. In particular, the problem remains CLS-hard even when the earning requirements are binary in $1$ and $2^k$, where $k$ is an integer. We prove hardness by encoding the first-order conditions of a box-constrained quadratic program in equilibrium prices and earning flows, using a compact minimum-cost flow construction. For convex constant-elasticity-of-substitution (CES) disutilities, exact equilibrium prices may be irrational. We formulate the problem of finite-precision equilibrium price computation, in which we seek rational prices with a certified market clearing error at most a given rational tolerance encoded in binary. We prove that this problem is CLS-complete for every fixed rational exponent $\rho>1$. To prove this hardness, we encode a quartic polynomial through the fourth-order expansion of the CES price potential function corresponding to the Eisenberg-Gale (EG) dual program, and show that every sufficiently accurate approximate equilibrium of the constructed market lies near uniform prices. Additionally, we also identify a tractable special case of chores Fisher markets. In particular, we provide a strongly polynomial algorithm for exact equilibrium computation in linear markets whose disutility matrix has rank at most two and earning requirements are arbitrary positive rationals. For $n$ agents and $m$ chores, the algorithm uses $O(nm(n+m))$ rational arithmetic operations and comparisons, with polynomial intermediate encoding length.

Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2611.11556 — 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-10T18:39:07.428Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).