Markets are competitive if and only if P != NP

xxpor

The actual paper's title is "Markets are competitive if and only if P != NP" Seems that HN's auto-headline rewriting in this case has made a critical error :) >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. I have to dig more into the paper but I don't see how this follows, except in the most straightforward way. Basically, if everyone uses the same methods to derive price, of course there will be "collusion", or in other words, everyone will have the same price. But this doesn't seem like a result of compute per se, but simply better communication networks and information flows. You could have gotten the same result in medieval England by having everyone post their selling prices on the town square board. Again, I haven't dug into the paper yet, but it seems like what really matters for firms is "compute"/$ (if the "compute" is an LLM or an assistant that has to go walk the 10 minutes down to the square makes little difference) Edit: Isn't another implication of this, that increased compute -> collusion imply that increased compute -> communism becomes feasible? I think this goes to my point above though, the primary problem preventing fully automated luxury communism isn't compute per se, but actually observing the information flows to make it possible. Capitalism famously solves this information problem through the pricing mechanism. So in effect, he's arguing that extra compute makes information gathering more efficient, and at the limit you get perfect information. Which, yeah, I guess so. Assuming everything can be perfectly measured, even theoretically.

kibwen

Keeping in mind the mistake in the HN title (should be "P != NP"), the interesting part of the abstract is this: > 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. (Note that Maymin is the author of both papers.)

cs702

Very interesting. The author claims to have proved that markets can be informationally efficient or competitive, but not both. The implications for policy and regulation are significant. The author looks credible: https://philipmaymin.com/about-philip Thank you for sharing this on HN. -- To the mods: The title needs to be edited to replace the equal sign with not-equal.

vlovich123

> 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. And yet we’ve clearly observed stable price fixing cartels. Maybe the word “unstable” means too much or the game theory model used doesn’t describe the real world accurately. When theory is contradicted by the evidence, it would be wise to consider the theory is flawed.

silentmafia

A 2010 entry by the same author: Markets are efficient if and only if P = NP https://arxiv.org/abs/1002.2284 :)

api

If markets were perfectly efficient, entrepreneurship would not exist. An entrepreneur is, at this level, someone who looks for an arbitrage opportunity in correcting a market inefficiency, usually of the form "there is a market for X, X could be provided, but X is not currently provided."

MostlyStable

I don't have the mathematical chops to really analyze this on my own. Is this a bigger deal than the fact that real world markets already violate all the theoretical assumptions (e.g. unimpeded access to new entrants, perfect information, etc.etc), and so, in practice are never perfectly competitive or efficient?

moomin

I don’t think anyone in the business thinks that the markets are 100% efficient, just that they are sufficiently efficient that beating them is a genuinely hard job requiring heavy, expensive analysis.

FailMore

Would anyone mind explaining what P and NP are?

glimshe

Markets are competitive if and only if P === NP! Now seriously, I wonder if AI collusion/use in investments would add to the market inefficiency and create opportunities for observing investors.

AlotOfReading

The argument structure is interesting, and reminds me a lot of Solomonoff Induction, but constrained into NP by the assumptions. I'm not sure the front half is enough to support the back half of the paper arguing that the current LLM craze means firms are actually running collusion detection algorithms, even unintentionally.

dzink

When everyone uses AI to study the same indicators and figures out how the prices move with those indicators they all start investing at the same time and the prices move together. AI silently gets everyone on the same page.

BoardsOfCanada

A lot of things are only true if P != NP but says nothing about P being within epsilon of NP.

bobkb

This gave me shivers

brunoborges

It's time to forbid bots and HFT. Want to buy/sell a stock? Humans need to manually submit in the system.

wellbehaved

"Third, I propose computational antitrust: the principle that market complexity itself is a competitive safeguard, and that regulators should consider computational difficulty as a design parameter." This "should" is doing a lot of work here. The paper is mainly about a game-theoretic model allegedly corresponding to real markets, but establishing what regulators ought to do requires far more rationale than mere math. It requires a bridge from "is" to "ought." It reminds me of Hume's warning about this kind of non-sequitur: "In every system of morality, which I have hitherto met with, I have always remarked, that the author proceeds for some time in the ordinary ways of reasoning, ... ; when all of a sudden I am surprised to find, that instead of the usual copulations of propositions, is , and is not , I meet with no proposition that is not connected with an ought , or an ought not . This change is imperceptible; but is however, of the last consequence."

jopsen

This offers little because while P != NP, in most practical cases it doesn't matter. NP problems gets solved with heuristics every day.

estebarb

This is interesting. Adam Smith said "People of the same trade seldom meet together, even for merriment and diversion, but the conversation ends in a conspiracy against the public, or in some contrivance to raise prices." The annoying part is that, as the same Adam Smith says, regulating industries would end up enforcing such assemblies, reinforcing the problem... after all, industries can share information via the market itself... And proposed solutions end up being controversial: employees ownership, open source, paying taxes over stocks ownership... or just hoping that colluders will be broken by a randomly ocurring incumbent...

madihaa

the same author 14 years ago. Markets are Efficient if and Only if P = NP and now Markets are competitive if and only if P != NP https://papers.ssrn.com/sol3/papers.cfm?abstract_id=1773169&...

j05ev1f3

This feels like it's pointing in the same direction Hayek was already pointing 80 years ago. This paper says that even if we had enough computing power to solve these problems, Hayek's argument was that we still wouldnt have all the information needed to do those calculations in the first place. That information is spread across millions of people, constantly changing, and often only known locally. So even if the computation became easy, getting all the inputs would still be impossible to achieve