Markets are competitive if and only if P != NP

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.

> markets can be informationally efficient or competitive, but not both

Really interesting conclusion, but I can't help but feel this is overly reductive, as stated. Surely market efficiency is a sliding scale and so is market competitiveness.

Okay, so a perfectly competitive market cannot also be a perfectly efficient market. Interesting! But I'm confused about how this may work when efficiency and competitiveness are a sliding scale. Should we think of this as one axis (with a spectrum from efficiency to competitiveness) or as two separate axes that just happen to have an exclusive relationship between their extremes?

A 2010 entry by the same author:

Markets are efficient if and only if P = NP https://arxiv.org/abs/1002.2284

:)

These things should not be submitted here unless there is meaningful editorial/peer commentary about it being significant or correct. There are dozens of bogus attempts to prove and disprove this

There's a long history of proving results like this.

NP-Completeness is the norm, not the exception. Any system that's complex enough is almost surely NP-Complete. For similar reasons, Turing Machine Equivalence is also the norm, not the exception.

These results are interesting but not unexpected. A more interesting question is under what conditions is the problem difficult to find solutions for. Many NP-Complete instance ensembles turn out to effectively have polynomial time solutions (3-SAT w/ uniform clause variable choice, Hamilton Cycles in Erdos-Renyi random graphs), so proving NP-Completeness is not a death knell for approximation.

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.

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

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?

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&...

This offers little because while P != NP, in most practical cases it doesn't matter.

NP problems gets solved with heuristics every day.

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

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.

This paper has all the hallmarks of being crackpot with GPT.

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.

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.

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.

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...

Would anyone mind explaining what P and NP are?

It's time to forbid bots and HFT.

Want to buy/sell a stock?

Humans need to manually submit in the system.

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."

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.)

"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."

> 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.

[flagged]

[dead]

This gave me shivers