Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Liquid Price of Anarchy Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

Selfish Network Creation with Non-uniform Edge Cost

verfasst von : Ankit Chauhan, Pascal Lenzner, Anna Melnichenko, Louise Molitor

Erschienen in: Algorithmic Game Theory

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Network creation games investigate complex networks from a game-theoretic point of view. Based on the original model by Fabrikant et al. [PODC’03] many variants have been introduced. However, almost all versions have the drawback that edges are treated uniformly, i.e. every edge has the same cost and that this common parameter heavily influences the outcomes and the analysis of these games.
We propose and analyze simple and natural parameter-free network creation games with non-uniform edge cost. Our models are inspired by social networks where the cost of forming a link is proportional to the popularity of the targeted node. Besides results on the complexity of computing a best response and on various properties of the sequential versions, we show that the most general version of our model has constant Price of Anarchy. To the best of our knowledge, this is the first proof of a constant Price of Anarchy for any network creation game.

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 "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

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
Vorheriges Kapitel Reconciling Selfish Routing with Social Good
Nächstes Kapitel Opinion Formation Games with Aggregation and Negative Influence
Literatur
1.
Albers, S., Eilts, S., Even-Dar, E., Mansour, Y., Roditty, L.: On Nash equilibria for a network creation game. ACM TEAC 2(1), 2 (2014)MATH
2.
Alon, N., Demaine, E.D., Hajiaghayi, M.T., Leighton, T.: Basic network creation games. SIAM J. Discret. Math. 27(2), 656–668 (2013)MathSciNetCrossRef
3.
Àlvarez, C., Blesa, M.J., Duch, A., Messegué, A., Serna, M.: Celebrity games. Theor. Comput. Sci. 648, 56–71 (2016)MathSciNetCrossRef
4.
5.
6.
Barabási, A.-L.: Network Science. Cambridge University Press, Cambridge (2016)MATH
7.
Bilò, D., Gualà, L., Leucci, S., Proietti, G.: Locality-based network creation games. In: SPAA 2014, pp. 277–286. ACM, New York (2014)
8.
Bilò, D., Gualà, L., Leucci, S., Proietti, G.: Network creation games with traceroute-based strategies. In: Halldórsson, M.M. (ed.) SIROCCO 2014. LNCS, vol. 8576, pp. 210–223. Springer, Cham (2014). doi:10.​1007/​978-3-319-09620-9_​17CrossRef
9.
Chauhan, A., Lenzner, P., Melnichenko, A., Molitor, L.: Selfish network creation with non-uniform edge cost (2017). arXiv preprint arXiv:​1706.​10200
10.
Corbo, J., Parkes, D.: The price of selfish behavior in bilateral network formation. In: PODC 2005, pp. 99–107. ACM, New York (2005)
11.
Cord-Landwehr, A., Lenzner, P.: Network creation games: think global – act local. In: Italiano, G.F., Pighizzini, G., Sannella, D.T. (eds.) MFCS 2015. LNCS, vol. 9235, pp. 248–260. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-48054-0_​21CrossRef
12.
Cord-Landwehr, A., Mäcker, A., auf der Heide, F.M.: Quality of service in network creation games. In: Liu, T.-Y., Qi, Q., Ye, Y. (eds.) WINE 2014. LNCS, vol. 8877, pp. 423–428. Springer, Cham (2014). doi:10.​1007/​978-3-319-13129-0_​34CrossRef
13.
Demaine, E.D., Hajiaghayi, M.T., Mahini, H., Zadimoghaddam, M.: The price of anarchy in network creation games. ACM Trans. Algorithms 8(2), 13 (2012)MathSciNetCrossRef
14.
Fabrikant, A., Luthra, A., Maneva, E., Papadimitriou, C.H., Shenker, S.: On a network creation game. In: PODC 2003, pp. 347–351. ACM, New York (2003)
15.
Graham, R., Hamilton, L., Levavi, A., Loh, P.-S.: Anarchy is free in network creation. ACM Trans. Algorithms (TALG) 12(2), 15 (2016)MathSciNetMATH
16.
Jackson, M.O., Wolinsky, A.: A strategic model of social and economic networks. J. Econ. Theory 71(1), 44–74 (1996)MathSciNetCrossRef
17.
Kawald, B., Lenzner, P.: On dynamics in selfish network creation. In: SPAA 2013, pp. 83–92. ACM (2013)
18.
19.
20.
Leskovec, J., Kleinberg, J., Faloutsos, C.: Graphs over time: densification laws, shrinking diameters and possible explanations. In: SIGKDD 2005, pp. 177–187. ACM (2005)
21.
Mamageishvili, A., Mihalák, M., Müller, D.: Tree Nash equilibria in the network creation game. In: Bonato, A., Mitzenmacher, M., Prałat, P. (eds.) WAW 2013. LNCS, vol. 8305, pp. 118–129. Springer, Cham (2013). doi:10.​1007/​978-3-319-03536-9_​10CrossRefMATH
22.
Meirom, E.A., Mannor, S., Orda, A.: Network formation games with heterogeneous players and the internet structure. In: EC 2014, pp. 735–752. ACM (2014)
23.
Mihalák, M., Schlegel, J.C.: The price of anarchy in network creation games is (mostly) constant. In: Kontogiannis, S., Koutsoupias, E., Spirakis, P.G. (eds.) SAGT 2010. LNCS, vol. 6386, pp. 276–287. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-16170-4_​24CrossRef
24.
Mihalák, M., Schlegel, J.C.: Asymmetric swap-equilibrium: a unifying equilibrium concept for network creation games. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 693–704. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-32589-2_​60CrossRef
25.
26.
Papadimitriou, C.H.: Algorithms, games, and the internet. In: Proceedings on 33rd Annual ACM Symposium on Theory of Computing, pp. 749–753 (2001)
Metadaten
Titel
Selfish Network Creation with Non-uniform Edge Cost
verfasst von
Ankit Chauhan
Pascal Lenzner
Anna Melnichenko
Louise Molitor
Copyright-Jahr
2017
Buch
Algorithmic Game Theory

Print ISBN: 978-3-319-66699-0

Electronic ISBN: 978-3-319-66700-3

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-66700-3_13

Premium Partner

    Bildnachweise