Directed communication in games with directed graphs

• E. C. Gavilán ^[1] ; C. Manuel ^[1] ; R. van den Brink ^[2]
  1. [1] Universidad Complutense de Madrid

     Universidad Complutense de Madrid

     Madrid, España

     
  2. [2] Vrije University Amsterdam
• Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 31, Nº. 3, 2023, págs. 584-617
• Idioma: inglés
• DOI: 10.1007/s11750-023-00654-8
• Enlaces
  • Texto completo
• Resumen

  • We introduce a novel concept of directed communication and a related connectedness in directed graphs, and apply this to model certain cooperation restrictions in cooperative games. In the literature on communication in directed networks or directed graphs, one can find different notions of connectedness, and different ways how directed communication restricts cooperation possibilities of players in a game. In this paper, we introduce a notion of connectedness in directed graphs that is based on directed paths. We assume that a coalition of players in a game can only cooperate if these players form a directed path in a directed communication graph. We define a restricted game following the same approach as Myerson for undirected communication situations, and consider the allocation rule that applies the Shapley value to this restricted game. We characterize this value by extended versions of the well-known component efficiency, fairness and balanced contributions axioms. Moreover, using the new notion of connectedness, we apply this allocation rule to define network centrality, efficiency and vulnerability measures for directed networks.

• Referencias bibliográficas
  • Aadithya KV, Ravindran B, Michalak TP, Jennings NR (2010) Efficient computation of the shapley value for centrality in networks. Internet...
  • Amer R, Giménez JM, Magaña A (2007) Accessibility in oriented networks. Eur J Oper Res 180:700–712
  • Bell MGF (2003) The use of game theory to measure the vulnerability of stochastic networks. IEEE Trans Reliab 52:63–68
  • Bonacich P (1987) Power and centrality: a family of measures. Am J Sociol 92:1170–1182
  • del Pozo M, Manuel C, González-Arangüena E, Owen G (2011) Centrality in directed social networks. A game theoretic approach. Soc Netw 33(3):191–200
  • Faigle U, Kern W (1992) The Shapley value for cooperative games under precedence constraints. Internat J Game Theory 21:249–266
  • Gallardo JM, Jiménez N, Jiménez-Losada A (2018) A Shapley distance in graphs. Inf Sci 432:269–277
  • Gilles RP, Owen G, van den Brink R (1992) Games with permission structures: the conjunctive approach. Internat J Game Theory 20:277–293
  • Gilles RP, Owen G (1994) Games with permission structures: the disjunctive approach. Department of Economics, Virginia Polytechnic Institute...
  • Gómez D, González-Arangüena E, Manuel C, Owen G, del Pozo M, Tejada J (2003) Centrality and power in social networks: a game theoretic approach....
  • Grofman B, Owen G (1982) A game theoretic approach to measuring centrality in social networks. Social Netw 4:213–224
  • Gueye A, Marbukh V, Walrand JC (2012) Towards a metric for communication network vulnerability to attacks: a game theoretic approach. In:...
  • Harary F, Sumner D (1980) The dichromatic number of an oriented tree. J Combin Inform System Sci 5(3):184–187
  • Harsanyi JC (1959) A bargaining model for cooperative n-person games. In: Tucker AW, Luce RD (eds) Contributions to the theory of games IV....
  • Khmelnitskaya A, Selcuk O, Talman D (2016) The Shapley value for directed graph games. Oper Res Lett 44:143–147
  • Latora V, Marchiori M (2001) Efficient behavior of small-world networks. Phys Rev Lett 87:198–701
  • Lee S, Kim S, Choi K, Shon T (2018) Game theory-based security vulnerability quantification for social internet of things. Fut Gen Comput...
  • Li D, Shan E (2020) The Myerson value for directed graph games. Oper Res Lett 48:142–146
  • Mazalov VV, Trukhina LI (2014) Generating functions and the Myerson vector in communication networks. Discret Math Appl 24(5):395–303
  • Mazalov VV, Avrachenkov KE, Trukhina LI, Tsynguev BT (2016) Game-theoretic centrality measures for weighted graphs. Fund Inf 145(3):341–358
  • Michalak TP, Aadithya KV, Szczepanski PL, Ravindram B, Jennings NR (2013) Efficient computation of the Shapley value for game-theoretic network...
  • Michalak TP, Rahwan T, Skibski O, Wooldridge M (2015) Defeating terrorits networks with game theory. IEEE Intell Syst 30(1):53–61
  • Myerson RB (1977) Graphs and cooperation in games. Math Oper Res 2:225–229
  • Myerson RB (1980) Conference structures and fair allocation rules. Internat J Game Theory 9:169–182
  • Navarro F (2020) The center value: a sharing rule for cooperative games on acyclic graphs. Math Soc Sci 105:1–13
  • Shapley LS (1953a) Additive and nom-additive set functions. Ph.D. Thesis, Princeton University
  • Shapley LS (1953) A value for n-person games, 307–317. In: Kuhn HW, Tucker AW (eds) Annals of mathematics studies, vol 28. Princeton University...
  • Slikker M, van den Nouweland A (2001) Social and economic networks in cooperative game theory. Kluwer Academic Publisher, Boston
  • Szczepański PL, Michalak TP, Rahwan T (2016) Efficient algorithms for game-theoretic betweenness centrality. Artif Intell 231:39–63
  • Tarkowski MK, Michalak TP, Rahwan T, Wooldridge M (2017) Game-theoretic network centrality: a review. arXiv: 1801. 00218 v1
  • Tarkowski MK, Szczepański PL, Michalak TP, Harrenstein P, Wooldridge M (2018) Efficient computation of semivalues for game-theoretic network...
  • van den Brink R, Gilles RP (1996) Axiomatizations of the conjunctive permission value for games with permission structures. Games Econ Behav...
  • R B (1997) An axiomatization of the disjunctive permission value forgames with permission structure. Internat J Game Theory 26:27–43
  • van den Brink R, Borm P (2002) Digraph competitions and cooperative games. Theor Decis 53:327–342