Lance Fortnow
(Northwestern University)
Applying Cryptography, Complexity and Randomness to Game Theory

Traditional game theory literature assumes that individuals can completely understand 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. By using models that capture efficient computation, we can get a better understanding of game theory results.

In this talk we survey how cryptography, complexity and randomness plays into game theory results with computationally-bounded players. Cryptographic, Complexity and limited randomness assumptions can greatly expand or alter the set of equilibriums of a game, except when they don't. We explore problems including games requiring solving complicated problems, achieving correlated equilibrium without trusted parties, equilibriums by playing programs instead of strategies and reducing or eliminating the randomness in games.

This talk will not assume any background in game theory.