[colloquium] special theory lunch: Christos Papadimitriou on Mon March 6
arora at CS.Princeton.EDU
Mon Mar 6 12:08:43 EST 2006
Christos talking at 12:20pm.
Sanjeev Arora wrote:
> 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.
> 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.
> colloquium mailing list
> colloquium at lists.cs.princeton.edu
I am recovering from RSI and often compose email using handwriting recognition or voice recognition software. My apologies for
Computer Science Department
More information about the colloquium