UTCS Colloquium/ACT Seminar: Lance Fortnow/Northwestern University: "Bounding Rationality with Computational Complexity" TAY 3.144, Wednesday, September 16, 2009 2:30 p.m.
Type of Talk: UTCS Colloquium/ACT Seminar
er/Affiliation: Lance Fortnow/Northwestern University
me: Wednesday, September 16, 2009 2:30 p.m.
Host: Adam Klivans
Talk Title: "Boundin
g Rationality with Computational Complexity"
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
- 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
Part of this talk represents joint work with Rahul San
- Awards & Honors
- About Us
- Student Engagement and Support
- Masters Program
- Ph.D. Program
- Financial Information
- Prospective Students
- Incoming Students
- Current Students
- Portfolio Program in Robotics
- Curricular Practical Training
- Grad Student Talks
- UTCS Direct