Wednesday, September 18, 2013

Lance Fortnow: Bounding Rationality by Computational Complexity

Lance Fortnow is professor and chair of the School of Computer Science of the College of Computing at the Georgia Institute of Technology. His research focuses on computational complexity and its applications to economic theory. Fortnow and William Gasarch write in a widely read blog on computational complexity. Fortnow is the author of a recently published book entitled "The Golden Ticket: P, NP, and the Search for the Impossible".

Fortnow s visiting Aalto University and gave an ICS Forum talk at the Department of Information and Computer Science at Aalto University School of Science. The title of his talk was "Bounding Rationality by Computational Complexity".

As a general topic, Fortnow showed how to incorporate computational complexity into various economic models including game theory, prediction markets, forecast testing, preference revelation and contract theory. He discussed, for instance, so called factoring game. The factoring game was introduced in the article "An Approach to Bounded Rationality" by Eli Ben-Sasson, Adam Tauman Kalai and Ehud Kalai. The basic motivation of the paper is how a rational intelligent agent should behave in a complex environment, given that it cannot perform unbounded computations.

Another example discussed by Fortnow was weather forecasting. He discussed Sandroni's theorem that has been published in the article "The reproducible properties of correct forecasts". Fortnow continued by described the results published in the article "The Complexity of Forecast Testing" by himself and Rakesh V. Vohra.

Another interesting topic was computational awareness. The amount of unawareness of an object is the time needed to enumerate that object in a certain environment and a context. A context is a topic like "restaurant". The environment would consist of ways to find restaurant including memories, interactions with others, guidebooks, internet, etc.

Fortnow discussed conditions that characterize wise crowds referring to the book by James Surowiecki on wisdom of crowds. Four criteria were mentioned: diversity of opinion, independence, decentralization and aggregation.

No comments: