The author looks credible:

  https://philipmaymin.com/about-philip

--

To the mods: The title needs to be edited to replace the equal sign with not-equal.

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.

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

:)

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

NP problems gets solved with heuristics every day.

Now seriously, I wonder if AI collusion/use in investments would add to the market inefficiency and create opportunities for observing investors.

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

Want to buy/sell a stock?

Humans need to manually submit in the system.

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

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

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.