The paradox of order and randomness

Consider the following two images:




First view each image as is, and then click on them to see larger versions. Ignore for a moment the different sizes, and the copyright notice in the second picture (hope I'm not breaking any laws!) What's going on in these pictures?

The first is a randomly generated image, in which a computer essentially flipped a coin to decide the color (black or white) of each pixel. The second is composed of alternating black and white pixels in a checkered pattern (click on the image to see this clearly.)

At this resolution, the first picture still has some texture to it. But zoom out a bit more and it would reduce to a uniform grey, just like the second.

This highlights something of a paradox in complex systems theory: complete randomness is actually pretty boring. Sure, it's unpredictable, but because it has no structure, there's not much else you can say about it. And if you squint at it, it all averages out to grey. Contrast this to the following fractal image:



Now this picture has a lot of interesting structure to describe, like most complex systems.

Why is this a paradox? Because according to the defintions of complexity we discussed some months ago, a completely random system is more complex than anything else! Any order or structure in a system makes it easier to describe, thereby reducing complexity according to conventional definitions. So the fractal is actually less complex than the random image.

Complex systems researchers have recognized this problem for a long time, but there's no consensus on how to resolve it. Some have suggested adopting a different definition of complexity that behaves something like this:



That is, complexity is greatest somewhere between total order and complete randomness. But this is unsatisfying; complexity is not a mere mixture between order and randomness, but a delicate balance combining features of the two.

Of course, I have my own opinion as to how this paradox should be resolved. But that's a tale for another time.

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!

On Communism

Communism was always a mystery to me. Why was it that all the countries supposedly founded on the egalitarian ideals of Marx ended up as repressive police states? Was it just a historical accident, or is there a deeper reason?


In this post I will argue that the failure of communism was the inevitable result of a failure to manage complexity. I expect this thesis to be somewhat controversial--chime in if you have an opinion. Also, I am not a history expert, so please forgive and correct any errors I make. As in many other areas, my thinking on this issue owes a large debt to Yaneer Bar-Yam.

Let's start with Marx's principle: "from each according to his ability, to each according to his need." According to this principle, everyone performs the tasks they are good at, and the goods and services produced are redistributed to those who need them. If this process runs smoothly, the needs of the entire society are taken care of.

However, as we all know from personal experience, it's complex enough to figure out what one person's abilities and needs are. Imagine trying to discern the needs and abilities of an entire country, and how best to match the needs and abilities with each other. To do this in a way which takes the idiosyncasies of each individual into account would be a massive complexity overload; it would take practically every individual in the country just to do the planning, with no one left to do the actual work.

So how did the USSR and other communist societies deal with this problem? Recall from last time the only way to control a complex system is to coercively reduce the system's complexity. This is precisely what happened in communist countries: they turned into permanent police states. In order for the leaders to control the economies they were trying to plan, the populace had to be forced into conformity and regimentation, i.e. lower complexity. People were forced into occupations that were not the best match for their talents, and governments made the simplifying assumption that everyone's needs were pretty much the same. It was the only way the organizational problem could be solved.

These simplifications worked, for a time. Eventually, in the USSR, people grew tired of the coercion and the economy stagnated. Gorbachev sought to reinvigorate the nation by allowing some economic and political freedoms, not realizing that the lack of freedom was precisely what was made the organizational system possible. No longer able to control the recomplexified system, the government fell.

So could communism ever work? Not, in my view, on the scale of a whole country. The principle of need and ability could be applied to smaller groups, where the organizational challenges are less severe. We see this, for example, in cooperative communities such as the kibbutzim of Israel (though even these are suffering from complexity management challenges.) In these smaller communist societies, you miss out on the efficiency provided by economies of scale, and there is no opportunity for highly specialized professions such as neurosurgeon or theoretical physicist. But the upside is the possibility of a society where everyone's needs are taken care of. Not such a bad deal.

Join us next time when we ask, "Does capitalism do any better?"

How Complex is a Human?

We humans are an egotistical bunch. We'd like to think that we are capable of anything, that our minds are infinite, and that there is no limit to our potential ingenuity.

Nevertheless we are, by any measure, creatures of finite complexity. Our bodies and our brains contain a finite number of cells, we live a finite amount of time, and at any given time there are a finite number of things we are physically and mentally capable of doing.

Since our complexity is finite, we should be able to quantify it somehow. As we discussed last time, there are different ways of quantifying complexity. We could look at ourselves as a system of cells and chemicals, and ask how many pages it would take to write a complete description of how a human is composed of these parts. Alternatively, we could look at ourselves as active beings and ask how many potential actions we could take at any given instant. Or how many actions we actually take (on average) over the course of a lifetime. Yaneer Bar-Yam has suggested this example: You could record a digital movie of a person from birth until death, store this movie in a digital file, and calculate the size of this file in gigabytes. I don't know if any of these computations has ever been tried, but each would give you an approximate number which quantifies just how finite we are.

Scary, huh? At least I find it so.

This may seem like just an interesting excercise, but it has important consquences due to the following fundamental rule:

You can't control a system that is more complex than yourself.

The reason for this is simple: If a system is more complex than you, it has more possible actions than you have potential responses. So it will eventually present you with a situation for which you have no response.

To illustrate this rule, suppose you are trying to manage a group of people; say, a family, business, class, or club. You might wish to control the actions of all of them, to make sure they don't act against your wishes. However, the group is more complex than you are because there are more of them then there are of you. The only way to control them completely would be to reduce the complexity of the group; for example, you could chain them to a wall and thereby limit their potential actions.

If you wish to organize a group without such restrictive measures, your best option is to put incentives and disincentives in place to promote the actions you wish. Then step back and let the group evolve as a system. If you designed your incentives correctly, the group should evolve into a system with the properties you desire. If not, the incentives should be changed. But no matter how you set up the system, you will not be in control of it. The group and its members will be making their own decisions, and different groups will evolve differently under the same set of incentives. This is the nature of the game.

Tune in next week, when we find that this discussion has massively political implications!

Quantifying Complexity

Complexity matters. This will hopefully become evident through the course of our discussion, but for now let's accept the principle that, in a great many situations, the extent to which something is complicated can be hugely important.

For a mathematician or scientist, a natural step after identifying something important is to attempt to quantify it, in the hopes of determining some of its properties. Us humans actually have a decent intuitive sense of different quantities of complexity. For example, we could all agree that Mozart's 40th is more complex than Twinkle Twinkle Little Star, or that sovling a crossword puzzle is more complex than tying a shoe. Other comparisons are less clear: Is a horse a more complex animal than a lion? Is China's economy more complex than India's?

Complexity researchers have identified several different ways that complexity can be quantified. These measures roughly fall into three categories:

• Variety - the complexity of an object can be quantified in terms of the number of actions it can take or the number of states in which it can exist.
  
• Descriptive complexity - the complexity of an object can be quantified in terms of the length of the shortest complete description of that object
  
• Algorithmic complexity - the complexity of a process can be quantified in terms of the number of steps or amount of time required to complete that process.
  

These three categories can be linked mathematically, which supports the idea that they are three expressions of the same concept rather than three different concepts. However, none of these can be unambiguously applied to the real world. For example, the number of actions or states of an object can be difficult to quantify. How many different actions can a human take? Descriptive complexity notions are dependent on the language used to describe something, and on what counts as a "complete" description. Similarly, algorithmic complexity notions depend on how a process is broken into tasks. This is not to say that the above quantification schemes are useless; just that care should be used in applying them and the values they give should be seen as approximate.

This approximateness is a problem for many scientists, who are used to dealing with the exact. How can we apply our analytical tools to a quantity which can never be precisely measured?

The way forward, in my opinion, is as follows. We (complex systems researchers) will investigate abstract models in which complexity can be mathematically quantified. The goal of investigating such models will be to discover laws of complexity which may carry over to the real world. At the same time, these laws must be checked against real-world experiment and observation. Because of the semi-fuzzy nature of complexity, the laws we discover will likely not be quantitative (e.g. F=ma or e=mc^2), but qualitative (e.g. "energy is conserved.")

In the near future, we will investigate two examples of such laws: Occam's Razor (the simplest explanation is the likeliest) and Ashby's Law (an organism must be as complex as its environment.) In the meantime, can anyone think of other qualitative laws of complexity/complex systems?