Perfect Competition Only Exists Because P≠NP: What Computational Complexity Reveals About Algorithmic Collusion

Every economics textbook opens with the same picture: perfect competition. Thousands of sellers jockeying for customers, prices sliding gracefully toward some optimal point, everybody better off. It’s a beautiful image. But a strange argument has been surfacing at the border of computer science and economics — that this equilibrium survives not because markets are virtuous, but because collusion is computationally too hard to pull off. And the moment AI cracks that difficulty, the market quietly slides into collusion instead.

I’ll admit it sounds like a stretch on first hearing. What does a gnarly math problem like P vs NP have to do with the price tag on a hotel room? Let’s take it apart piece by piece.

P vs NP in Five Minutes

Start with the basics. P vs NP is the most famous unsolved problem in the 60-year history of computer science, and you don’t need a PhD to get the gist.

Some problems are easy to solve quickly. Call those P. Other problems are hard to solve, but if someone hands you an answer, you can check it quickly. Call those NP.

A giant Sudoku puzzle is the classic example. Solving it from scratch takes forever. Verifying that a completed grid follows the rules takes a glance. Hard to find, easy to check. That gap is the essence of NP.

The P vs NP question is deceptively simple: if a solution is easy to verify, is it secretly easy to find too? If P equals NP, nearly every hard problem in the world collapses into an easy one — encryption breaks, optimization becomes instant. If P does not equal NP, some problems are just inherently slow to crack, no matter how clever you are. Almost every expert bets on P≠NP. That bet is the quiet foundation under a lot of things we take for granted, including, apparently, competitive markets.

A Market Is Just a Giant Computer

Here’s where economics walks in. If you reframe the market’s search for an equilibrium price as a computer solving a problem, the whole thing looks different.

Friedrich Hayek called the market an “information processing device” decades ago. Millions of buyers and sellers, each holding a scrap of private knowledge, compress it all into a single signal: the price. Push that idea through complexity theory and finding a market equilibrium becomes, literally, a computational problem.

And that computation is often brutally hard. A body of research shows that computing a general market equilibrium is at least as hard as NP, sometimes harder. Tangle enough goods together, layer in enough messy preferences, and calculating the true optimal price becomes practically impossible.

Now pause. Is that bad news? Weirdly, no. That very difficulty may have been the shield protecting competition all along.

Why Collusion Was Always Hard

Picture a cartel. A handful of firms secretly agree to keep prices high. Terrible for consumers, lovely for the firms.

Pulling it off takes work. You have to monitor your co-conspirators for signs of cheating. You have to calculate the optimal collusive price. You have to keep re-tuning it as the market shifts. All of that demands heavy computation and constant information-sharing.

When humans ran the show, that was a natural barrier. People conspiring in a room leave evidence, do math slowly, and can’t catch a defector the instant they break ranks. So most markets stayed at least somewhat competitive simply because collusion was a hassle — too slow, too risky, too hard to coordinate.

Which yields a provocative claim: perfect competition is only possible when P≠NP. Put plainly, markets stay competitive precisely because the computation collusion requires is inherently hard. Make that computation easy, and the friction that kept everyone honest evaporates. Collusion becomes the default setting.

When AI Erases the Friction

Now the uncomfortable part. AI pricing algorithms are dissolving exactly that computational difficulty.

This is already happening. When multiple firms run the same AI pricing software, their prices climb in lockstep — no phone calls, no smoke-filled rooms. The algorithm reads market data in real time, learns how rivals respond, and arrives on its own at the conclusion that “cutting price now just hurts us both.” Nobody signed anything, but the outcome is a cartel. Researchers call this algorithmic collusion.

The key shift is this: the monitoring and coordination that collusion demands used to be prohibitively expensive for humans. Not for AI. Reinforcement-learning agents discover strategies for watching and punishing each other — reward-and-retaliate schemes nobody explicitly programmed — entirely on their own in experimental settings. The computational wall has come down.

And this isn’t a chalkboard thought experiment. The US lawsuits over rental-pricing software like RealPage, and the growing number of regulators in multiple countries starting to probe AI-driven price coordination, show the worry has legs.

So What Should We Actually Fear

One caveat worth naming: over the last 30 days, there hasn’t been much loud public debate on this specific thread. This isn’t a viral controversy yet — it’s a corner where a handful of researchers and regulators are quietly wrestling. Which, to me, is exactly why it’s worth understanding now, before it hits the headlines.

Here’s the summary. The market competition we treat as natural may have been an accident — sustained only because collusion happened to be computationally too hard. AI is lowering that difficulty fast. The law punishes explicit agreement as collusion, but algorithms manufacture the results of collusion with no agreement at all. How existing antitrust law plugs that gap is the real homework ahead.

So a question to leave you with. When a price emerges that nobody agreed to and everybody loses on, who do we hold responsible? The algorithm? The company that deployed it? Or all of us, for not seeing it coming?