ICS Forum talk by Lance Fortnow, Wed 18 Sep at 13:15

[Pekka Orponen]

ICS Forum talk:

Bounding Rationality by Computational Complexity

Prof. Lance Fortnow
Georgia Institute of Technology

Abstract:

Traditional micro-economic theory treats individuals and institutions as
completely understanding the consequences of their decisions given the
information they have available. These assumptions may not be valid as
we might have to solve hard computational problems to optimize our
choices. What happens if we restrict the computational power of economic
agents?

There has been some work in economics treating computation as a fixed
cost or simply considering the size of a program. This talk will explore
a new direction bringing the rich tools of computational complexity into
economic models, a tricky prospect where even basic concepts like "input
size" are not well defined.

We show how to incorporate computational complexity into a number of
economic models including game theory, prediction markets, forecast
testing, preference revelation and contract theory.

This talk will not assume any background in either economics or
computational complexity.

About the speaker:

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. He also holds an adjoint professorship at the Toyota
Technological Institute at Chicago.

Fortnow's research spans computational complexity and its applications,
most recently to micro-economic theory. His work on interactive proof
systems and time-space lower bounds for satisfiability led to his
election as ACM Fellow in 2007. Fortnow has served as the founding
editor-in-chief of the ACM Transactions on Computation Theory, as chair
of the steering committee for the IEEE Conference on Computational
Complexity, as chair of ACM SIGACT, and currently sits on the Computing
Research Association board of directors and the council of the Computing
Community Consortium. Fortnow originated and co-authors the
Computational Complexity weblog since 2002, the first major theoretical
computer science blog. He has thousands of followers on Twitter.

Fortnow's survey The Status of the P versus NP Problem is CACM's most
downloaded article. Fortnow has written a popular science book The
Golden Ticket: P, NP and the Search for the Impossible loosely based on
that article.

Host: Pekka Orponen

Date: Wednesday, 18 September, 2013
Time: 13:15 - 14:00
Venue: Lecture hall T2, Aalto Otaniemi Computer Science building,
Konemiehentie 2, Espoo

Welcome!

Further information: <http://ics.aalto.fi/en/current/ics_forum/>