Directed communication in games with directed graphs

  1. E. C. Gavilán 2
  2. C. Manuel 2
  3. R. van den Brink 1
  1. 1 VU University Amsterdam
    info

    VU University Amsterdam

    Ámsterdam, Holanda

    ROR https://ror.org/008xxew50

  2. 2 Universidad Complutense de Madrid
    info

    Universidad Complutense de Madrid

    Madrid, España

    ROR 02p0gd045

Revista:
Top

ISSN: 1863-8279,  1134-5764

Año de publicación: 2023

Volumen: 31

Número: 3

Páginas: 584-617

Tipo: Artículo

DOI: 10.1007/S11750-023-00654-8 DIALNET GOOGLE SCHOLAR lock_openAcceso abierto editor

Otras publicaciones en: Top

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.

€ Ver financiación

Información de financiación

Financiadores

Referencias bibliográficas

  • Aadithya KV, Ravindran B, Michalak TP, Jennings NR (2010) Efficient computation of the shapley value for centrality in networks. Internet and Network Economics. Springer, 1–13
  • 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 and State University, Blacksburg, Virginia. Mimeo
  • 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. Math Soc Sci 46:27–54
  • 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: Krishnamurthy V, Zhao Q, Huang M, Wen Y (eds) Game Theory for Networks. GameNets 2012. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, vol 105. Springer, Berlin, Heidelberg
  • 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. Priceton University Press, Princeton, NJ, pp 325–355
  • 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 Syst 82:752–760
  • 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 centrality. J Artif Intell Res 46:607–650
  • 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 Press, Princeton, NJ, pp 307–317
  • 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 centrality. J Artif Intell Res 63:145–189
  • van den Brink R, Gilles RP (1996) Axiomatizations of the conjunctive permission value for games with permission structures. Games Econ Behav 12:112–126
  • 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
Fuente de los datos: Dialnet