CS Paper Radar

Sharp Complexity Thresholds for Network Cournot Competition

Mohammad Hajiaghayi, Mohammad Mahdavi

cs.GT cs.CC ·submitted 2026-11-18 18:55 UTC · v1

Abstract

We determine the approximation complexity of network Cournot equilibrium as a function of demand degree and the number of firms sharing a market. For common, nonincreasing concave polynomial inverse demands, convex quadratic costs of firms' allocation vectors, and rational total capacities, high-precision approximation is polynomial-time solvable for cubic demands, regardless of market size. Quartic demands remain tractable when each market has at most three firms, and quintic demands remain tractable with at most two. These thresholds are exact: approximation at a fixed positive profit-regret tolerance is PPAD-hard for quartic demands with four firms per market, quintic demands with three, and sextic demands with two. Each hardness result uses one fixed demand curve in every market, a constant number of markets per firm, and globally nondecreasing strongly convex quadratic costs. We also give a polynomial-time algorithm for arbitrary-degree nonincreasing concave polynomial demands when each firm's convex polynomial cost depends only on its total production. The algorithm applies to arbitrary access graphs and permits firm-specific inverse demands. Its running time is polynomial in the input size and the logarithm of the inverse accuracy. The algorithm assigns one marginal charge to each firm and adjusts the charges until each firm's total sales approximate the quantity it would produce at that charge.

Comment
26 pages, 2 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Nonuniform Buy-at-Bulk Network Design: Improved Approximation and LP Integrality Gap

cs.DS ·2026-11-04 ·Iman Gholami, MohammadTaghi Hajiaghayi
theory similarity 0.65
Abstract

In nonuniform buy-at-bulk network design, we are given an undirected graph and $h$ terminal pairs with positive demands, and we must route every demand at minimum total cost when each network resource has two independent parameters: a fixed buying price paid once if the resource is used, and a per-unit rental cost (or physical length) paid proportionally to the traffic it carries. Unlike the uniform-cost or single-sink variants, the general multicommodity problem allows unrelated buying and rental metrics across arbitrary source--sink pairs, arbitrary demands, and both edge and node resources. We give a deterministic polynomial-time $O(\log^2 h / (\log\log h)^2)$-approximation algorithm for undirected nonuniform buy-at-bulk network design. The guarantee holds for edge costs, node costs, and their combination, and applies to arbitrary positive rational demands with no dependence on the number of vertices or the numerical demand ratio. This improves upon the $O(\log^4 h)$ bound of Chekuri, Hajiaghayi, Kortsarz, and Salavatipour (2010) for unrestricted instances. Our result also establishes the same $O(\log^2 h / (\log\log h)^2)$ upper bound on the integrality gap of the natural affine multicommodity flow LP, bounding integral buying and rental costs separately against their fractional counterparts and preserving zero rental budgets exactly.

0.25

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.62
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

Computing Equilibria in Integer Programming Games with Shared Constraints

cs.GT math.OC ·2026-10-03 ·Bainian Hao, Hyunwoo Lee, Robert Hildebrand, Carla Michini
similarity 0.59
Abstract

We develop a cutting-plane algorithm for computing pure Nash equilibria in finite integer games with shared constraints, where a deviation may be feasible against one opponent profile and infeasible against another. Conditional equilibrium inequalities capture this dependence through an explicit activation term. We give affine encodings of costs and activation conditions and prove that the resulting inequalities characterize the equilibrium set exactly. Embedded as lazy constraints in branch-and-cut, they yield the Generalized Zero-Regret algorithm for optimizing a linear objective over exact or approximate equilibria; a bisection procedure maintains certified bounds on the smallest achievable approximation factor. We also prove that, when the conditional polytopes have integral vertices, a concave cost is constant on the minimal face containing an equilibrium strategy, so strict concavity forces vertex strategies; for uniform integer-splittable bin packing, a cost-preserving transformation yields vertex equilibria even without strict concavity. We give formulations for bin packing, network formation, and knapsack games with shared capacities and evaluate the algorithm on 3,300 instances, computing a socially optimal equilibrium on all but 43, certifying nonexistence on 16, and certifying approximation factors within a few percent where no exact equilibrium exists.

0.41

A Better-Than-$3$ Approximation Algorithm for Demand Matching via Knapsack Intersection LP and Contention Resolution

cs.DS cs.DMmath.CO ·2026-09-15 ·Michel X. Goemans, Yuchong Pan
theory similarity 0.59
Abstract

