[Colloq] REMINDER: Today's colloquium with Xi Chen

[Diane Keys]

College of Computer and Information Science Colloquium

Presents:
Xi Chen
Tsinghua University

Who will speak on:
On the Computation and Approximation of Two-Player Nash Equilibria

Wednesday, December 13, 2006
12:00pm
110 West Village H
Northeastern University

Abstract:
In 1950, Nash showed that every non-cooperative game has an equilibrium.
Before his work, the result was known only for two-player zero-sum
games. While von Neumann's minimax theorem was the mathematical
foundation of the two-player zero-sum game, Brouwer's and Katutani's
fixed point theorems were crucially used in Nash's proofs. His approach
was later used by Arrow and Debreu in their development of the general
equilibrium theory.

Fourteen years after Nash's work, Lemke and Howson designed a
simplex-like path-following algorithm for finding a Nash equilibrium in
a general two-player game. Despite its several appealing properties,
this algorithm was recently shown to have exponential worst-case
complexity. In contrast, in his groundbreaking work, Khachiyan showed
that the ellipsoid algorithm can solve any linear program and hence any
two-player zero-sum game in polynomial time. His success, however, has
not been extended to general two-player games --- no polynomial-time
algorithm has yet been found for this remarkable problem.

In this talk, Xi will present the recent results in characterizing the
complexity of computing and approximating two-player Nash equilibria.

Biography
Xi Chen is a fourth-year PhD student in the department of Computer
Science at Tsinghua University. Xi Chen studied in the Physics
department of Tsinghua University and received B.S. there in 2003.

Xi's research interests lie in the area of Theoretical Computer Science.
Xi is particularly interested in the computational complexity of natural
problems in Algorithmic Game Theory and Computational Biology.



_______________________________________________
Colloq mailing list
Colloq at lists.ccs.neu.edu
https://lists.ccs.neu.edu/bin/listinfo/colloq