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

Abstract

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.

• The article: PDF (391,210 bytes)
• Source materials: ZIP (430,188 byes)
• Self citation in BIBTeX (314 bytes)

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

© 2011 Joshua R. Davis, David Liben-Nowell, Alexa Sharp, and Tom Wexler
Licensed under a Creative Commons Attribution License

Volume 2011, Article 4

Article 6

Volume 2011

Published articles