[colloquium] special theory lunch: Christos Papadimitriou on Mon March 6

[Sanjeev Arora]

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.