New algorithm solves century-old economic equilibrium problem in polynomial time

A team led by Denizalp Goktas, Klára Chura, Alp Emin Guneri, and Amy Greenwald has published a paper on arXiv that cracks a 150-year-old problem in economic theory: how to compute Walrasian equilibrium efficiently and reliably. The classic tâtonnement process, proposed by Léon Walras in 1874, works for many economies but famously fails in the Scarf economy—a pathological case that causes prices to oscillate indefinitely. The researchers reformulate the equilibrium problem using variational inequalities (VIs) and introduce a class of mirror extragradient algorithms. Their key insight is to show that any balanced economy (including Arrow-Debreu) corresponds to a VI satisfying the Minty condition, even though the mapping is generally discontinuous. By applying mirror extragradient algorithms, they derive a new process they call mirror extratâtonnement, which converges to equilibrium in polynomial time for variationally stable economies with bounded elasticity—including both the WARP-satisfying economies and the Scarf economy.

The theoretical guarantees are backed by extensive experiments on large-scale economies. The team tested mirror extratâtonnement on Arrow-Debreu models with Cobb-Douglas, Leontief, and constant elasticity of substitution (CES) consumers, as well as the Scarf economy. In every case, the algorithm converged quickly without any failures. This is a significant advance because prior methods either lacked convergence guarantees or required restrictive conditions. The work bridges computational game theory, optimization, and mathematical economics, offering a practical tool for analyzing and simulating general equilibrium models. Potential applications include policy analysis, market design, and multi-agent AI systems where decentralized price discovery is critical.