Mediated Equilibria in Load-Balancing Games

Mediated Equilibria in Load-Balancing Games,10.1007/978-3-642-10841-9_60,Joshua R. Davis,David Liben-nowell,Alexa Sharp,Tom Wexler

Mediated Equilibria in Load-Balancing Games  
BibTex | RIS | RefWorks Download
Mediators are third parties to whom the players in a game can delegate the task of choosing a strategy; a mediator forms a medi- ated 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 begin the study of the power of mediation by using 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 mea- sured by weighted average latency. Even in this restricted class of games, bme can range from as good as opt to no better than the best correlated equilibrium. In unweighted games bme achieves opt; the weighted case is more subtle. Our main results are (1) that the worst-case ratio bme/opt is at least (1 + p 2)/2 1.2071 (and at most 1 + 2.618 (3)) 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 also give similarly detailed results for other natural social-cost functions.
Conference: Workshop on Internet and Network Economics - WINE , pp. 591-599, 2009
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.