Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(7)
Correlated Equilibrium
Cost Function
Load Balance
Price of Stability
Social Welfare
Lower Bound
Weighted Averaging
Subscribe
Academic
Publications
Mediated Equilibria in LoadBalancing Games
Mediated Equilibria in LoadBalancing Games,10.1007/9783642108419_60,Joshua R. Davis,David Libennowell,Alexa Sharp,Tom Wexler
Edit
Mediated Equilibria in LoadBalancing Games
BibTex

RIS

RefWorks
Download
Joshua R. Davis
,
David Libennowell
,
Alexa Sharp
,
Tom Wexler
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 loadbalancing 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 worstcase ratio bme/opt is at least (1 + p 2)/2 1.2071 (and at most 1 + 2.618 (3)) for linearlatency weighted loadbalancing games, and that the
lower bound
is tight when there are two players; and (2) tight bounds on the worst case bme/opt for generallatency weighted loadbalancing games. We also give similarly detailed results for other natural socialcost functions.
Conference:
Workshop on Internet and Network Economics  WINE
, pp. 591599, 2009
DOI:
10.1007/9783642108419_60
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.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.cs.carleton.edu
)
(
dx.doi.org
)
(
www.informatik.unitrier.de
)
More »
References
(34)
Mediators in position auctions
(
Citations: 13
)
Itai Ashlagi
,
Dov Monderer
,
Moshe Tennenholtz
Conference:
ACM Conference on Electronic Commerce  EC
, pp. 279287, 2007
Correlated Equilibrium as an expression of Bayesian Rationality
(
Citations: 455
)
Robert J. Aumann
Published in 1987.
The Price of Routing Unsplittable Flow
(
Citations: 74
)
Baruch Awerbuch
,
Yossi Azar
,
Amir Epstein
The price of anarchy of finite congestion games
(
Citations: 153
)
George Christodoulou
,
Elias Koutsoupias
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 6773, 2005
Tight bounds for worstcase equilibria
(
Citations: 189
)
Artur Czumaj
,
Berthold Viicking
Conference:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 413420, 2002