Game Theory and Cooperation

Why do gas stations on the same corner charge the same price? Why do they occasionally drop into a price war, then snap back to coordination? And what does any of this have to do with Cantor's diagonal argument?

The standard answer — Nash equilibrium, rational agents, stable strategies — turns out to be less stable than the textbooks suggest. The interesting question isn't "why do rational agents defect?" but "how do real agents cooperate when theory says they shouldn't?"

Edgeworth Cycles: Game Theory You Can See at the Pump

The Australian fuel market is one of the cleanest natural laboratories for game theory ever documented. Petrol stations in cities like Perth and Brisbane exhibit remarkably regular price cycles — prices spike suddenly, then decline slowly over days until the next spike. These "Edgeworth cycles" are named after the 19th-century economist Francis Edgeworth, who predicted that oligopolists with capacity constraints would oscillate rather than settling into a stable equilibrium.¹

The mechanism is straightforward once you see it. When prices are high, every station has an incentive to undercut slightly — steal a few customers by being a cent cheaper. This triggers a cascade of undercutting that drives prices down toward cost. But once margins are squeezed thin enough, one firm jumps its price back up. If others follow, the cycle restarts. If they don't, the price-raiser loses all its customers and capitulates back down.

What's striking is that the Australian Competition and Consumer Commission has documented these cycles with enough data to test theoretical predictions against reality. The cycles aren't perfectly regular — they're disrupted by holidays, weather, new entrants — but the underlying game-theoretic structure is visible. Competing firms, acting in their own interest with imperfect information, spontaneously generate oscillations that no individual firm planned. It's emergence in an economic system, driven by the same tension between local optimization and global dynamics that produces oscillations in ecological models and cellular automata.¹

The practical lesson is counterintuitive: transparent pricing makes consumers worse off. When prices are posted publicly and updated in real time, it becomes easier for firms to monitor and punish undercutting, which supports tacit collusion. The cycles that look like competition — prices falling! — are actually the visible signature of a system that spends most of its time near the cooperative (high-price) equilibrium.

The Prisoner's Dilemma, Taken Seriously

The classic prisoner's dilemma is a toy. Two players, one round, cooperate or defect. But the iterated version — where you play the same opponent repeatedly and can remember what they did — is where things get genuinely complicated.

In 2012, a team of LessWrong-adjacent researchers pushed this further: what if both players are programs that can read each other's source code?² This is the "program equilibrium" setup, and it transforms the problem completely. If I can verify that your code cooperates whenever mine does, then cooperating becomes rational — not because of warm feelings, but because mutual source-code inspection eliminates the uncertainty that makes defection attractive.

The paper's formal contribution is a series of programs that robustly cooperate with cooperative partners and defect against defectors, even when the opponent is allowed to be computationally more powerful. The key insight is that cooperation becomes a provable property of the strategy pair rather than a fragile social norm. Your cooperating bot carries a proof that it cooperates with any bot that cooperates with it, and that proof is machine-checkable.

This connects to something deeper about the nature of trust. In the one-shot prisoner's dilemma, defection is rational because you have no information about the other player's decision. In the iterated version, trust emerges from repeated interaction — but it's fragile, vulnerable to trembling hands and misunderstandings. In the program-equilibrium version, trust is verified — it follows from the logical structure of the programs rather than from empirical observation of past behavior. It's the difference between "I think you'll cooperate because you have before" and "I know you'll cooperate because I can read the proof."

Whether this has real-world implications depends on how much of human cooperation involves something like mutual source-code inspection. I think more than we'd expect — when you know someone's incentives, beliefs, and constraints well enough, you're doing a rough version of reading their source code. The LessWrong crowd would call this "decision-theoretic cooperation," and while the formal machinery is exotic, the intuition is not: you cooperate because you can see that cooperation is the locally optimal joint strategy, and you can verify that the other party sees it too.

The Diagonal Connection

There's a beautiful structural link between Cantor's theorem (some infinities are bigger than others), the prisoner's dilemma (rational self-interest can produce collectively terrible outcomes), and the halting problem (no program can determine whether arbitrary programs halt).³

The connection is the diagonal argument. In Cantor's proof, you assume you have a complete list of real numbers and construct one not on the list by changing the nth digit of the nth number. In the halting problem, you assume you have a program that decides halting and construct one that does the opposite of what the decider predicts. In the prisoner's dilemma with source-code reading, a similar diagonalization lurks: if you try to construct a universal strategy that always does the "right thing" against any opponent, you can always construct an opponent that defeats it by doing the opposite of whatever it predicts.

This is more than a cute analogy — it's the same mathematical structure appearing in set theory, computability theory, and game theory. All three involve a system trying to model or predict itself, running into the fundamental impossibility of complete self-reference. Cantor shows you can't list all reals. Turing shows you can't predict all computations. And the game-theoretic version shows you can't construct a single strategy that dominates all possible opponents. The diagonal method is a universal limitation theorem: any sufficiently expressive system can be turned against itself.³

This connects to Information And Computation through Chaitin's information-theoretic Gödel: you can't derive more information from axioms than the axioms contain. The diagonal argument is why. Whenever a system rich enough to encode self-reference tries to completely describe itself, it generates contradictions — or, equivalently, truths it cannot prove, reals it cannot list, strategies it cannot beat. The prisoner's dilemma version of this is perhaps the most accessible: the reason there's no universally optimal strategy isn't just that opponents are tricky. It's that the structure of strategic interaction contains the same self-referential loop that Cantor exploited in 1891.