Comparing Nash and Correlated Equilibrium Solutions

Adam Meyerson
University of California, Los Angeles (UCLA)

We produce upper and lower bounds on the Price of Mediation for a variety of games; this is the ratio of the social cost of the worst correlated equilibrium solution to the worst Nash equilibrium solution. A small Price of Mediation suggests that little is lost by implementing a sub-optimum "mediator" or by utilizing machine learning techniques guaranteed to converge to a correlated solution. Our results focus on small matrix games, and on congestion or load balancing games with bounded cost functions.

Back to Algorithmic Game Theory