nach oben

Journal of Combinatorial Optimization

Erschienen in:

01.01.2015

On the sequential price of anarchy of isolation games

verfasst von: Anna Angelucci, Vittorio Bilò, Michele Flammini, Luca Moscardelli

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 1/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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.

Vorheriger Artikel Improved approximation algorithms for computing disjoint paths subject to two constraints

Nächster Artikel New bounds for the balloon popping problem

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Adar R, Epstein L (2013) Selfish bin packing with cardinality constraints. Theor Comput Sci 495:66–80CrossRefMATHMathSciNet

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–1233CrossRefMATHMathSciNet

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

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

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–669CrossRefMATHMathSciNet

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

Bilò V, Flammini M (2011) Extending the notion of rationality of selfish agents: second order Nash equilibria. Theor Comput Sci 412(22):2296–2311

Bilò V, Fanelli A, Flammini M, Moscardelli L (2010) When ignorance helps: graphical multicast cost sharing games. Theor Comput Sci 411(3):660–671CrossRefMATH

Bilò V, Flammini M, Monaco G, Moscardelli L (2011) On the performances of Nash equilibria in isolation games. J Comb Optim 22:378–397

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

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

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

Caragiannis I, Flammini M, Kaklamanis C, Kanellopoulos P, Moscardelli L (2011) Tight bounds for selfish and greedy load balancing. Algorithmica 61(3):606–637CrossRefMATHMathSciNet

Cardinal J, Hoefer M (2010) Non-cooperative facility location and covering games. Theor Comput Sci 411(16–18):1855–1876CrossRefMATHMathSciNet

Chen X, Epstein L, Kleiman E, van Stee R (2013) Maximizing the minimum load: the cost of selfishness. Theor Comput Sci 482:9–19CrossRefMATH

Cheong O, Har-Peled S, Linial N, Matousek J (2004) The one-round Voronoi game. Discret Comput Geom 31:125–138CrossRefMATHMathSciNet

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

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

Czumaj A, Vöcking B (2007) Tight bounds for worst-case equilibria. ACM Trans Algorithms 3(1):4CrossRefMathSciNet

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

Eiselt HA, Laporte G, Thisse JF (1993) Competitive location models: a framework and bibliography. Transp Sci 27(1):44–54CrossRefMATH

Epstein L, Kleiman E (2001) Selfish bin packing. Algorithmica 60(2):368–394CrossRefMathSciNet

Epstein L, van Stee R (2010) Maximizing the minimum load for selfish agents. Theor Comput Sci 411(1):44–57CrossRefMATH

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

Epstein L, Krumke SO, Levin A, Sperber H (2011) Selfish bin coloring. J Comb Optim 22(4):531–548CrossRefMATHMathSciNet

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

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

Jain AK, Murty MN, Flynn PJ (1999) Data clustering: a review. ACM Comput Surv 31(3):264–323CrossRef

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

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

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

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

Li J (2009) An \(O(\log n/\log \log n)\) upper bound on the price of stability for undirected Shapley network design games. Inf Process Lett 109(15):876–878CrossRefMATH

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

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

Nash J (1951) Non-cooperative games. Ann Math 54(2):286–295CrossRefMATHMathSciNet

Osborne MJ, Rubinstein A (1994) A course in game theory. MIT Press, CambridgeMATH

Roughgarden T, Tardos É (2002) How bad is selfish routing? J ACM 49(2):236–259CrossRefMathSciNet

Teng SH (1999) Low energy and mutually distant sampling. J Algorithms 30(1):42–67CrossRef

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

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

Zhao Y, Chen W, Teng SH (2009) The isolation game: a game of distances. Theor Comput Sci 410 (47–49):4905–4919

Titel: On the sequential price of anarchy of isolation games
verfasst von: Anna Angelucci
Vittorio Bilò
Michele Flammini
Luca Moscardelli
Publikationsdatum: 01.01.2015
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 1/2015
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-013-9694-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2015

Complexity analysis and algorithms for the Program Download Problem

Packing cubes into a cube is NP-complete in the strong sense

An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs

Online unbounded batch scheduling on parallel machines with delivery times

Parametric power supply networks

Improved local search for universal facility location