The Quandaries of Quantifying Complexity

My good friend and computer scientest Kyle Burke has recently started a highly interesting blog on his research field: combinatorial game theory. The idea of this field is to use games as a tool for studying issues of complexity. Though his blog is only a month old, some important foundational ideas have begun to rear their heads, one of which I'll explore in this post.

Understanding complexity is important for almost any human endeavor, but defining it in rigorous terms is notoriously difficult. For example, which is the more complicated game, chess or tic-tac-toe? Almost anyone would say chess, but suppose you had a computer that was designed only to play chess. In fact, this computer has no capacity for calculation; it simply has the best move for any given chess position hardwired into its architecture. To get this computer to play tic-tac-toe, you would have to program it to translate each tic-tac-toe position into an analagous chess position, so it could then find the best chess move and translate this move back into tic-tac-toe. This computer would certainly find chess an easier game to play.

Computer scientists have a way around this paradox: instead of looking at individual games or problems, they look at classes of problems. Each problem in the class has a certain size, and they look at how complexity increases in relation to size.

For example, you could easily imagine playing tic-tac-toe on boards of various sizes. Computer scientists can analyze how the complexity of tic-tac-toe varies with the size of the board. (Chess, on the other hand, doesn't generalize as easily to larger sizes, which makes it difficult to talk about its complexity.)

Unfortunately, if we are faced with a real-world issue (such as how to provide for the needs of a large population), we will want to know the complexity of the specific problem at hand, not how the complexity might theoretically scale with problem size. Part of the reason that complexity issues are so often ignored (to the detriment of many well-meaning policies and programs) is that defining and quantifying complexity is so unavoidably slippery.

Further reading

The Criminalization of Poverty

Barbara Ehrenreich had an excellent article in yesterday's New York Times on the many ways that being poor can land you in trouble with the law. One striking example:

In just the past few months, a growing number of cities have taken to ticketing and sometimes handcuffing teenagers found on the streets during school hours.

In Los Angeles, the fine for truancy is $250; in Dallas, it can be as much as $500 — crushing amounts for people living near the poverty level. According to the Los Angeles Bus Riders Union, an advocacy group, 12,000 students were ticketed for truancy in 2008.

Why does the Bus Riders Union care? Because it estimates that 80 percent of the “truants,” especially those who are black or Latino, are merely late for school, thanks to the way that over-filled buses whiz by them without stopping. I met people in Los Angeles who told me they keep their children home if there’s the slightest chance of their being late. It’s an ingenious anti-truancy policy that discourages parents from sending their youngsters to school.

The column was based on a report by the National Law Center on Homelessness and Poverty, which finds that the number of ordinances passed and tickets issued for crimes related to poverty has grown since 2006.

Hey, no one likes poverty, right? Let's pass a law!

The Evolution of Bad Ideas

It is by now common wisdom that our current financial crisis is due in large part to misplaced incentives in our financial system. Analysts and fund managers were rewarded for short-term thinking and risk-taking. If we can rework our financial system to reward long-term, careful planning, it is often argued, we can avoid collapses like this in the future.

While I agree that misplaced incentives were a fundamental problem, the question of how to change this is rather more deep and complex than I think many people realize.

Our economy is, of course, an evolutionary system. Successful businesses grow in size and their practices are imitated by others; unsuccessful businesses vanish. This process has led to many good business practices, even in the financial sector.

However, evolution does not always yield the best outcomes, in biology or in economics. Our recent crisis illustrates two key limitations of evolutionary systems, limitations which allow bad ideas to evolve over good ones.

The first problem has to do with time lags. Suppose Financial Company A comes up with an idea that will yield huge sums of money for five years and then drive the company to bankruptcy. They implement the idea, obfuscating the downside, and soon the company is rolling in cash. Investors line up to give them money, magazines laud them, and other companies begin imitating them.

Not so Company B. Company B believes in long-term thinking, and can see this idea for the sham it is. They persue a quiet, sound strategy, even when their investors begin pulling money out to invest in A.

We would like to think that in the end, Company B will be left standing and reap them benefits of their foresight. But there is a fundamental problem of time-scales here: by the time A folds, B may already be out of business, due to lack of interest from investors. In theoretical terms, there is a fundamental problem when the evolutionary process proceeds faster than the unfolding of negative consequences. In these situations, good ideas never have a chance to be rewarded, evolutionarily speaking.

One might argue that investors, not to mention government regulators and ratings agencies, should have forseen the flaw in A's plan. But this highlights a second limitation of the evolutionary process: it favors complexity. Simple bad ideas can be detected by intelligent agents, but complex ones have a chance to really stick. If Company A's idea was so complicated that no one aside from a few physicists could figure it out, investors and regulators could easily be fooled.

It's not clear to me how to patch these flaws in the evolutionary system. Increased transparency and oversight will help, but unless we can somehow cap the complexity of financial instruments (difficult) or slow down the evolutionary process (impossible), I'm not sure how we'll avoid similar crashes in the future.

Biodiversity and Entropy

On Tuesday, my Erdos number dropped from infinity to four. That's right: after four years of grad school, I am now officially published!

The article, “A New Phylogenetic Diversity Measure Generlizing the Shannon Index and Its Application to Phyllostomid Bats,” by Ben Allen, Mark Kon, Yaneer Bar-Yam, can be found on the American Naturalist website or, more accessibly, on my professional site.

So what is it about? Glad you asked!

Protecting biodiversity has become a central theme of conservation work over the past few decades. There has been something of a shift in focus from saving particular iconic endangered species, to preserving, as much as possible, the wealth and variety of life on the planet.

However, while biodiversity may seem like an intuitive concept, there is some disgreement about what it means in a formal sense and, in particular, how one might measure it. Given two ecological communities, or the same ecological community at two points in time, is there a way we can say which community is more diverse, or whether diversity has increased or decreased?

Certainly, a good starting point is to focus on species. As the writers of the Biblical flood narrative were in some sense aware, species are the basic unit of ecological reproduction. Thus the number of species (what biologists call the "species richness") is a good measure of the variety of life in a community.

But aren't genes the real unit of heredity, and hence diversity? Is the number of species more important than the variety of genes among those species? Should a forest containing many very closely related tree species be deemed more diverse than another whose species, though fewer, have unique genetic characteristics that make them valuable?

And while we're complicating matters, what about the number of organisms per species? Is a community that is dominated by one species (with numerous others in low proportion) less diverse than one containing an even mixture?


There is no obvious way to combine all this information into a single measure for use in monitoring and comparing ecological communities. Some previously proposed measures have undesirable properties; for example, they may increase, counterintuitively, when a rare species is eliminated.

In this paper we propose a new measure based on one of my favorite ideas in all of science: entropy. You may have heard of entropy from physics, where it measures the "disorderliness" of a physical system. But it is really a far more general concept, used also in mathematics, staticstics, and the theory of automated communication (information theory) in particular. At heart, entropy is a measure of unpredictability. The more entropy in a system, the less able you will be to accurately predict its future behavior.

The connection to diversity is not so much of a stretch: in a highly diverse community, you will be less able to predict what kinds of life you will come across next. Diversity creates unpredictability.

To be fair, we weren't the first to propose a connection between diversity and entropy. This connection is already well-known to conservation biologists. But we showed a new and mathematically elegant way of extending the entropy concept to include both species-level and gene-level diversity. It remains to be seen whether biologists will take up use of our measure, but whatever happens I am happy to have contributed to the conversation.

A Middle/High School That Teaches Complex Systems Through Games??!

A new school is opening in New York for grades 6-12 that completely blows my mind. The Quest to Learn school combines games and complex systems in a way that pretty much would have made my life as a teenager. Hell, I wouldn't mind going back to high school now if I got to go here. I'll let them describe it:

Mission critical at Quest is a translation of the underlying form of games into a powerful pedagogical model for its 6-12th graders. Games work as rule-based learning systems, creating worlds in which players actively participate, use strategic thinking to make choices, solve complex problems, seek content knowledge, receive constant feedback, and consider the point of view of others. As is the case with many of the games played by young people today, Quest is designed to enable students to “take on” the identities and behaviors of explorers, mathematicians, historians, writers, and evolutionary biologists as they work through a dynamic, challenge-based curriculum with content-rich questing to learn at its core. It’s important to note that Quest is not a school whose curriculum is made up of the play of commercial videogames, but rather a school that uses the underlying design principles of games to create highly immersive, game-like learning experiences. Games and other forms of digital media serve another useful purpose at Quest: they serve to model the complexity and promise of “systems.” Understanding and accounting for this complexity is a fundamental literacy of the 21st century.

Elsewhere they go into a bit more detail about how games are used to teach different subject areas:

At Quest students learn standards‐based content within classes that we call domains. These domains organize disciplinary knowledge in 21st certain ways—around big ideas that require expertise in two or more traditional subjects, like math and science, or ELA and social studies. One of our domains— The Way Things Work—is an integrated math and science class organized around ideas from design and engineering: taking systems apart and putting them back together again. Another domain—Codeworlds—is an integrated ELA, math, and computer programming class organized around the big idea of symbolic systems, language, syntax, and grammar. A third domain—Being, Space and Place—an integrated ELA and social studies class—is organized around the big idea of the individual and their relationship to community and networks of knowledge, across time and space. Wellness is the last of our integrated domains, a class that combines the study of health, socio‐emotional issues, nutrition, movement, organizational strategies, and communication skills.

OMG!OMG!OMG!OMG!

One of my favorite aspects of this school is that they have a separate staff of game designers working together with their teachers. As a former teacher I can tell you that designing good, creative lessons is a relatively different skill-set from actually implementing these lessons in front of a class and following up with your students, and that doing both well requires more time than is physically possible without traveling at relativistic speeds. So having designers who are there at the school and understand the teachers' needs, and who have the time to make great lessons, is a really really good idea.

At IIASA

This is just a brief note to let everyone know I'm spending the summer at IIASA, a scientific policy research institute located just outside of Vienna. IIASA focus on systems analysis of global problems such as climate change, land use, demographic changes, public health, ecology, and energy. They don't seem to use the phrase "complex systems" much, but they're clearly talking about the same thing.

I happen to be one of 53 lucky graduate students to be selected for this year's Young Scholars Summer Program, meaning I get to paid to live in Vienna and do research. Can't really complain about that. Tomorrow I get to hear mini-presentations on everyone's research proposals, which should be very interesting. My own project will be on the long term, gradual evolution of cooperation in spatially structured populations, using a mathematical framework known as adaptive dynamics.

I'm expecting to learn a lot here, and I'll share as much as I can with you readers. Looking forward to it!

Nature Minus Humans?

From the "nothing is quite so simple" department, a Boston Globe article this week points out a hidden legacy of the conservation movement: The expulsion of native peoples from their land.

Starting with Yosemite in the late 19th and early 20th centuries, the pattern of forcing indigineous civilizations from their ancestral land in order to create wildlife reserves and national parks has been repeated across the country and the world.

The conflict is... compelling the conservation movement to grapple with the effects of its own century-long blunder, and with its origins as an American movement driven largely by nature romantics and aristocratic men determined to protect their hunting grounds. Not only has it dispossessed millions of people who might very well have been excellent stewards of the land, but it has engendered a worldwide hostility toward the whole idea of wildland conservation - damaging the cause in many countries whose crucial wildland is most in need of protection.

The article describes how indigineous peoples threatened with displacement across the globe have begun to band together to force a change in the conservationist mindset that humanity and nature are antithetical.

Reporting like this is why the Boston Globe needs to stay in business.