Christos Papadimitriou will speak at a special theory lunch on Monday
March 6 in the small auditorium in the CS building. I am sending this
announcement to the colloquium mailing list too since the talk should be
of wider interest.
Lunch will be served shortly before noon and the talk begins at 12:20.
We have to be out of the room by 1:25, and food is not allowed in the
auditorium so please come early.
I apologize for conflicts with other ongoing activities; this time
meshed best with the speaker's schedule.
His abstract appears below.
Sanjeev
---------------
Title: COMPUTING EQUILIBRIA
Christos H. Papadimitriou
UC, Berkeley
In 1951 Nash showed that every game has a mixed
equilibrium; whether such an equilibrium can be found
efficiently has been open since that time. Two decades later
Aumann proposed a relaxation called correlated equilibrium,
which can be found efficiently by linear programming. These
two problems become more interesting and meaningful in the
case of succinctly representable multiplayer games. For
correlated equilibria, a novel use of the ellipsoid algorithm
yields a polynomial-time algorithm in this case; for Nash
equilibria a sequence of reductions (discovered in
collaboration with Costas Daskalakis and Paul Goldberg) sheds
light to the complexity of finding Nash equilibria.
