Chicago Journal of Theoretical Computer Science

Volume 2011

Article 5

Published by the Department of Computer Science, The University of Chicago.

Mediated Equilibria in Load-Balancing Games

Joshua R. Davis
University of Wisconsin, Madison

David Liben-Nowell
Deaprtment of Computer Science
Carleton College
One North College Street
Northfield, MN 55057

Alexa Sharp
Computer Science Department
Oberlin College
10 N Professor St.
Oberlin, OH 44074
Tom Wexler
Computer Science Department
Oberlin College
10 N Professor St.
Oberlin, OH 44074

November 6, 2011

Mediators are third parties to whom the players in a game can delegate the task of choosing a strategy; a mediator forms a mediated equilibrium if delegating is a best response for all players. Mediated equilibria have more power to achieve outcomes with high social welfare than Nash or correlated equilibria, but less power than a fully centralized authority. Here we initiate the study of the power of mediation by introducing the mediation analogue of the price of stability—the ratio of the social cost of the best mediated equilibrium BME to that of the socially optimal outcome OPT. We focus on load-balancing games with social cost measured by weighted average latency. Even in this restricted class of games, BME can range from being as good as OPT to being no better than the best correlated equilibrium. In unweighted games BME achieves OPT; the weighted case is more subtle. Our main results are (1) a proof that the worst-case ratio BME=OPT is at least (1+sqrt(2))/2 ~= 1.2071 and at most 2 for linear-latency weighted load-balancing games, and that the lower bound is tight when there are two players; and (2) tight bounds on the worst-case BME=OPT for general-latency weighted load-balancing games. We give similarly detailed results for other natural social-cost functions. We also show a precise correspondence between the quality of mediated equilibria in a game G and the quality of Nash equilibria in the repeated game when G is played as the stage game. The proof of this correspondence is based on a close connection between mediated equilibria and the Folk Theorem from the economics literature.

Submitted May 9, 2011, revised version submitted August 15 2011, and in final form November 6, 2011, published November 14, 2011.

DOI: 10.4086/cjtcs.2011.005

[] Volume 2011, Article 4 [] Article 6
[back] Volume 2011 [back] Published articles
[CJCTS home]