经济与社会科学2012arxiv.org
市场有效当且仅当 P = NP (2010)
Markets are efficient if and only if P = NP (2010)
进阶 · 约 45 分钟读完前置知识：计算复杂性（P/NP）、有效市场假说、期权定价基础
导读
这篇论文讨论有效市场假说（EMH）与计算复杂性之间的关系，标题提出强命题：市场完全有效当且仅当 P = NP。作者用期权等市场构件把 3-SAT 之类的 NP 问题嵌入定价/套利问题，论证若市场能完全有效定价，则可在多项式时间解 NP 问题；反之若 P≠NP，则市场无法达到完全有效。
HN 关注点：HN 读者被“把有效市场假说与 P vs NP 划等号”的强标题吸引，讨论焦点是证明是否成立、模型假设是否过强，以及它会被怎样解读为支持或反对市场与集中计划。
HN 评论精选
这几条评论里：质疑 3 补充 1
质疑质疑标题过强，指出 P=NP 不等于市场有效，且连续近似、算法成本等限制都会影响结论。
虽然这很有趣，但标题有点过强。有三点限制（适用于许多关于 P=NP 的论文）：1. 市场仍可能有效，因为要造成 P vs NP 问题所需的情形非常复杂；特别地，它们需要购买非常昂贵且不可分割的东西，而大多数情况下我们可以把股票等当作连续量，只有很小误差。2. 如果 P=NP 且我们知道如何在多项式时间解 NP 问题并真的去做，市场才可能有效；标题听起来好像只要 P=NP 市场就已经有效，这不成立。3. 即使 P=NP，多项式时间算法的开销也可能大到市场无法有效；同理，P≠NP 但指数很小，现实中市场仍可能有效。
CJefferson查看英文原文
While this is a fun, the title is a little strong. There are three limitations (whuch apply to many papers about P=NP). 1. The market could still be efficient, because the situations which must arise to cause P vs NP problems are very complicated. In particular thry require very expensive indivisible things to buy, whereas in most situations we can treat things like shares as continuous with only a small error. 2. Markets could be efficient if P=NP and we know how to solve NP probkems in P, and we do it. The title makes it sound like the market will already be efficient if P=NP, which isnt true. 3. Even if P=NP, the polynomial could still be big enough the market cant be efficient. Similarly, P could not equal NP but the expoenential be small enough markets can still be efficient in reality.
补充若 P≠NP，反而支持哈耶克式经济计算论证：集中计划计算经济分配更难，市场近似可能是次优但可行的选择。
大多数人似乎把这读成证明市场天生有缺陷，并支持他们对市场经济意识形态上的不信任。我认为，如果作者论点成立且 P 确实≠NP，这种结论对主张用另一种通常更集中的经济计算形式来扩大或取代市场经济的人可能意味着更大的问题。Allende 的 Cybersyn 著名地使用线性规划（P）来集中“模拟”并改进常规市场机制。如果作者论点成立，我认为这实际上支持 Hayek 等人的经济计算问题论点：经济分配问题的有效计算是不可能的，市场有缺陷的动态大概已是我们能负担的最佳近似。
zwww查看英文原文
Most people seem to read this as a proof that markets are inherently flawed and as lending support to their ideological distrust of market economies. I think that if the authors thesis holds true and p indeed != np, this kind of conclusion could spell an even bigger problem for those who advocate to agument or replace market economies with another, typically more centralized, form of economic calculation. Allende's cybersyn famously used linear programming (P) in order to centrally 'simulate' and improve upon more regular market mechanics. If the authors thesis holds I think it's actually an argument in favor of the economic calculation problem talking point of Hayek and the like: efficient calculation of economic distribution problems is impossible and flawed dynamics of the market are probably close to the best approximation we can afford.
质疑批评证明只是把 3-SAT 嵌入期权定价，未证近似困难性，且这种 NP-hard 论证过于宽泛，不能否定 EMH 作为近似模型。
这篇论文并没有声称或做多少不明显的事（还有跑题问题）。它通过基于期权的构件把 3-SAT“嵌入”市场，从而“证明”EMH（或市场效率）是 NP-hard。这没问题，除了：(a) 我们常常不关心精确解，所以需要近似困难性，而论文没证明；(b) 我能想出成千上万个类似的显然例子。举个傻例子：我给出一个衍生品，如果某个已知存在解的 NP-hard 问题在给定时间前被找到，它付 1 美元。这会“显示 EMH 的 NP 困难性”，因为显然该衍生品价格应为 1（问题按构造有解），所以任何人都应“显然”定价 1。这就像说“生活是 NP-hard”。是啊，当然。但这不意味着我们不擅长做正确的事、理性（如 EMH）不是分析行为的好但不完美的工具。推到极端一切都会崩，因为模型是错的。
LolWolf查看英文原文
This paper just gets me every time I see it. It really doesn’t claim or do much that isn’t already quite obvious (it also has the other problem of going on completely unrelated tangents.) First, it does this funny thing where it “proves” that EMH (or market efficiency) is NP-hard, by building gadgets based on options and then using them to “embed” 3-SAT. This is fine except (a) we often don’t care about an exact solution (so we need approximation-hardness that isn’t shown) and (b) I can come up with millions of other obvious things like this! Here’s a silly one one: I give a derivative whose price is $1 if a solution (that is known to exist) to an NP-hard problem is found by a given time. This will “show the NP hardness of EMH” because obviously the derivative price should be 1 (the problem has a solution, by construction) and so anyone should “obviously” price it at $1. This is like saying “life is NP-hard.” Like, yeah, of course it is. That doesn’t mean we aren’t pretty good at doing the right thing and rationality (like EMH) is a good, if imperfect tool to analyze behavior. Taking it to its extreme then everything breaks, because the model is wrong. We don’t throw up our hands and quit because making real-life decisions is a sampling-hard, query-hard, and NP-hard problem (if all data is known), but a basic model of rationality would say that humans can “perfectly” solve it. (Which is obviously crazy, but we obviously don’t throw the assumption of rationality of agents out the window because of this.) Otoh, I am definitely of the opinion that some economists hold EMH as a “magical” axiom, but that’s a different story.
质疑认为结论不新且对多数市场效率定义不成立；N 人纳什均衡 NP-hard 是更一般的结果。
这篇报告对任何有抱负的学者是个有趣的思想实验，但并非新颖洞见，而且对大多数市场效率定义显然不成立。若玩学术压人游戏，更一般的结果是 N>2 的“最佳”或“多个”N 人纳什均衡已经是 NP-hard。有效市场的含义会是每个参与者都有多项式时间算法解这个 NP-hard 问题，因此 P=NP。
ericjang查看英文原文
The report, while a fun thought exercise for any aspiring academic, is not a novel insight, and is obviously untrue for most definitions of market efficiency. If we are going to play the academic one-upmanship game, a more general result that "best" or "multiple" N-player Nash Equilibria for N > 2 is already NP-hard. The implication of an efficient market would be if every player had a polynomial-time algorithm to solve the NP-hard problem, ergo P=NP. [1] https://people.csail.mit.edu/costis/simplified.pdf [2] https://www.quantamagazine.org/in-game-theory-no-clear-path-to-equilibrium-20170718/ [3] https://arxiv.org/abs/1104.3760#:~:text=Unlike%20general%20Nash%20equilibrium%2C%20which,as%20finding%20a%20planted%20clique.
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2012Hacker News 讨论帖107 分 · 123 评
- 2018Hacker News 讨论帖332 分 · 191 评
- 2020Hacker News 讨论帖214 分 · 169 评
同领域还值得读
一切的回报率，1870–2015
The Rate of Return on Everything, 1870–2015
利用1870–2015年多国的长期数据，估算股票、住房等各类资本的回报率，并将其与经济增长率进行比较。
经济与社会科学2019 · 487 分 · 260 评进阶 · 约 100 分钟编辑精选一切资产的回报率，1870–2015
The Rate of Return on Everything, 1870–2015
构建了 1870–2015 年 16 个国家的长周期资产回报数据集，覆盖股票、住房、政府债券和短期票据，系统比较各类资产的真实回报与波动性。
经济与社会科学2018 · 215 分 · 151 评进阶 · 约 120 分钟编辑精选一切资产的回报率，1870–2015（2019）
The Rate of Return on Everything, 1870–2015 (2019)
这篇发表于《经济学季刊》的论文构建了 1870–2015 年间 16 个主要发达国家的股票、债券、房地产等资产收益率的长周期数据库。
经济与社会科学2024 · 190 分 · 148 评进阶 · 约 80 分钟编辑精选想法是否越来越难找？
Are ideas getting harder to find?
探讨“想法是否越来越难找到”：通过衡量多个领域的“研究生产率”，发现维持相同的增长需要投入指数级增长的研究资源，即研究效率在持续下降。
经济与社会科学2016 · 182 分 · 106 评入门 · 约 60 分钟编辑精选比特币与区块链的经济极限
The Economic Limits of Bitcoin and the Blockchain
芝加哥大学 Eric Budish 的论文从经济学角度分析比特币与区块链的根本限制：核心论点是只要攻击网络（双花或砸盘做空）的收益超过挖矿成本，51% 算力攻击就有利可图，而挖矿…
经济与社会科学2018 · 176 分 · 37 评进阶 · 约 90 分钟编辑精选