Lecture 11: Algorithmic Game Theory

Decentralized financial exchanges can reach stable, competitive states by replacing complex Nash equilibrium calculations with coordinated equilibrium concepts and efficient machine learning, which are better suited for the strict computational limits of blockchain code.

• Dubey's market — A limit order system where non-cooperative strategies naturally result in competitive outcomes [02:28].
• Computational limits — Standard Nash equilibrium calculations require exponential time, making them unfeasible for decentralized networks that demand predictable execution speed [19:36].
• Easier alternatives — Correlated and coarse correlated equilibria allow for polynomial-time calculation, making them practical for real-world software [18:31].
• No-regret learning — Machine learning agents optimize strategies based on previous feedback, which removes the need to compute an entire joint probability distribution that grows exponentially with the number of players [46:24].
• Implementation trade-offs — Design choices between "full information" settings, which converge quickly but cost more to calculate, and "bandit" settings, which are cheaper but converge slowly, dictate overall performance [1:08:55].
• Front-running protection — Centralized block-matching prevents node validators from reordering transactions to extract profit, a vulnerability in older exchange models [16:30].

How does the timing of a player's commitment differ between correlated and coarse correlated equilibrium? Why do blockchain systems enforce limits on code execution time?