Type of Talk:  UTCS Colloquium/ACT Seminar

Speak

er/Affiliation:  Lance Fortnow/Northwestern University

Date/Ti

me:  Wednesday, September 16, 2009  2:30 p.m.

Location:
TAY 3.144

Host: Adam Klivans

Talk Title:  "Boundin

g Rationality with Computational Complexity"

Talk Abstract:

Consider the following game:

Alice sends Bob and integer m>1

.
Bob responds with an integer r.
Bob wins the game if r is a pri

me factor of m.

In traditional game theory Bob would always win

this game since every m>1 has a prime factor. But most computer scienti

sts would choose to play Alice.

We show how to bring computatio

nal complexity into this game to prove a rough equivalence of the following
statements:
- Factoring is hard on average
- In equilibrium in t

his new model, Alice wins with high probability.

We will also d

iscuss how complexity can play into a series of other micro-economic models
as well.

Part of this talk represents joint work with Rahul San

thanam