Abstract:

Recently, there has been tremendous interest in the study of Algorithmic Game Theory, a rapidly growing and interdisciplinary area that lies at the intersection of Computer Science, Mathematical Economics, Game Theory, and Operations Research, mainly due to the presence of selfish agents in highly decentralized systems, the Internet in particular. The computation of Nash equilibria in normal form games and the computation of Market equilibria in exchange markets have received great attention.

Both problems have a long intellectual history. In 1950, Nash showed that every game has an equilibrium. Before his work, the result was known only for two-player zero-sum games due to von Neumann and his minimax theorem. In 1954, Arrow and Debreu showed that, under very mild conditions, every market has an equilibrium. Other than the fact that both existence proofs heavily rely on fixed point theorems, the two models look very different from each other.

In this talk, we will review some of the recent results that characterize how difficult it is to compute or to approximate Nash equilibria in two-player games. We will then show how these results also advanced our understanding about market equilibria.

No prior knowledge of Game Theory will be assumed for this talk.