Christos Papadimitriou

Christos Papadimitriou, one of the world's foremost computational theorists, gave a talk Thursday at MIT entitled "The Algorithmic Lens: How the Computational Perspective is Changing the Sciences." Through a series of eight "vignettes" in math, physics, biology and economics, he showed how ideas from computer science have influenced thinking in all other sciences. I don't know if he explicitly aligns himself with the complex systems movement, but the ideas he presented were very much in line with complex systems thinking, and gave me a lot to ponder.

When mathematicians and physicists look at a problem, the main questions they ask are "Is there a solution?" and "How do we find it?" If there is even a theoretical procedure for finding the answer, the mathematicians and physicists are usually satisfied. What computer scientists bring to the table is another question "How complex is the solution procedure?" Computer scientists ask this question because they know of many problems which can be solved in theory, but even the fastest computer in the world couldn't solve them before the end of the universe. Computational complexity started as a practical concern of deciding which problems can be solved in reasonable amounts of time, but it was soon recognized as an interesting theoretical problem as well. Papadimitriou's thesis is that importance of this question has now spread beyond computer science to all of the natural and social sciences.

In this post I'll focus on two of his vignettes. My next post will focus on a third.

The first is from economics. It is a central tenet of economic theory that a market will always "find" its equilibrium: that magical point where supply, demand, and price are perfectly aligned. However, Deng and Huang, among others, have shown that finding such an equilibrium is not polynomially bounded, meaning that even very powerful computers can't find equilibria in large markets.

Now, if the market itself is performing computations as its various players try to sort out optimum prices and production levels. If it were true that the market could always find its equilibrium, this would constitute a "proof" that the the problem can be solved relatively easily. In fact, you could just write a computer program to emulate what the market does.

But since an easy solution is theoretically impossible, this must mean that markets don't always find their equilibria. And this fact is actually obvious from looking at how markets really behave: they go up and down, they crash, they generally do strange things. So this tenet of economic theory must be due for a serious revision.

A second interesting vignette was ostensibly about the brain, though it has much wider implications. As we make decisions, we can often feel different parts of our brain working against each other. Part of us wants something and part of us wants something else. Papadimitriou asked, "Could this possibly be the most efficient way to make decisions?" It doesn't seem particularly efficient. And if it isn't, why has our brain, over millions of years of evolution, developed such an inefficient process?

A recent paper of Livant and Pippenger cast the problem this way: Can an optimal decision-making system ever contain agents with conflicting priorities? The answer is no in general, but yes if the system has limited computational power, i.e. limited resources for dealing with complexity. Which of course is true for every real-world decision-making system, including brains.

Their reseach implies that, not only does it make sense for our brains to seemingly conflict with itself, but also that, if you are assembling a decision-making team, it actually makes sense to include people who disagree with each other. A belated lesson for Mr. Bush, perhaps?

Next time: phase changes!