Computer Science – Computer Science and Game Theory
Scientific paper
2008-09-28
Computer Science
Computer Science and Game Theory
19 pages, 5 figures, 2 tables, partially appeared in WINE 2008
Scientific paper
We study social cost losses in Facility Location games, where $n$ selfish agents install facilities over a network and connect to them, so as to forward their local demand (expressed by a non-negative weight per agent). Agents using the same facility share fairly its installation cost, but every agent pays individually a (weighted) connection cost to the chosen location. We study the Price of Stability (PoS) of pure Nash equilibria and the Price of Anarchy of strong equilibria (SPoA), that generalize pure equilibria by being resilient to coalitional deviations. A special case of recently studied network design games, Facility Location merits separate study as a classic model with numerous applications and individual characteristics: our analysis for unweighted agents on metric networks reveals constant upper and lower bounds for the PoS, while an $O(\ln n)$ upper bound implied by previous work is tight for non-metric networks. Strong equilibria do not always exist, even for the unweighted metric case. We show that $e$-approximate strong equilibria exist ($e=2.718...$). The SPoA is generally upper bounded by $O(\ln W)$ ($W$ is the sum of agents' weights), which becomes tight $\Theta(\ln n)$ for unweighted agents. For the unweighted metric case we prove a constant upper bound. We point out several challenging open questions that arise.
Hansen Thomas Dueholm
Telelis Orestis A.
No associations
LandOfFree
On Pure and (approximate) Strong Equilibria of Facility Location Games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Pure and (approximate) Strong Equilibria of Facility Location Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Pure and (approximate) Strong Equilibria of Facility Location Games will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-353394