CS Paper Radar

Competitive Equilibrium for Linear Chores is CLS-complete

Qian Liu, Shinuo Ma, Yixin Tao, Minji Yang, Weiqiang Zheng

cs.GT cs.CC ·submitted 2026-11-04 14:43 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

The Complexity of Computing a Competitive Equilibrium in Fisher Markets with Chores

cs.GT ·2026-11-08 ·Christian Kroer, Ruta Mehta, Tianlong Nan
theory similarity 0.75
Abstract

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 $ρ>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.

0.14

A Polynomial-Time Algorithm for Constant-Factor EFX Allocations of Chores

cs.GT ·2026-11-16 ·Aniket Murhekar
similarity 0.68
Abstract · 32 pages

We study the fair division of indivisible chores among agents with additive disutilities, focusing on the central fairness notion of envy-freeness up to any chore (EFX), and its multiplicative approximations. Although the existence of constant-factor approximations to EFX are known, computing such an allocation in polynomial time remained open. We resolve this question by giving an algorithm that, for every $\varepsilon\in(0,1)$, computes a $(3+\varepsilon)$-EFX allocation in time polynomial in the input length and $1/\varepsilon$. Our result relies on two algorithmic contributions. First, we give a fully polynomial-time approximation scheme (FPTAS) for earning-restricted (ER) equilibria with equal earning requirements and arbitrary feasible chore earning limits. We develop a new nonconvex program with chore payouts and money-flow variables, and prove that every local maximum yields an exact ER equilibrium. We then give a mirror-ascent algorithm for this program and prove that it converges to an approximate ER equilibrium in polynomial time. Second, we give a new procedure that converts the approximate equilibrium into a $(3+\varepsilon)$-EFX-friendly allocation, a suitable starting point for the chore-swap framework of Garg and Murhekar (2026). The procedure uses a flexible price threshold to choose swap chores and their recipients together, overcoming a factor-four bottleneck in the earlier approaches while accommodating approximate earnings. We expect these ideas to be useful more broadly in fair division, including for goods and other fairness notions.

0.30

Solving the Arctic Product-Mix Auction

cs.GT econ.TH ·2026-09-28 ·Elizabeth Baldwin, Paul Klemperer, Edwin Lock
similarity 0.64
Abstract

Arctic product-mix auctions allow budget-constrained bidders to express preferences over multiple substitute goods. We give the first strongly polynomial algorithm to find the competitive equilibria when the auctioneer has separable convex piecewise-linear costs. It combines a strongly polynomial reduction to the costless Arctic auction with an existing strongly polynomial algorithm for costless Arctic auctions. We also give a polynomial-time Turing reduction from costless Arctic auctions to linear Fisher markets, and a strongly polynomial many-to-one reduction to linear Arrow-Debreu exchange markets. If a good is sold in positive quantity in two competitive equilibria, its price is the same in both.

0.32

Welfare in Envy-free Contracts: When Agents Have Sparse Interests

cs.GT ·2026-11-08 ·Junjie Chen, Cong Chen, Takuro Yamashita
similarity 0.63
Abstract

We study welfare maximization under envy-free contracts, where a principal assigns tasks and offers success-contingent payments to heterogeneous agents with hidden effort. For unit-demand agents, we establish a sharp complexity boundary: the problem is polynomial-time solvable when each agent is interested in at most two tasks, but NP-hard with at most three interests. Our algorithm analyzes tree-structured dependencies among forced assignments and reduces optimization to maximum-weight independent set in a perfect graph. When agents may receive multiple tasks, no polynomial-time constant-factor approximation exists unless $\mathrm{P}=\mathrm{NP}$. Finally, with homogeneous success probabilities and rewards, we establish a welfare- and revenue-preserving equivalence between unit-demand contract design and envy-free pricing. This yields polynomial-time welfare maximization without restricting interests, while revenue maximization remains NP-hard.

0.11

Newton Steps are Faster for Linear Complementarity Problems

cs.DS math.OC ·2026-11-05 ·Haoyuan Ma, László A. Végh, Adrian Vladu
similarity 0.62
Abstract

Linear Complementarity Problems (LCPs) with sufficient matrices form a well-studied class of problems, dating back from the foundational works of Cottle and Dantzig (1968). LCPs capture convex quadratic programs, and admit reductions from problems such as discounted stochastic games or mean-payoff games. While the original approach for solving these problems was based on pivoting methods, in their 1991 book, Kojima, Megiddo, Noma, and Yoshise introduced an interior point method (IPM) with running time that is polynomial in the input size, but which depends linearly on a certain parameter called the handicap number of the matrix. Despite the ensuing rich literature on sufficient LCP IPMs, the linear dependence on the handicap number has not been improved since then. We present an IPM whose running time depends on the square root of the handicap number. The algorithm can decrease the duality gap by a constant factor in $O\left(\min\left\{\sqrt{n} (1+κ),n^{9/8}\sqrt{1+κ}\right\}\right)$ iterations. Curiously, this can already be achieved using standard Newton updates. We analyze the IPM in a norm defined by a local weighting, where centralizing Newton steps quadratically converge to the central path, without any dependence on the handicap number. The weights arise from a characterization by Rump (Linear Algebra and Its Applications, 1997, 1998, 2003) of the sign-real spectral radius and its relation to sufficiency; another ingredient of our proof is a new operator norm characterization of the handicap number. Moreover, the connection to Rump's work also enables us to show coNP-completeness of testing sufficiency, and approximation hardness of the handicap number.

