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
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Validation, Synthesis and Optimization for Cyber-Physical Systems Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

Hierarchical Network Formation Games

verfasst von : Orna Kupferman, Tami Tamir

Erschienen in: Tools and Algorithms for the Construction and Analysis of Systems

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

Classical network-formation games (NFGs) are played on directed graphs, and are used in network design and analysis. Edges in the network are associated with costs and players have reachability objectives, which they try to fulfill at a minimal cost. When several players use the same edge, they share its cost. The theoretical and practical aspects of NFGs have been extensively studied and are well understood. All studies of NFGs, however, consider an explicit representation of the network. In practice, networks are often built in a hierarchical manner. Technically, some of the vertices in the network are boxes, associated with nested sub-networks, where a sub-network may be “called” by several boxes in the network. This makes hierarchical networks exponentially more succinct than traditional “flat” networks.
We introduce hierarchical network formation games (HNFGs) and study theoretical and practical aspects of the hierarchical setting. Different applications call for different cost-sharing mechanisms, which define how edge-formation costs are shared by their users. Indeed, in some applications, cost sharing should refer to the flat expansion of the network and in some it should take into account the hierarchical structure of the network. We study properties of HNFGs like stability and equilibrium inefficiency in the different mechanisms. We also study computational aspects of HNFGs, where the principal question is whether their exponential succinctness with respect to NFGs leads to an exponential increase in the complexity of reasoning about them. This question is analogous to research done in the formal-verification community about the ability to model-check hierarchical systems in their succinct presentation. We show that the picture is diverse and depends on the mechanism applied.

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 A Novel Learning Algorithm for Büchi Automata Based on Family of DFAs and Classification Trees
Nächstes Kapitel Synthesis of Recursive ADT Transformations from Reusable Templates
Fußnoten
1
Throughout this paper, we consider pure strategies, as is the case for the vast literature on cost-sharing games. Unlike mixed strategies, pure strategies may not be random, or drawn from a distribution.
 
2
We note that different types of hierarchies, mainly ones that refer to a partition of the network to levels, have already been studied. In particular, in [35, 36], it is shown how these levels induce a hierarchical game (also termed “hierarchical NFG”, but with the adjective “hierarchical” describing the game rather than the network), leading to a clever decomposition of the game. Our notion of hierarchy is different and refers to nesting of sub-networks. In particular, in earlier work there is no notion of a flat extension, which is the key issue in our games.
 
Literatur
1.
Albers, S., Elits, S., Even-Dar, E., Mansour, Y., Roditty, L.: On Nash equilibria for a network creation game. In: Proceedings of 7th SODA, pp. 89–98 (2006)
2.
Almagor, S., Avni, G., Kupferman, O.: Repairing multi-player games. In: Proceedings of 26th CONCUR, pp. 325–339 (2015)
3.
4.
Alur, R., Kannan, S., Yannakakis, M.: Communicating hierarchical state machines. In: Wiedermann, J., Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, pp. 169–178. Springer, Heidelberg (1999). doi:10.​1007/​3-540-48523-6_​14 CrossRef
5.
Alur, R., Yannakakis, M.: Model checking of hierarchical state machines. ACM TOPLAS 23(3), 273–303 (2001)CrossRef
6.
7.
Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos, E., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. SIAM J. Comput. 38(4), 1602–1623 (2008)MathSciNetCrossRefMATH
8.
Avni, G., Kupferman, O.: Synthesis from component libraries with costs. In: Baldan, P., Gorla, D. (eds.) CONCUR 2014. LNCS, vol. 8704, pp. 156–172. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-44584-6_​12
9.
10.
Avni, G., Kupferman, O., Tamir, T.: Congestion games with multisets of resources and applications in synthesis. In: Proceedings of 35th FST and TCS. LIPIcs, pp. 365–379 (2015)
11.
Brihaye, T., Bruyère, V., De Pril, J., Gimbert, H.: On subgame perfection in quantitative reachability games. LMCS 9(1), 1–32 (2012)MATH
12.
13.
Chatterjee, K., Henzinger, T.A., Jurdzinski, M.: Games with secure equilibria. Theoret. Comput. Sci. 365(1–2), 67–82 (2006)MathSciNetCrossRefMATH
14.
15.
Chatterjee, K., Majumdar, R., Jurdziński, M.: On Nash equilibria in stochastic games. In: Marcinkowski, J., Tarlecki, A. (eds.) CSL 2004. LNCS, vol. 3210, pp. 26–40. Springer, Heidelberg (2004). doi:10.​1007/​978-3-540-30124-0_​6 CrossRef
16.
17.
Clarke, E.M., Grumberg, O., Peled, D.: Model Checking. MIT Press, Cambridge (1999)
18.
Correa, J.R., Schulz, A.S., Stier-Moses, N.E.: Selfish routing in capacitated networks. Math. Oper. Res. 29, 961–976 (2004)MathSciNetCrossRefMATH
19.
20.
21.
Fabrikant, A., Luthra, A., Maneva, E., Papadimitriou, C., Shenker, S.: On a network creation game. In: ACM PODC, pp. 347–351 (2003)
22.
23.
24.
25.
26.
Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. Comput. Sci. Rev. 3(2), 65–69 (2009)CrossRefMATH
27.
Lustig, Y., Vardi, M.Y.: Synthesis from component libraries. STTT 15(5–6), 603–618 (2013)CrossRefMATH
28.
Mavronicolas, M., Milchtaich, I., Monien, B., Tiemann, K.: Congestion games with player-specific constants. In: Kučera, L., Kučera, A. (eds.) MFCS 2007. LNCS, vol. 4708, pp. 633–644. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-74456-6_​56 CrossRef
29.
30.
Mitchell, J.C.: Concepts in Programming Languages. Cambridge University Press, Cambridge (2003)MATH
31.
32.
33.
Papadimitriou, C.H.: Algorithms, games, and the internet. In: Proceedings of STOC, pp. 749–753 (2001)
34.
Pnueli, A.: In transition from global to modular temporal reasoning about programs. In: Apt, K.R. (ed.) Logics and Models of Concurrent Systems. NATO Advanced Science Institutes, vol. 13, pp. 123–144. Springer, Heidelberg (1985). doi:10.​1007/​978-3-642-82453-1_​5 CrossRef
35.
Rose, L., Belmega, E.V., Saad, W., Debbah, M.: Pricing in heterogeneous wireless networks: hierarchical games and dynamics. IEEE Trans. Wireless Commun. 13(9), 4985–5001 (2014)CrossRef
36.
Saad, W., Zhu, Q., Basar, T., Han, Z., Hjørungnes, A.: Hierarchical network formation games in the uplink of multi-hop wireless networks. In: Proceedings of GLOBECOM, pp. 1–6. IEEE (2009)
37.
Tardos, E., Wexler, T.: Network formation games and the potential function method. In: Algorithmic Game Theory. Cambridge University Press (2007)
Metadaten
Titel
Hierarchical Network Formation Games
verfasst von
Orna Kupferman
Tami Tamir
Copyright-Jahr
2017
Verlag
Springer Berlin Heidelberg
Buch
Tools and Algorithms for the Construction and Analysis of Systems

Print ISBN: 978-3-662-54576-8

Electronic ISBN: 978-3-662-54577-5

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-662-54577-5_13