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.