Name
Abstract | ||
|---|---|---|
We study social cost losses in Facility Location games, where nselfish agents install facilities over a network and connect tothem, so as to forward their local demand (expressed by anon-negative weight per agent). Agents using the same facilityshare fairly its installation cost, but every agent paysindividually a (weighted) connection cost to the chosen location.We study the Price of Stability (PoS) of pure Nash equilibria andthe Price of Anarchy of strong equilibria (SPoA), that generalizepure equilibria by being resilient to coalitional deviations. Forunweighted agents on metric networks we prove upper and lowerbounds on PoS, while an O(ln n) upper bound implied by previouswork is tight for non-metric networks. We also prove a constantupper bound for the SPoA of metric networks when strong equilibriaexist. For the weighted game on general networks we prove existenceof e-approximate (e = 2.718...) strong equilibria andan upper bound of O(ln W) on SPoA (W is the sum of agents’weights), which becomes tight Θ(ln n) for unweightedagents. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-92185-1_54 | Clinical Orthopaedics and Related Research |
Keywords | DocType | Volume |
strong equilibria,strong equilibrium,installation cost,ln w,metric network,agent paysindividually,forunweighted agent,social cost loss,strong equilibriaexist,ln n,facility location games,connection cost,network design,nash equilibria,price of anarchy,facility location,price of stability,upper and lower bounds,upper bound | Conference | abs/0809.4792 |
ISSN | Citations | PageRank |
0302-9743 | 5 | 0.49 |
References | Authors | |
12 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Thomas Dueholm Hansen | 1 | 161 | 13.77 |
| Orestis A. Telelis | 2 | 47 | 4.95 |