Новая статья доказывает: рынки конкурентны, только если P≠NP. Тред отвечает: картели фиксируют цены годами

Теорема: конкуренции нужны задачи, которые слишком сложно решить

Статья Филипа Меймина *Markets are competitive if and only if P ≠ NP* превращает антимонопольное право в теорию сложности. Цепочка рассуждений: чтобы картель держался, нужно убедительно наказывать нарушителей; чтобы наказывать нарушителей, нужно их обнаруживать; а обнаружение отклонения от сговора при естественном допущении о сложности структуры спроса вычислительно тяжело. Значит, если P = NP, фирмы могли бы эффективно ловить обман, угрозы наказания оставались бы убедительными, и сговор был бы устойчив. Если P ≠ NP, обнаружение невозможно, угрозы рассыпаются, и рынок по умолчанию остаётся конкурентным.

Если добавить его более ранний результат: рынок *эффективен* тогда и только тогда, когда P = NP, получается настоящая невозможность: информационно эффективный рынок и конкурентный рынок взаимно исключают друг друга. Далее Меймин утверждает, что ИИ расширяет вычислительные возможности фирм в сторону режима сговора, и предлагает «вычислительное антимонопольное право»: саму сложность задачи как защитный механизм устройства рынка.

«И всё же мы явно наблюдали устойчивые картели по фиксации цен»

Тред оценил конструкцию, но отверг эмпирику. Убийственное возражение опиралось на факт:

«задача обнаружения сговора вычислительно неразрешима... из-за чего угрозы наказания теряют убедительность, а сговор становится неустойчивым. И всё же мы явно наблюдали устойчивые картели по фиксации цен... Когда теория противоречит фактам, разумно предположить, что ошибается теория.» — комментатор, указывающий на реально существующие картели

Специалисты по теории сложности атаковали несущее слово «неразрешимо»:

«Это мало что даёт, потому что даже если P ≠ NP, в большинстве практических случаев это не имеет значения. NP-задачи каждый день решают эвристиками.» — комментатор о разрыве между худшим случаем и практической сложностью

Другой поместил результат в контекст: интересно, но не удивительно, ведь NP-полнота обычна, а не исключение, как только система становится достаточно сложной. А прыжок к политическим рекомендациям поймали на философском нарушении:

«чтобы установить, что должны делать регуляторы, нужно намного больше обоснований, чем просто математика. Нужен мост от «есть» к «должно быть». Это напоминает мне предостережение Юма о подобных нелогичных переходах...» — комментатор, указывающий на скачок от «есть» к «должно быть» в «вычислительном антимонополии»

Вывод, который тред оставляет экономисту: биусловие — красивое утверждение для худшего случая, но реальные рынки живут в среднем случае, а картели, как и задача коммивояжёра, на практике решаются достаточно хорошо, так что аккуратная дихотомия теоремы протекает везде, где касается реальности.