Factoring game and algorithmic game theory

(A vignette inspired by Ehud Kalai's talk at the Lens 2011 Conference.)

Consider the following sequential-move game:

1. Player 1 chooses an integer $n > 1$.
2. Player 2 chooses an integer $k > 1$.
3. Player 2 wins if $k$ is a prime factor of $n$; Player 1 wins if $k$ is not a prime factor of $n$.

The backward induction solution to this game is obvious: Player 2 picks $k$ such that it is a prime factor of $n$, and Player 1 picks any $n$, which is irrelevant because Player 2 always wins.

This game, created by Ben-Sasson, Kalai, and Kalai, called the Factoring Game, illustrates a problem with the concept of equilibrium: it assumes that Player 2 can solve a complex problem (integer factorization) in useful time.*

So that "because Player 2 always wins" boldface part above should really be preceded by "assuming that Player 2 has a quantum computer to run Shor's algorithm." In other words, in actual useful time the more likely event is that Player 1 wins (by picking a number that is the product of two very large primes, for example).

The Factoring Game exposes a problem with game-theoretic solutions to some strategic problems: they don't take into account computability or complexity. That is a problem for many real-world situations, like paid search and auction mechanism design.

There's a new-ish field at the intersection of economic game theory and computer science, algorithmic game theory. This field explicit models computation as part of the process of solving games. Something that we should keep our eyes open for, as it already has real world applications in search, mechanism design, and online auctions.

Game theory is really expanding its purview: modal logic, computational (simulated, numerical), algorithmic (computation-theoretic), and behavioral versions... good times.

Reference: E. Ben-Sasson, A. Kalai, and E. Kalai. "An approach  to bounded rationality." In Advances in Neural Information Processing, Volume 19, pages 145–152. MIT Press,  Cambridge, MA, 2006.

* This game actually only illustrates the problem of subgame-perfect Nash equilibrium, not all equilibria concepts. Hey, I had to take a ton of game theory, might as well use some of it to be pedantic here.