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@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