OpenAlex ·
Competitive Equilibrium for Linear Chores is CLS-complete
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2611.06589
- Original
- Read it at the publisher
- Topics
Abstract
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
Does Frontier AI Strengthen Cyber Defense? Evidence from Project Glasswing
Winning Reviews, Losing Discovery? The Co-Evolutionary Game of AI Research and Peer Review
You Know What You Will Like: People Predict Their Own Ratings Better Than Recommender Systems
Dynamic investment and coordination in teams: Theory and experimental evidence
Dull, Dirty, Dangerous? Working Conditions and the Limits of Occupational AI Exposure
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.