{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T17:26:32Z","timestamp":1784049992140,"version":"3.55.0"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,1,12]],"date-time":"2019-01-12T00:00:00Z","timestamp":1547251200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100010663","name":"European Research Council","doi-asserted-by":"publisher","award":["Advanced Grant 291528 (RACE)"],"award-info":[{"award-number":["Advanced Grant 291528 (RACE)"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2015\/19\/D\/ST6\/03113, 2013\/09\/D\/ST6\/03920"],"award-info":[{"award-number":["2015\/19\/D\/ST6\/03113, 2013\/09\/D\/ST6\/03920"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Intell. Syst. Technol."],"published-print":{"date-parts":[[2019,3,31]]},"abstract":"<jats:p>\n            At the heart of multi-agent systems is the ability to cooperate to improve the performance of individual agents and\/or the system as a whole. While a widespread assumption in the literature is that such cooperation is essentially unrestricted, in many realistic settings this assumption does not hold. A highly influential approach for modelling such scenarios are graph-restricted games introduced by Myerson [36]. In this approach, agents are represented by nodes in a graph, edges represent communication channels, and a group can generate an arbitrary value only if there exists a direct or indirect communication channel between every pair of agents within the group. Two fundamental solution-concepts that were proposed for such games are the\n            <jats:italic>Myerson value<\/jats:italic>\n            and the\n            <jats:italic>Shapley value<\/jats:italic>\n            . While an algorithm has been developed to compute the Shapley value in arbitrary graph-restricted games, no such general-purpose algorithm has been developed for the Myerson value to date. With this in mind, we set out to develop for such games a general-purpose algorithm to compute the Myerson value, and a more efficient algorithm to compute the Shapley value. Since the computation of either value involves enumerating all connected induced subgraphs of the game\u2019s underlying graph, we start by developing an algorithm dedicated to this enumeration, and then we show empirically that it is faster than the state of the art in the literature. Finally, we present a sample application of both algorithms, in which we test the Myerson value and the Shapley value as advanced measures of node centrality in networks.\n          <\/jats:p>","DOI":"10.1145\/3235026","type":"journal-article","created":{"date-parts":[[2019,1,14]],"date-time":"2019-01-14T13:16:39Z","timestamp":1547471799000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Enumerating Connected Subgraphs and Computing the Myerson and Shapley Values in Graph-Restricted Games"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3978-416X","authenticated-orcid":false,"given":"Oskar","family":"Skibski","sequence":"first","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Talal","family":"Rahwan","sequence":"additional","affiliation":[{"name":"Khalifa University of Science and Technology, Abu Dabi, UAE"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tomasz P.","family":"Michalak","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Wooldridge","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,1,12]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"L\u00f3pez","author":"Algaba Encarnacion","year":"2007","unstructured":"Encarnacion Algaba , Jes\u00fas M. Bilbao , Julio R. Fern\u00e1ndez , Nieves Jim\u00e9nez , and Jorge J . L\u00f3pez . 2007 . Algorithms for computing the Myerson value by dividends. In Discrete Mathematics Research Progress. Nova Science Publishers , Chapter 6, 126--137. Encarnacion Algaba, Jes\u00fas M. Bilbao, Julio R. Fern\u00e1ndez, Nieves Jim\u00e9nez, and Jorge J. L\u00f3pez. 2007. Algorithms for computing the Myerson value by dividends. In Discrete Mathematics Research Progress. Nova Science Publishers, Chapter 6, 126--137."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001860400356"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2006.04.027"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)00026-N"},{"key":"e_1_2_2_5_1","volume-title":"Emergence of scaling in random networks. Science 286, 5439","author":"Barab\u00e1si Albert-L\u00e1szl\u00f3","year":"1999","unstructured":"Albert-L\u00e1szl\u00f3 Barab\u00e1si and R\u00e9ka Albert . 1999. Emergence of scaling in random networks. Science 286, 5439 ( 1999 ), 509--512. Albert-L\u00e1szl\u00f3 Barab\u00e1si and R\u00e9ka Albert. 1999. Emergence of scaling in random networks. Science 286, 5439 (1999), 509--512."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001820050062"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3040967"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018972901171"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2132771"},{"key":"e_1_2_2_10_1","volume-title":"Burleigh Bradford Gardner, and Mary R. Gardner","author":"Davis Allison","year":"2009","unstructured":"Allison Davis , Burleigh Bradford Gardner, and Mary R. Gardner . 2009 . Deep South : A Social Anthropological Study of Caste and Class. University of South Carolina Press . Allison Davis, Burleigh Bradford Gardner, and Mary R. Gardner. 2009. Deep South: A Social Anthropological Study of Caste and Class. University of South Carolina Press."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2011.04.001"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-13129-0_25"},{"key":"e_1_2_2_13_1","first-page":"1","article-title":"Some further statistical properties of the digits in Cantor\u2019s series","volume":"10","author":"Erd\u0151s Paul","year":"1959","unstructured":"Paul Erd\u0151s and Alfr\u00e9d R\u00e9nyi . 1959 . Some further statistical properties of the digits in Cantor\u2019s series . Acta Math. Hungarica 10 , 1 -- 2 (1959), 21--29. Paul Erd\u0151s and Alfr\u00e9d R\u00e9nyi. 1959. Some further statistical properties of the digits in Cantor\u2019s series. Acta Math. Hungarica 10, 1--2 (1959), 21--29.","journal-title":"Acta Math. Hungarica"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016348001805"},{"key":"e_1_2_2_15_1","volume-title":"Social Organization of an Urban Grants Economy: A Study of Business Philanthropy and Nonprofit Organizations","author":"Galaskiewicz Joseph","unstructured":"Joseph Galaskiewicz . 2016. Social Organization of an Urban Grants Economy: A Study of Business Philanthropy and Nonprofit Organizations . Elsevier . Joseph Galaskiewicz. 2016. Social Organization of an Urban Grants Economy: A Study of Business Philanthropy and Nonprofit Organizations. Elsevier."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0165-4896(03)00028-3"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001860400346"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/362248.362272"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0269888905000317"},{"key":"e_1_2_2_20_1","volume-title":"A survey of network formation models: Stability and efficiency","author":"Jackson Matthew O.","unstructured":"Matthew O. Jackson . 2005. A survey of network formation models: Stability and efficiency . In Group Formation in Economics : Networks, Clubs, and Coalitions. Cambridge University Press , Cambridge, MA, 11--49. Matthew O. Jackson. 2005. A survey of network formation models: Stability and efficiency. In Group Formation in Economics: Networks, Clubs, and Coalitions. Cambridge University Press, Cambridge, MA, 11--49."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVT.2016.2646459"},{"key":"e_1_2_2_22_1","volume-title":"Hartke","author":"Karakashian Shant","year":"2013","unstructured":"Shant Karakashian , Berthe Y. Choueiry , and Stephen G . Hartke . 2013 . An Algorithm for Generating all Connected Subgraphs with K vertices of a Graph. Technical Report. University of Nebraska-Lincoln . Shant Karakashian, Berthe Y. Choueiry, and Stephen G. Hartke. 2013. An Algorithm for Generating all Connected Subgraphs with K vertices of a Graph. Technical Report. University of Nebraska-Lincoln."},{"key":"e_1_2_2_23_1","first-page":"43","article-title":"Mapping networks of terrorist cells","volume":"24","author":"Krebs Valdis E.","year":"2002","unstructured":"Valdis E. Krebs . 2002 . Mapping networks of terrorist cells . Connections 24 (2002), 43 -- 52 . Issue 3. Valdis E. Krebs. 2002. Mapping networks of terrorist cells. Connections 24 (2002), 43--52. Issue 3.","journal-title":"Connections"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0960-0779(03)00429-6"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2007.04.058"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2013.02.032"},{"key":"e_1_2_2_27_1","volume-title":"Game Theory","author":"Maschler Michael","unstructured":"Michael Maschler , Eilon Solan , and Shmuel Zamir . 2013. Game Theory . Cambridge University Press . Michael Maschler, Eilon Solan, and Shmuel Zamir. 2013. Game Theory. Cambridge University Press."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07953-0_14"},{"key":"e_1_2_2_29_1","volume-title":"Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI\u201913)","author":"Meir Reshef","unstructured":"Reshef Meir , Yair Zick , Edith Elkind , and Jeffrey S. Rosenschein . 2013. Bounding the cost of stability in games over interaction networks . In Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI\u201913) . AAAI Press, 690--696. Reshef Meir, Yair Zick, Edith Elkind, and Jeffrey S. Rosenschein. 2013. Bounding the cost of stability in games over interaction networks. In Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI\u201913). AAAI Press, 690--696."},{"key":"e_1_2_2_30_1","first-page":"18145","article-title":"Effect of edge pruning on structural controllability and observability of complex networks. Sci","volume":"5","author":"Mengiste Simachew A.","year":"2015","unstructured":"Simachew A. Mengiste , Ad Aertsen , and Arvind Kumar . 2015 . Effect of edge pruning on structural controllability and observability of complex networks. Sci . Rep. 5 (2015), 18145 . Simachew A. Mengiste, Ad Aertsen, and Arvind Kumar. 2015. Effect of edge pruning on structural controllability and observability of complex networks. Sci. Rep. 5 (2015), 18145.","journal-title":"Rep."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/2512538.2512553"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/MIS.2015.11"},{"key":"e_1_2_2_33_1","volume-title":"Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI\u201913)","author":"Michalak Tomasz P.","unstructured":"Tomasz P. Michalak , Talal Rahwan , Piotr L. Szczepa\u0144ski , Oskar Skibski , Ramasuri Narayanam , Michael Wooldridge , and Nicholas R. Jennings . 2013. Computational analysis of connectivity games with applications to the investigation of terrorist networks . In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI\u201913) . AAAI Press, 293--301. Tomasz P. Michalak, Talal Rahwan, Piotr L. Szczepa\u0144ski, Oskar Skibski, Ramasuri Narayanam, Michael Wooldridge, and Nicholas R. Jennings. 2013. Computational analysis of connectivity games with applications to the investigation of terrorist networks. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI\u201913). AAAI Press, 293--301."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/1182635.1164207"},{"key":"e_1_2_2_35_1","first-page":"2686","article-title":"Fair topologies: Community structures and network hubs drive emergence of fairness norms. Sci","volume":"7","author":"Mosleh Mohsen","year":"2017","unstructured":"Mohsen Mosleh and Babak Heydari . 2017 . Fair topologies: Community structures and network hubs drive emergence of fairness norms. Sci . Rep. 7 , 1 (2017), 2686 . Mohsen Mosleh and Babak Heydari. 2017. Fair topologies: Community structures and network hubs drive emergence of fairness norms. Sci. Rep. 7, 1 (2017), 2686.","journal-title":"Rep."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2.3.225"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.mathsocsci.2012.05.008"},{"key":"e_1_2_2_38_1","first-page":"113","article-title":"The Zagreb indices 30 years after","volume":"76","author":"Nikoli\u0107 Sonja","year":"2003","unstructured":"Sonja Nikoli\u0107 , Goran Kova\u010devi\u0107 , Ante Mili\u010devi\u0107 , and Nenad Trinajsti\u0107 . 2003 . The Zagreb indices 30 years after . Croatia Chem. Acta 76 (2003), 113 -- 124 . Sonja Nikoli\u0107, Goran Kova\u010devi\u0107, Ante Mili\u010devi\u0107, and Nenad Trinajsti\u0107. 2003. The Zagreb indices 30 years after. Croatia Chem. Acta 76 (2003), 113--124.","journal-title":"Croatia Chem. Acta"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1994.1008"},{"key":"e_1_2_2_40_1","first-page":"1","article-title":"Social network analysis as an approach to combat terrorism: Past, present and future research","volume":"2","author":"Ressler Steve","year":"2006","unstructured":"Steve Ressler . 2006 . Social network analysis as an approach to combat terrorism: Past, present and future research . Homeland Secur. Affairs 2 (2006), 1 -- 10 . Steve Ressler. 2006. Social network analysis as an approach to combat terrorism: Past, present and future research. Homeland Secur. Affairs 2 (2006), 1--10.","journal-title":"Homeland Secur. Affairs"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2009.000000"},{"key":"e_1_2_2_42_1","volume-title":"Understanding Terror Networks","author":"Sageman Marc","unstructured":"Marc Sageman . 2004. Understanding Terror Networks . University of Pennsylvania Press. Marc Sageman. 2004. Understanding Terror Networks. University of Pennsylvania Press."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001860050058"},{"key":"e_1_2_2_44_1","volume-title":"Contributions to the Theory of Games","author":"Shapley Lloyd S.","unstructured":"Lloyd S. Shapley . 1953. A value for n-person games . In Contributions to the Theory of Games , H. W. Kuhn and A. W. Tucker (Eds.). Vol. II . Princeton University Press , 307--317. Lloyd S. Shapley. 1953. A value for n-person games. In Contributions to the Theory of Games, H. W. Kuhn and A. W. Tucker (Eds.). Vol. II. Princeton University Press, 307--317."},{"key":"e_1_2_2_45_1","first-page":"749","article-title":"Recursive contraction algorithm: A novel and efficient graph traversal method for scanning all minimal cut sets","volume":"30","author":"Sharafat A. R.","year":"2006","unstructured":"A. R. Sharafat and O. R. Marouzi . 2006 . Recursive contraction algorithm: A novel and efficient graph traversal method for scanning all minimal cut sets . Iran. J. Sci. Technol. Trans. B: Eng. 30 (2006), 749 -- 761 . A. R. Sharafat and O. R. Marouzi. 2006. Recursive contraction algorithm: A novel and efficient graph traversal method for scanning all minimal cut sets. Iran. J. Sci. Technol. Trans. B: Eng. 30 (2006), 749--761.","journal-title":"Iran. J. Sci. Technol. Trans. B: Eng."},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.11202"},{"key":"e_1_2_2_47_1","volume-title":"Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201914)","author":"Skibski Oskar","year":"2014","unstructured":"Oskar Skibski , Tomasz P. Michalak , Talal Rahwan , and Michael Wooldridge . 2014 . Algorithms for the Shapley and Myerson values in graph-restricted games . In Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201914) . IFAAMAS, 197--204. Oskar Skibski, Tomasz P. Michalak, Talal Rahwan, and Michael Wooldridge. 2014. Algorithms for the Shapley and Myerson values in graph-restricted games. In Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201914). IFAAMAS, 197--204."},{"key":"e_1_2_2_48_1","volume-title":"Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201916)","author":"Skibski Oskar","year":"2016","unstructured":"Oskar Skibski , Talal Rahwan , Tomasz P. Michalak , and Makoto Yokoo . 2016 . Attachment centrality: An axiomatic approach to connectivity in networks . In Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201916) . IFAAMAS, 168--176. Oskar Skibski, Talal Rahwan, Tomasz P. Michalak, and Makoto Yokoo. 2016. Attachment centrality: An axiomatic approach to connectivity in networks. In Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201916). IFAAMAS, 168--176."},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/MIS.2017.3"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/3171642.3171702"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2632661.2632664"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1024172719965"},{"key":"e_1_2_2_53_1","volume-title":"Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201912)","author":"Voice Thomas","unstructured":"Thomas Voice , Sarvapali D. Ramchurn , and Nicholas R. Jennings . 2012. On coalition formation with sparse synergies . In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201912) . IFAAMAS, 223--230. Thomas Voice, Sarvapali D. Ramchurn, and Nicholas R. Jennings. 2012. On coalition formation with sparse synergies. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201912). IFAAMAS, 223--230."},{"key":"e_1_2_2_54_1","volume-title":"Strogatz","author":"Watts Duncan J.","year":"1998","unstructured":"Duncan J. Watts and Steven H . Strogatz . 1998 . Collective dynamics of small-world networks. Nature 393, 6684 (1998), 440--442. Duncan J. Watts and Steven H. Strogatz. 1998. Collective dynamics of small-world networks. Nature 393, 6684 (1998), 440--442."},{"key":"e_1_2_2_55_1","volume-title":"An Introduction to Multiagent Systems","author":"Wooldridge Michael","unstructured":"Michael Wooldridge . 2009. An Introduction to Multiagent Systems . John Wiley 8 Sons. Michael Wooldridge. 2009. An Introduction to Multiagent Systems. John Wiley 8 Sons."},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1086\/jar.33.4.3629752"}],"container-title":["ACM Transactions on Intelligent Systems and Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3235026","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3235026","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:08:16Z","timestamp":1750212496000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3235026"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,12]]},"references-count":56,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,3,31]]}},"alternative-id":["10.1145\/3235026"],"URL":"https:\/\/doi.org\/10.1145\/3235026","relation":{},"ISSN":["2157-6904","2157-6912"],"issn-type":[{"value":"2157-6904","type":"print"},{"value":"2157-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,12]]},"assertion":[{"value":"2017-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}