|
Friday, October 3, 2008 |
|
|
|
|
On the Complexity of Game and Market Equilibria |
|
|
I will present some recent results in Algorithmic Game Theory and
particularly in computing and approximating game and market
equilibria. As you may have already known, the notion of the Nash
equilibrium has captured the imagination of much of the computer
science theory community, both for its many applications in the
growing domain of online interactions and for its deep and fundamental
mathematical structures. As the scale of typical internet applications
increases, the problems of efficiently analyzing their game-theoretic
properties become more pointed. I will discuss the recent results in
settling several open questions about Nash equilibria. I will focus
on the approximation and smoothed complexity of equilibrium
computation in noncooperative two-player games. I will also address
the extensions of these results to other equilibrium problems such as
in trading and market economies. |