# 市场具有竞争性当且仅当 P ≠ NP

- 来源：Hacker News 热门（buzzing.cc 中文翻译）
- 作者：kscarlet
- 发布时间：2026-07-04 00:55
- AIHOT 分数：56
- AIHOT 链接：https://aihot.virxact.com/items/cmr571gw1007islbr0wlbl21s
- 原文链接：https://arxiv.org/abs/2602.20415

## AI 摘要

论文证明竞争性市场结果需要计算上的难解性。若 P = NP，企业可高效求解合谋检测问题，使合谋成为可维持的均衡；若 P ≠ NP，满足特定需求结构硬度条件的市场中合谋检测在计算上不可行，惩罚威胁不可信，合谋不稳定。结合此前（Maymin, 2011）证明市场效率需要 P = NP 的结论，得到一个根本不可能性：市场无法同时具备信息效率与竞争性。人工智能正将市场从竞争区间推向合谋区间，为算法合谋现象提供了理论解释。

## 正文

Computer Science > Computer Science and Game Theory

[Submitted on 23 Feb 2026]

Title:Markets are competitive if and only if P != NP

Philip Z. Maymin

Abstract:I prove that competitive market outcomes require computational intractability. If P = NP, firms can efficiently solve the collusion detection problem, identifying deviations from cooperative agreements in complex, noisy markets and thereby making collusion sustainable as an equilibrium. If P != NP, the collusion detection problem is computationally infeasible for markets satisfying a natural instance-hardness condition on their demand structure, rendering punishment threats non-credible and collusion unstable. Combined with Maymin (2011), who proved that market efficiency requires P = NP, this yields a fundamental impossibility: markets can be informationally efficient or competitive, but not both. Artificial intelligence, by expanding firms' computational capabilities, is pushing markets from the competitive regime toward the collusive regime, explaining the empirical emergence of algorithmic collusion without explicit coordination.

Comments:

Subjects: Computer Science and Game Theory (cs.GT); Computational Complexity (cs.CC); Theoretical Economics (econ.TH); Computational Finance (q-fin.CP)

MSC classes: 91B26, 68Q17, 91A20

Cite as: arXiv:2602.20415 [cs.GT]

(or arXiv:2602.20415v1 [cs.GT] for this version)

https://doi.org/10.48550/arXiv.2602.20415

arXiv-issued DOI via DataCite

Submission history

From: Philip Maymin [

Mon, 23 Feb 2026 23:31:43 UTC (58 KB)

Access Paper:

Current browse context:

cs.GT

cs.CC

econ

econ.TH

q-fin

q-fin.CP

References & Citations

Bookmark

Bibliographic and Citation Tools

Code, Data and Media Associated with this Article

Demos

Recommenders and Search Tools

arXivLabs: experimental projects with community collaborators