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

[Sanjeev arora]

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.
>
> 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.
>
> _______________________________________________
> colloquium mailing list
> colloquium at lists.cs.princeton.edu
> https://lists.cs.princeton.edu/mailman/listinfo/colloquium



-- 
--------------------

I am recovering from RSI and often compose email using handwriting recognition or voice recognition software. My apologies for
minor errors.

Sanjeev Arora
Computer Science Department
Princeton University