0.34

Exploring the Tractability Frontier of Hylland-Zeckhauser Models

cs.GT ·2026-10-26 ·Ioannis Panageas, Avi Shein, Shayan Taherijam, Vijay V. Vazirani
theory similarity 0.62
Abstract

The Hylland-Zeckhauser (HZ) mechanism provides a market-based approach to one-sided matching, making efficient equilibrium computation central to its implementation. Under bi-valued utilities, it admits a strongly polynomial-time algorithm [VY], whereas with four values per buyer, the problem is PPAD-hard under inverse polynomial approximation [CCPY]. To understand the tractability boundary, we study two extensions of the bi-valued case: a third linear utility value and separable concave utilities with two common slopes. For every fixed rational $a\in(0,1)$, we prove that computing a normalized additive $\varepsilon_{*}(a)/N$-equilibrium in an $N$-buyer HZ market is PPAD-complete for some constant $\varepsilon_{*}(a)>0$, even when all utilities belong to the same prescribed set $\{0,a,1\}$. This resolves the main question left open by [VY, CCPY]: whether three utility values already suffice for PPAD-hardness. Assuming the PCP-for-PPAD conjecture, we strengthen the above-stated result to constant additive-error hardness. For the concave extension, we compute an exact equilibrium in strongly polynomial time with two marginal utility slopes common across goods for each buyer and arbitrary rational buyer-good breakpoints. With three common marginal slopes, suitable breakpoints encode the three valued linear case, yielding PPAD-hardness. Thus, our paper identifies two thresholds separating tractable and intractable cases of HZ models with utility functions specified by utility values or marginal slopes. In both cases, the tractability threshold lies between two and three.

0.16

Fair and Efficient Allocations: Decision Problems in the Gap of Polynomial Hierarchy

cs.GT ·2026-09-25 ·Xiaolin Bu, Biaoshuai Tao
published similarity 0.62
Abstract · Accepted by WINE'26

We consider the fair division problem with indivisible goods and study the following decision problem: given a fair division instance, does there exist an allocation that is envy-free and efficient? We consider two efficiency criteria: Pareto-optimality and social welfare optimality. We provide a complete landscape on the computational complexity of this decision problem, with the number of agents ranging from $2$ to $\infty$, both additive valuations and general valuations, and the more restricted class of $k$-ary valuation functions (where an item's marginal value is restricted to $\{0,1,\ldots,k-1\}$ for some constant $k\geq2$). One interesting observation is that many versions of the above-mentioned decision problems fall into the ``gap'' between the first and the second levels of the polynomial hierarchy. Specifically, assuming the polynomial hierarchy does not collapse to the first level (i.e., assuming $\text{NP}\neq\text{coNP}$), these problems are in $(Σ_2^{\text{p}}\capΠ_2^{\text{p}})\setminus(\text{NP}\cup\text{coNP})$. In particular, we provide a fine-grained complexity analysis across different parameter regimes, including the number of agents and the choice of valuation models. Depending on different parameters, many problems admit different complexity classifications, ranging from the intermediate classes $Θ_2^{\text{p}}$ and $Δ_2^{\text{p}}$ between the two levels to $Σ_2^{\text{p}}$-completeness. Finally, De Keijzer et al. show the $Σ_2^{\text{p}}$-completeness of the decision problem when considering Pareto-optimality as the efficiency criterion with additive valuations. Our main results extend this result to more restricted settings, such as instances with a constant number of agents or $3$-ary valuation functions, which resolves the open problem given by Bouveret and Lang.

0.16

Envy-free Allocations with Individual Payments

cs.GT cs.DS ·2026-10-07 ·Robert Bredereck, Eva Deltl, Tanmay Inamdar, Pallavi Jain, Pranjal Pandey
survey similarity 0.62
Abstract

When an envy-free allocation of indivisible goods does not exist, monetary transfers can restore envy-freeness. Existing work on fair division with subsidies, however, typically assumes that these payments are provided by an external source, an assumption that may be unrealistic in many applications. We address this limitation by allowing only monetary transfers between agents, with each agent's payments constrained by their individual budget. We show that while it is polynomial-time tractable to determine whether a given allocation can be made envy-free by payments under individual budgets, the general problem of computing such an allocation from scratch is NP-hard, even when agents have relatively large budgets. Motivated by this intractability, we conduct a parameterized complexity analysis, establishing fixed-parameter tractability with respect to the number of goods or to the joint parameter number of agents and good types, and we provide efficient algorithms in several special cases. For explicitly listed items, our type-based algorithm answers the envy-freeness part of an open question of T. T. Nguyen and J. Rothe, "Complexity Results and Exact Algorithms for Fair Division of Indivisible Items: A Survey."

0.15