On the sequential price of anarchy of isolation games. (English) Zbl 1320.91030
Summary: We study the performance of subgame perfect equilibria, a solution concept which better captures the players’ rationality in sequential games with respect to the classical myopic dynamics based on the notions of improving deviations and Nash equilibria, in the context of sequential isolation games. In particular, for two important classes of sequential isolation games, we show upper and lower bounds on the sequential price of anarchy, that is the worst-case ratio between the social performance of an optimal solution and that of a subgame perfect equilibrium, 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.
MSC:
| 91A20 | Multistage and repeated games |
| 91A10 | Noncooperative games |
| 91A26 | Rationality and learning in game theory |
References:
| [1] | Adar R, Epstein L (2013) Selfish bin packing with cardinality constraints. Theor Comput Sci 495:66-80 · Zbl 1295.91005 · doi:10.1016/j.tcs.2013.05.041 |
| [2] | Aland S, Dumrauf D, Gairing M, Monien B, Schoppmann F (2011) Exact price of anarchy for polynomial congestion games. SIAM J Comput 40(5):1211-1233 · Zbl 1231.91008 · doi:10.1137/090748986 |
| [3] | Anshelevich E, Dasgupta A, Tardos É, Wexler T (2003) Near-optimal network design with selfish agents. In: Proceedings of the 35th annual ACM symposium on theory of computing (STOC). ACM Press, New York, pp 511-520 · Zbl 1192.68019 |
| [4] | Awerbuch B, Azar Y, Epstein A (2005) The price of routing unsplittable flow. In: Proceedings of the 37th annual ACM symposium on theory of computing (STOC). ACM Press, New York, pp 57-66 · Zbl 1192.90099 |
| [5] | Banik A, Bhattacharya BB, Das S (2013) Optimal strategies for the one-round discrete Voronoi game on a line. J Comb Optim 26(4):655-669 · Zbl 1302.91006 · doi:10.1007/s10878-011-9447-6 |
| [6] | Bilò V (2006) On the packing of selfish items. In: Proceedings of the 20th international parallel and distributed processing symposium (IPDPS). IEEE Computer Society, New York, p 9 · Zbl 1302.91006 |
| [7] | Bilò V, Flammini M (2011) Extending the notion of rationality of selfish agents: second order Nash equilibria. Theor Comput Sci 412(22):2296-2311 · Zbl 1211.91015 |
| [8] | Bilò V, Fanelli A, Flammini M, Moscardelli L (2010) When ignorance helps: graphical multicast cost sharing games. Theor Comput Sci 411(3):660-671 · Zbl 1185.91051 · doi:10.1016/j.tcs.2009.10.007 |
| [9] | Bilò V, Flammini M, Monaco G, Moscardelli L (2011) On the performances of Nash equilibria in isolation games. J Comb Optim 22:378-397 · Zbl 1230.91008 |
| [10] | Bilò V, Flammini M, Monaco G, Moscardelli L (2012) Some anomalies of farsighted strategic behavior. In: Proceedings of the 10th workshop on approximation and online algorithms (WAOA). LNCS 7846. Springer, Berlin, pp 229-241 · Zbl 1395.91008 |
| [11] | Bilò V, Caragiannis I, Fanelli A, Monaco G (2013a) Improved lower bounds on the price of stability of undirected network design games. Theory Comput Syst 52(4):668-686 · Zbl 1273.90168 |
| [12] | Bilò V, Flammini M, Moscardelli L (2013b) The price of stability for undirected broadcast network design with fair cost allocation is constant. In: Proceedings of the 54th symposium on foundations of computer science (FOCS). IEEE Computer Society, New York, pp 638-647 · Zbl 1452.91051 |
| [13] | Caragiannis I, Flammini M, Kaklamanis C, Kanellopoulos P, Moscardelli L (2011) Tight bounds for selfish and greedy load balancing. Algorithmica 61(3):606-637 · Zbl 1237.91049 · doi:10.1007/s00453-010-9427-8 |
| [14] | Cardinal J, Hoefer M (2010) Non-cooperative facility location and covering games. Theor Comput Sci 411(16-18):1855-1876 · Zbl 1188.91020 · doi:10.1016/j.tcs.2010.02.005 |
| [15] | Chen X, Epstein L, Kleiman E, van Stee R (2013) Maximizing the minimum load: the cost of selfishness. Theor Comput Sci 482:9-19 · Zbl 1291.90090 · doi:10.1016/j.tcs.2013.02.033 |
| [16] | Cheong O, Har-Peled S, Linial N, Matousek J (2004) The one-round Voronoi game. Discret Comput Geom 31:125-138 · Zbl 1079.91010 · doi:10.1007/s00454-003-2951-4 |
| [17] | Christodoulou G, Koutsoupias E (2005a) The price of anarchy of finite congestion games. In: Proceedings of the 37th annual ACM symposium on theory of computing (STOC). ACM Press, New York, pp 67-73 · Zbl 1192.91039 |
| [18] | Christodoulou G, Koutsoupias E (2005b) On the price of anarchy and stability of correlated equilibria of linear congestion games. In: Proceedings of the 13th annual European symposium on algorithms (ESA). LNCS 3669. Springer, New York, pp 59-70 · Zbl 1162.91305 |
| [19] | Czumaj A, Vöcking B (2007) Tight bounds for worst-case equilibria. ACM Trans Algorithms 3(1):4 · Zbl 1322.91017 · doi:10.1145/1186810.1186814 |
| [20] | Dürr C, Thang NK (2007) Nash equilibria in Voronoi games on graphs. In: Proceedings of the 15th annual European symposium on algorithms (ESA). LNCS 4698. Springer, New York, pp 17-28 · Zbl 1151.90477 |
| [21] | 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 |
| [22] | Epstein L, Kleiman E (2001) Selfish bin packing. Algorithmica 60(2):368-394 · Zbl 1213.90211 · doi:10.1007/s00453-009-9348-6 |
| [23] | Epstein L, van Stee R (2010) Maximizing the minimum load for selfish agents. Theor Comput Sci 411(1):44-57 · Zbl 1187.68091 · doi:10.1016/j.tcs.2009.08.032 |
| [24] | Epstein L, Kleiman E, Mestre J (2009) Parametric packing of selfish items and the subset sum algorithm. In: Proceedings of the 5th international workshop on internet and network economics (WINE). LNCS 5929. Springer, Berlin, pp 67-78 · Zbl 1394.68440 |
| [25] | Epstein L, Krumke SO, Levin A, Sperber H (2011) Selfish bin coloring. J Comb Optim 22(4):531-548 · Zbl 1237.91060 · doi:10.1007/s10878-010-9302-1 |
| [26] | Epstein L, Kleiman E, van Stee R (2012) The cost of selfishness for maximizing the minimum load on uniformly related machines. J Comb Optim. doi:10.1007/s10878-012-9555-y · Zbl 1291.90092 |
| [27] | Fiat A, Kaplan H, Levy M, Olonetsky S, Shabo R (2006) On the Price of stability for designing undirected networks with fair cost allocations. In: Proceedings of the 33rd international colloquium on automata, languages and programming (ICALP). LNCS 4051. Springer, New York, pp 608-618 · Zbl 1223.91014 |
| [28] | Jain AK, Murty MN, Flynn PJ (1999) Data clustering: a review. ACM Comput Surv 31(3):264-323 · doi:10.1145/331499.331504 |
| [29] | Koutsoupias E, Papadimitriou CH (1999) Worst-case equilibria. In: Proceedings of the 16th international symposium on theoretical aspects of computer science (STACS). LNCS 1653. Springer, New York, pp 404-413 · Zbl 1099.91501 |
| [30] | Lee E, Ligett K (2013) Improved bounds on the price of stability in network cost sharing games. In: Proceedings of the 14th ACM conference on electronic commerce (EC). ACM Press, New York, pp 607-620 · Zbl 1205.68044 |
| [31] | Leme RP, Syrgkanis V, Tardos É (2012a) Sequential auctions and externalities. In: Proceedings of the twenty-third annual ACM-SIAM symposium on discrete algorithms (SODA). SIAM, New Orleans, pp 869-886 · Zbl 1425.91203 |
| [32] | Leme RP, Syrgkanis V, Tardos É (2012b) The curse of simultaneity. In: Proceedings of innovations in theoretical computer science (ITCS). ACM Press, New York, pp 60-67 · Zbl 1348.91014 |
| [33] | Li J (2009) An \[O(\log n/\log \log n)O\](logn/loglogn) upper bound on the price of stability for undirected Shapley network design games. Inf Process Lett 109(15):876-878 · Zbl 1205.68044 · doi:10.1016/j.ipl.2009.04.015 |
| [34] | Mavronicolas M, Spirakis PG (2001) The price of selfish routing. In: Proceedings of the 33rd annual ACM symposium on theory of computing (STOC). ACM Press, New York, pp 510-519 · Zbl 1323.91006 |
| [35] | Mavronicolas M, Monien B, Papadopoulou VG, Schoppmann F (2008) Voronoi games on cycle graphs. In: Proceedings of the 33rd international symposium on mathematical foundations of computer science (MFCS). LNCS 5162. Springer, New York, pp 503-514 · Zbl 1173.91327 |
| [36] | Nash J (1951) Non-cooperative games. Ann Math 54(2):286-295 · Zbl 0045.08202 · doi:10.2307/1969529 |
| [37] | Osborne MJ, Rubinstein A (1994) A course in game theory. MIT Press, Cambridge · Zbl 1194.91003 |
| [38] | Roughgarden T, Tardos É (2002) How bad is selfish routing? J ACM 49(2):236-259 · Zbl 1323.90011 · doi:10.1145/506147.506153 |
| [39] | Teng SH (1999) Low energy and mutually distant sampling. J Algorithms 30(1):42-67 · Zbl 0914.68203 · doi:10.1006/jagm.1998.0963 |
| [40] | Vetta A (2002) Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions. In: Proceedings of the 43th symposium on foundations of computer science (FOCS). IEEE Computer Society, New York, pp 416 · Zbl 1188.91020 |
| [41] | Yu G, Zhang G (2008) Bin packing of selfish items. In: Proceedings of the 4th international workshop on internet and network economics (WINE). LNCS 5385. Springer, New York, pp 446-453 |
| [42] | Zhao Y, Chen W, Teng SH (2009) The isolation game: a game of distances. Theor Comput Sci 410 (47-49):4905-4919 · Zbl 1185.91060 |
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.
