CAGT Seminar: Orestis Telelis
2008.10.27 |
| Date | Tue Nov 04 |
| Time | 14:15 — 15:15 |
| Location | DI-Turing-014 |
Title: On Pure and (approximate) Strong Equilibria of Facility Location Games
Speaker: Orestis Telelis
Time: Tue Nov 4th 2008, 14:15-15:00
Location: Turing-014
Abstract:
We study social cost losses in Facility Location games, where n selfish agents install facilities over anetwork and connect to them, so as to forward their localdemand (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. For unweighted agents on metric networks we prove upper and lower bounds on P oS, while an O(ln n) upper bound implied by previous work is tight for non- metric networks. We also prove a constant upper bound for the SPoA of metric networks when strong equilibria exist. For the weighted game on general networks we prove existence of e-approximate (e = 2.718...) strong equilibria and an upper bound of O(ln W) on SPoA (W is the sum of agents weights), which becomes tight (ln n) for unweighted agents.
Joint work with Thomas DueholmHansen.