The demand matching problem generalizes both the knapsack problem and the $b$-matching problem. In this problem, each edge of a graph has a demand and a weight, and each vertex has a capacity. The goal is to find a maximum weight subset of edges such that, at each vertex, the total demand of the incident selected edges does not exceed the vertex capacity. Parekh [IPCO 2011] proved that, if each edge is individually feasible, the natural LP relaxation for demand matching has integrality gap at most $3$, yielding a $3$-approximation algorithm. This bound is tight for the natural LP relaxation, matching the lower bound of Shepherd and Vetta [Math. Oper. Res. 2007]. We present a randomized $(3/2 + \sqrt{2} + \varepsilon) \approx (2.914 + \varepsilon)$-approximation algorithm for the demand matching problem for every $\varepsilon > 0$, giving the first approximation ratio strictly better than $3$. For bipartite graphs, we obtain a randomized $(2 + \varepsilon)$-approximation algorithm for every $\varepsilon > 0$. Both algorithms run in time polynomial in $1/\varepsilon$ and the input length. Our algorithms use a strengthened LP relaxation based on intersecting the integral knapsack polytopes associated with the vertices, together with a multiple-choice generalization. As a key ingredient, we prove the existence of a $(q, 1/(1+q))$-balanced contention resolution scheme for the integral knapsack polytope for every $q \in [0, 1]$, which may be of independent interest. The balance guarantee $1/(1+q)$ is tight in the worst case over all knapsack instances.

0.23

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.58
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

Algorithms with Smoothed Polynomial-Time Complexity for Deterministic Discounted-sum and Mean-payoff Games

cs.GT cs.DS ·2026-10-09 ·Ali Asadi, Krishnendu Chatterjee, Ruichen Luo
similarity 0.58
Abstract

Turn-based deterministic games on graphs are two-player zero-sum games played on finite directed graphs, where the vertex set is partitioned between the Max and the adversarial Min Player. The respective player chooses outgoing edges from their vertices. We consider these games with the classical discounted-sum and mean-payoff objectives. The goal of the Max Player is to maximize the objective against the adversarial Min Player. These games lie in NP $\cap$ coNP and are among the rare combinatorial problems that belong to this complexity class, yet the existence of a polynomial-time algorithm is a major open question. All known deterministic algorithms require exponential time in the worst case, while the classical strategy iteration (policy iteration) algorithm is remarkably efficient in practice, which motivates the study of the smoothed complexity of these games. Previous results established a smoothed polynomial-time bound only for the restricted class of ergodic games and presented only a high-probability guarantee. Our main result is a new analysis technique for a variant of the strategy iteration algorithm, and we show these algorithms achieve smoothed polynomial complexity for general game graphs with both high-probability and expected runtime guarantees. In particular, our result removes the ergodicity restriction of prior work and strengthens the high-probability guarantee to the stronger expected-runtime guarantee, thereby resolving the open question on the smoothed complexity of these games.

0.50

FIXP-Completeness in Second-Price Auctions

cs.GT cs.CC ·2026-10-31 ·Nobutaka Shimizu
theory similarity 0.58
Abstract

Computing equilibria is a fundamental algorithmic problem in game theory and economics. Although general frameworks are available for proving membership in FIXP, the class capturing exact fixed-point computation, establishing FIXP-completeness often remains challenging. We prove FIXP-completeness of exact equilibrium computation in three second-price auction models: (1). pacing with return-on-investment constraints, with multiplier cap $1+δ$ for every fixed rational $δ>0$ [Filos-Ratsikas, Hansen, Høgh, and Hollender (2024)]; (2). budget-constrained generalized second-price sponsored shopping [Hansen, Li, and Nie (2026)]; (3). budget-constrained throttling [Liu (2026)]. These results resolve open questions on the exact complexity of automated bidding. Our technical ingredient is a FIXP-complete generalized-circuit problem using only clipped affine gates and the reciprocal $x\mapsto1/(1+τx)$, for any fixed positive rational $τ$. This gate basis provides a common framework for the three auction reductions: simulating these gates in each model establishes FIXP-hardness without directly implementing multiplication or squaring.

0.15

The Complexity of Continuous Contract Design over Polymatroids

cs.GT ·2026-11-03 ·Max Klimm, Paul Lippke, Philipp Warode
theorycode/data similarity 0.58
Abstract · 89 pages, 6 figures. The Lean 4 formalization is at https://github.com/philippwarode/contract-design-polymatroids-lean

We study optimal contracts when an agent allocates continuous effort subject to polymatroid capacity constraints. Effort produces a linear expected reward and incurs a cost. With binary outcomes and limited liability, the principal chooses a single reward share. For linear costs, an optimal contract can be computed in polynomial time. For quadratic costs, the agent has a unique best response computable by polynomially many submodular minimizations, yet optimizing the principal's share is NP-hard even for explicitly represented cut-based rank functions. With $n$ activities, the best-response path can have $2^{n-O(\log n)}$ breakpoints even when each reward coefficient and each rank value is an integer representable in $O(n\log n)$ bits. The construction also answers a question of Allman, Lo, and McCormick on polynomial bit length for source-sink monotone two-parameter minimum cuts. Despite this complexity, an optimal contract for quadratic costs always exists with a share of at most $1/2$. Consequently, $O(1/\varepsilon)$ best-response computations suffice for a $(1-\varepsilon)$-approximation. For rational quadratic costs on explicitly described rational polytopes containing zero, this gives a fully polynomial-time approximation scheme. More generally, a share of at most $1/p$ suffices for continuous convex costs homogeneous of degree $p>1$, on any compact convex action set containing zero. For general convex costs with an exact value and bounded-subgradient oracle, we obtain an oracle approximation scheme using approximate best responses and a supplied lower bound on positive welfare.

0.43