跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.24931 · v1

Sharp Complexity Thresholds for Network Cournot Competition

网络古诺竞争的精确复杂性阈值

首次提交 2026-11-19 02:55
版本更新 2026-11-19 02:55
雷达观测 2026-11-19 15:04
arXiv ↗PDF ↗

摘要

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.

作者备注:26 pages, 2 figures

AI 论文解读

基于摘要 · 非全文审阅

作者确定了网络古诺均衡近似复杂度随需求多项式的次数和每个市场中的企业数量变化的精确阈值。

正在读取账号与研究记录…

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-19 02:55 · 最新观测版本

Sharp Complexity Thresholds for Network Cournot Competition

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.

查看此版本解读 →查看此版本原文 ↗