On the performances of Nash equilibria in isolation games. (English) Zbl 1230.91008
Summary: We study the performances of Nash equilibria in isolation games, a class of competitive location games recently introduced in Y. Zhao, W. Chen and S. H. W [“The isolation game: a game of distances”, in: Proc. of the 19th International Symposium on Algorithms and Computation (ISAAC), 148–159 (2008)]. For all the cases in which the existence of Nash equilibria has been shown, we give tight or asymptotically tight bounds on the prices of anarchy and stability under the two classical social functions mostly investigated in the scientific literature, namely, the minimum utility per player and the sum of the players’ utilities. Moreover, we prove that the convergence to Nash equilibria is not guaranteed in some of the not yet analyzed cases.
MSC:
| 91A10 | Noncooperative games |
References:
| [1] | Ahn HK, Cheng SW, Cheong O, Golin MJ, Oostrum R (2004) Competitive facility location: the Voronoi game. Theor Comput Sci 310(1–3):457–467 · Zbl 1098.91003 · doi:10.1016/j.tcs.2003.09.004 |
| [2] | Anshelevich E, Dasgupta A, Tardos E, Wexler T (2003) Near-optimal network design with selfish agents. In: Proc of the 35th annual ACM symposium on theory of computing (STOC). ACM, New York, pp 511–520 · Zbl 1192.68019 |
| [3] | Cheong O, Har-Peled S, Linial N, Matousek J (2004) The one-round Voronoi game. Discrete Comput Geom 31:125–138 · Zbl 1079.91010 · doi:10.1007/s00454-003-2951-4 |
| [4] | Dürr C, Thang NK (2007) Nash equilibria in Voronoi games on graphs. In: Proc of the 15th annual European symposium on algorithms (ESA). LNCS, vol 4698. Springer, Berlin, pp 17–28 · Zbl 1151.90477 |
| [5] | Eaton BC, Lipsey RG (1975) The principle of minimum differentiation reconsidered: Some new developments in the theory of spatial competition. Rev Econ Stud 42(129):27–49 · Zbl 0294.90003 · doi:10.2307/2296817 |
| [6] | Eiselt HA, Laporte G, Thisse JF (1993) Competitive location models: A framework and bibliography. Transp Sci 27(1):44–54 · Zbl 0767.90006 · doi:10.1287/trsc.27.1.44 |
| [7] | Fekete SP, Meijer H (2005) The one-round Voronoi game replayed. Comput Geom Theory Appl 30:81–94 · Zbl 1068.65035 · doi:10.1016/j.comgeo.2004.05.005 |
| [8] | Hotelling H (1929) Stability in competition. Comput Geom Theory Appl 39(153):41–57 |
| [9] | Jain AK, Murty MN, Flynn PJ (1999) Data clustering: a review. ACM Comput Surv 31(3) |
| [10] | Koutsoupias E, Papadimitriou CH (1999) Worst-case equilibria. In: Proc of the 16th international symposium on theoretical aspects of computer science (STACS). LNCS, vol 1653. Springer, Berlin, pp 404–413 · Zbl 1099.91501 |
| [11] | Mavronicolas M, Monien B, Papadopoulou VG, Schoppmann F (2008) Voronoi games on cycle graphs. In: Proc. of the 33rd international symposium on mathematical foundations of computer science (MFCS). LNCS, vol 5162. Springer, Berlin, pp 503–514 · Zbl 1173.91327 |
| [12] | Nash J (1950) Equilibrium points in n-person games. In: Proc of the national academy of sciences, vol 36, pp 48–49 · Zbl 0036.01104 |
| [13] | Teng SH (1999) Low energy and mutually distant sampling. J Algorithms 30(1):42–67 · Zbl 0914.68203 |
| [14] | Zhao Y, Chen W, Teng SH (2008) The isolation game: A game of distances. In: Proc of the 19th international symposium on algorithms and computation (ISAAC). LNCS, vol 5369. Springer, Berlin, pp 148–159 · Zbl 1185.91059 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
