Competitive Equilibrium for Linear Chores is CLS-complete
cs.GT, cs.CC
Submitted: 2026-11-04
Updated: 2026-11-04
Terminology
Sources
- Settling the complexity of Nash equilibrium in congestion games
- Polynomial Time Algorithms to Find an Approximate Competitive Equilibrium for Chores
- Algorithms for Competitive Division of Chores
- Competitive Allocation of a Mixed Manna
- Competitive Equilibrium with Chores: Combinatorial Algorithm and Hardness
- Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
- Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD
- A Rational Convex Program for Linear Arrow-Debreu Markets
- A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market
- The Complexity of Gradient Descent: CLS = PPAD $\cap$ PLS
- Satiation in Fisher Markets and Approximation of Nash Social Welfare
Related papers
- How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation
- Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards
- Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee
- The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets
- From signaling to interviews in random matching markets
- Optimizing Social Utility in Sequential Experiments