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
(15)
Best Response Dynamics
Construction Cost
Convergence Time
Cost Allocation
Cost Sharing
Fair Division
Network Connectivity
Network Design
Optimal Solution
Potential Game
Price of Stability
shapley value
Strategic Behavior
Nash Equilibria
Nash Equilibrium
Related Publications
(56)
Nearoptimal network design with selfish agents
Worstcase Equilibria
On a network creation game
How bad is selfish routing?
Applications of approximation algorithms to cooperative games
Subscribe
Academic
Publications
The Price of Stability for Network Design with Fair Cost Allocation
The Price of Stability for Network Design with Fair Cost Allocation,10.1109/FOCS.2004.68,Elliot Anshelevich,Anirban Dasgupta,Jon M. Kleinberg,Éva Tard
Edit
The Price of Stability for Network Design with Fair Cost Allocation
(
Citations: 234
)
BibTex

RIS

RefWorks
Download
Elliot Anshelevich
,
Anirban Dasgupta
,
Jon M. Kleinberg
,
Éva Tardos
,
Tom Wexler
,
Tim Roughgarden
Network design
is a fundamental problem for which it is important to understand the efiects of strategic behavior. Given a collection of selfinterested agents who want to form a network connecting certain endpoints, the set of stable solutions  the
Nash equilibria
 may look quite difierent from the centrally enforced optimum. We study the quality of the best Nash equilibrium, and refer to the ratio of its cost to the optimum network cost as the price of stability. The best
Nash equilibrium
solution has a natural meaning of stability in this context  it is the
optimal solution
that can be proposed from which no user will defect. We consider the
price of stability
for
network design
with respect to one of the most widelystudied protocols for network cost allocation, in which the cost of each edge is divided equally between users whose connections make use of it; this fairdivision scheme can be derived from the Shapley value, and has a number of basic economic motivations. We show that the
price of stability
for
network design
with respect to this fair
cost allocation
is O(logk), where k is the number of users, and that a good
Nash equilibrium
can be achieved via bestresponse dynamics in which users iteratively defect from a starting solution. This establishes that the fair
cost allocation
protocol is in fact a useful mechanism for inducing
strategic behavior
to form nearoptimal equilibria. We discuss connections to the class of potential games deflned by Monderer and Shapley, and extend our results to cases in which users are seeking to balance
network design
costs with latencies in the constructed network, with stronger results when the network has only delays and no construction costs. We also present bounds on the
convergence time
of bestresponse dynamics, and discuss extensions to a weighted game.
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, pp. 295304, 2004
DOI:
10.1109/FOCS.2004.68
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.
(
theory.stanford.edu
)
(
www.cs.cornell.edu
)
(
www.denison.edu
)
(
webcourse.cs.technion.ac.il
)
(
personal.denison.edu
)
(
csdl.computer.org
)
(
www.cs.cornell.edu
)
(
www.cs.cornell.edu
)
(
www.denison.edu
)
(
ieeexplore.ieee.org
)
(
ieeexplore.ieee.org
)
(
www.cs.rpi.edu
)
(
www.cs.cornell.edu
)
(
www.informatik.unitrier.de
)
More »
Citation Context
(171)
...Congestion games (Rosenthal 1973) are a wellstudied model of strategic sharing of resource, and have been used to investigate domains ranging from network design and routing (Kunniyur and Srikant 2003;
Anshelevich et al. 2004
) to cloudcomputing and loadbalancing (Suri, T ´ oth, and Zhou 2007; V¨ 2007; Ashlagi, Tennenholtz, and Zohar 2010)...
Reshef Meir
,
et al.
Congestion Games with Agent Failures
...Recent works [
1
,2,3,4,5] have modeled how independent selfish agents can build or maintain a large network by paying for possible edges...
...The network formation problem has been addressed in several recent works, mainly in the context of noncooperative games [
1
,2,6]...
...The socalled Shapley network design game is proposed in [
1
]...
...This latter is determined in the noncooperative network formation framework proposed in [
1
], revised in Section 2, starting from the empty network and using a best response algorithm where each user greedily minimizes its path cost until an equilibrium is reached...
Konstantin Avrachenkov
,
et al.
A Nash Bargaining Solution for Cooperative Network Formation Games
...Central to this area is the notion of the price of anarchy (PoA) [20, 25] and the price of stability (PoS) [
3
]...
...For example, there are still open problems from the first paper to study the PoS [
3
] concerning some important cases of network design games (for example undirected networks [2, 18])...
George Christodoulou
,
et al.
On the Performance of Approximate Equilibria in Congestion Games
...Consequently, the collaborative solution proposed by our algorithm approximates the socially best Nash equilibrium (corresponding to the equilibrium used in the Price of Stability [
17
]), as it optimizes the global makespan with a guarantee that no player has incentive to deviate from the proposed solution...
PierreFrancois Dutot
,
et al.
Approximation Algorithms for the Multiorganization Scheduling Problem
...Opposite to this, Anshelevich et al. [
2
] define the price of stability as the ratio of the social value of the best Nash equilibrium and an optimal strategy profile, thus characterizing the minimal loss of optimality that a system has to suffer in presence of selfish users...
Vittorio Bilò
,
et al.
Performance of OneRound Walks in Linear Congestion Games
References
(51)
The price of anarchy is independent of the network topology
(
Citations: 210
)
Tim Roughgarden
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 428437, 2002
Selfish Routing in Capacitated Networks
(
Citations: 83
)
Jose R. Correa
,
Andreas S. Schulz
,
Nicolas E. Stier Moses
Journal:
Mathematics of Operations Research  MOR
, 2003
The complexity of pure Nash equilibria
(
Citations: 214
)
Alex Fabrikant
,
Christos H. Papadimitriou
,
Kunal Talwar
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 604612, 2004
Selfish traffic allocation for server farms
(
Citations: 29
)
A. Czumaj
,
P. Krysta
,
Berthold Vocking
Conference:
ACM Symposium on Theory of Computing  STOC
, 2002
Strategyproof Sharing of Submodular Costs: Budget Balance Versus E ciency
(
Citations: 19
)
H. Moulin
,
S. Shenker
Published in 1996.
Sort by:
Citations
(234)
Congestion Games with Agent Failures
Reshef Meir
,
Moshe Tennenholtz
,
Yoram Bachrach
,
Peter Key
Published in 2012.
A Nash Bargaining Solution for Cooperative Network Formation Games
(
Citations: 1
)
Konstantin Avrachenkov
,
Jocelyne Elias
,
Fabio Martignon
,
Giovanni Neglia
,
Leon A. Petrosyan
Conference:
Networking  Networking
, pp. 307318, 2011
Selfish Bin Packing
(
Citations: 1
)
Leah Epstein
,
Elena Kleiman
Journal:
Algorithmica
, vol. 60, no. 2, pp. 368394, 2011
On the Performance of Approximate Equilibria in Congestion Games
George Christodoulou
,
Elias Koutsoupias
,
Paul G. Spirakis
Journal:
Algorithmica
, vol. 61, no. 1, pp. 116140, 2011
Approximation Algorithms for the Multiorganization Scheduling Problem
PierreFrancois Dutot
,
Fanny Pascual
,
Krzysztof Rzadca
,
Denis Trystram
Journal:
IEEE Transactions on Parallel and Distributed Systems  TPDS
, vol. 22, no. 11, pp. 18881895, 2011