市場が競争的であるための必要十分条件はP = NP
本論文は、計算複雑性理論と経済学の市場競争性の間に驚くべき関係があることを示す。具体的には、市場が完全競争的であることと、計算量理論におけるP = NP問題が真であることが必要十分条件であることを証明する。この結果は、効率的な市場均衡の計算可能性と計算複雑性の深い関連性を明らかにする。
背景メモ
- 本論文は計算量理論の未解決問題「P ≠ NP予想」と、経済学の「完全競争市場」の理論的定義を結びつける理論計算機科学の研究。
- P = NP とは「解の検証が簡単な問題は、解の発見も簡単である」という（おそらく偽とされる）命題。もし真なら、多くの暗号技術が破られるなど社会的影響が極めて大きい。
- 著者は、ある種の市場均衡の計算が「NP困難」（事実上効率的に解けない）であることを示し、効率的な市場メカニズムが存在する（＝完全競争が成り立つ）のは P = NP のときに限られる、と論じている。
- この結果は「市場は本質的に計算が難しい」という直感に理論的裏付けを与え、暗号通貨や自動マーケットメーカーなど計算論的市場設計にも示唆を含む。