Thursday, March 24, 2016

Complexity versus Complexity

For those interested, I've started writing posts for the Predictwise Blog. Predictwise makes predictions of future events such as who will win the Republican Nomination (currently Trump with an 80% probability) based on prediction markets and other betting sites. This has been a fascinating election in terms of predictions, strategies, rules and game theory and I'm happy to try and makes sense out of it over at Predictwise without subjecting my readers here at Computational Complexity with too many political posts.

A reader had asked me to comment on a Slate article The Theory of Everything and Then Some, a book review of John Miller's A Crude Look at the Whole: The Science of Complex Systems in Business, Life, and Society. John Miller is a social scientist who works on the other "complexity theory" that studies that "simple local rules can have complex global implications". Often complex systems work quite well, like the invisible hand of the economy, but sometimes things can go wrong and the article often mentions the "flash crash" of trading programs reacting to each other causing a major drop in stock prices in May of 2010.

Our fields with the similar names are not as different as might appear. Much of what they study are inherently computational-like processes and we also look at emergent behavior from simple operations of Turing machine; read, write and move the tape. What they call non-linear we call computation. We do take very different approaches. The computational complexity theory community proves theorems where we can and helps understand the mathematical challenges of when we can't. The other complexity theorists try to explain by examples, simulations and simplified models.

The two communities often, but not always, seem to have disdain for one another and that's a shame. The tools of computational complexity can help understand the power and limitations of complex systems. These collaborations require them to understand how we can help them and for us to be willing to work on problems that may not yield difficult-to-prove theorems. That's what attracts me to prediction markets, a very simple kind of information aggregation system that still is very difficult to analyze as a computational mechanism.

What's missing from the article is how tools like machine learning can play in helping to predict the outcomes of many complex systems. The big deluge of data that starts off the article may add to the complexity but it almost paradoxically also makes it possible to learn from it.


  1. It is so obvious from you PredictWise post that your preferred candidate is Clinton and you don't like Trump.

    If the only thing one cares about who become president then yes, you are right. But there are more at stake. Clinton has a history of flip-flopping and the only thing that is keeping her from flip-flopping on many of positions she has taken so far is Sanders being in the race. I don't want TPP, Bill Clinton opposed NAFTA during the election and then flip-flopped after it.

    The reason Republicans hate Trump is because he is not that he is not a religious fundamentalist like Cruz nor that he is not a neocon like Rubio. They hate him because he is not for free-trade and globalization.

    The truth is that a large number of Americans have been at the losing end of globalization and both establishment Republicans and Democrats including Clinton are pro-globalization. Globalization benefits poor in undeveloped countries and rich in the developed countries but it has been really bad for middle class in the developed countries. Ordinary American voters are often portrayed as not very intelligent but they do understand who is likely to stand for their interests. That is why Trump's support is not effected by all the negative ads run against him, people can agree with all the criticism of Trump and still vote for him because it is in their interest.

  2. ...and this is related to Computational Complexity how?