depth first search

I went to a very interesting talk by Lance Fortnow on applying ideas from computational complexity to game-theory situations. The key problem from the game theory side is articulating a model of bounded rationality. Fortnow’s insight is that “efficiently computable” is the appropriate model for bounded rationality.

One idea that I hadn’t seen before is the notion of Program Equilibrium. The most common type of equilibrium in game theory is Nash equilibrium, where everything else being fixed, any change to a player’s strategy decreases that player’s reward. In program equilibrium, a player is able to spend time reasoning about the other player’s strategy (in the form of a program that the other player runs to play the game), but the time spent doing so discounts any reward received at the end of the game.

•