[Colloq] Talk, Friday, Aug. 21 - 11am

[Rachel Kalweit]

College of Computer and Information Science Colloquium presents:

Title:    On the Price of Mediation
Speaker:  Professor Adam Meyerson, UCLA
Location: WVH 366
Time:     Friday, August 21, 11 AM

Abstract:

This talk explore the relationship between the social cost of  
correlated equilibrium and Nash equilibrium. In contrast to previous  
work which models correlated equilibrium as a benevolent mediator, we  
will define and bound the Price of Mediation: the ratio of the cost of  
the worst correlated equilibrium to the cost of the worst Nash. In  
practice, the heuristics used for mediation are frequently non-
optimal, and mediators may be inept or self-interested.

The results in this talk focus on symmetric congestion games (also  
known as load balancing games). For convex cost functions, the Price  
of Mediation can grow exponentially in the number of players. We  
provide better bounds for linear, concave, and polynomially-bounded  
cost functions.

Bio:

Adam Meyerson received his PhD from Stanford University in Fall 2002.  
Following a one year postdoctoral position with the Aladdin center at  
Carnegie-Mellon, he joined the faculty of UCLA in Fall 2003. His  
research interests span approximation algorithms, online algorithms,  
and algorithmic game theory.

Host: Rajmohan Rajaraman