Economists are sometimes content asking whether or not a banking system could be stable or a market could continue to grow. But they and other scientists could benefit from a computational view that asks not just whether the right conditions exist but also how hard it is to find them, according to a commentary published today in Proceedings of the National Academy of Sciences.
The "how hard?" question is about computational complexity, says Christos Papadimitriou, a University of California-Berkeley computer scientist and the commentary's author. "Nature, [people]—they are doing some kind of computation," he says, but some computations are easier than others. For nature to compute the best possible kind of life for every environment on Earth is profoundly complex, an observation that informs biologists' understanding of evolution. In fact, biologists don't think nature actually finds the optimal kinds of life—it's far too difficult a problem—an observation that helps them understand why life is so diverse.
Under certain assumptions about the economy, free markets produce stable, socially optimal outcomes, in the sense that no one person can improve his or her lot without hurting someone else.
Societies face a similar problem. For example, under certain assumptions about the economy, free markets produce stable, socially optimal outcomes, in the sense that no one person can improve his or her lot without hurting someone else. Politicians and the occasional novelist have used that claim to promote an unregulated free market.
That makes sense if you don't contemplate the problem any further, but thinking about markets in terms of computational complexity puts the problem in a different light. Finding an economic outcome that's stable and benefits everyone is a lot like the evolution problem. It's not the hardest problem to solve, but as the number of economic players grows, the problem gets exponentially harder—tough even for a computer to deal with.
That has an important consequence. "You can't expect a market to get there because you can't expect a computer to get there," Papadimitriou says. And if a market can't get to a stable, socially-optimal solution, whether or not a solution exists becomes a less interesting—or at least quite different—question.
Ben Golub, a Harvard economist who studies social and financial networks, says that's an important perspective, though it may not always be the most valuable one. "Much of complexity theory is focused on worst-case complexity," he writes in an email. "So 'hardness' results that at first seem very sweeping" might not always apply. For example, real-world markets might be set up—intentionally or otherwise—to make solving certain economic problems computationally easier.
Still, "whatever it is that markets do, they are doing a sort of computation," Golub says, and Papadimitriou and other computer scientists pose "a provocative, invigorating challenge for economists." In a way, it's a return to economists' roots, too: In the 1950s and '60s, economists thought long and hard about how societies could reach optimal solutions, or at least an equilibrium. Now, Golub says, "computer science has reinvigorated this hugely important area."