Efficiently computing the Shapley value of connectivity games in low-treewidth graphs
Author
Abstract
Suggested Citation
DOI: 10.1007/s12351-023-00742-4
Download full text from publisher
As the access to this document is restricted, you may want to search for a different version of it.
References listed on IDEAS
- Rafael Amer & José Miguel Giménez, 2004. "A connectivity game for graphs," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 60(3), pages 453-470, December.
- Lindelauf, R.H.A. & Hamers, H.J.M. & Husslage, B.G.M., 2013. "Cooperative game theoretic centrality analysis of terrorist networks: The cases of Jemaah Islamiyah and Al Qaeda," European Journal of Operational Research, Elsevier, vol. 229(1), pages 230-238.
- Stefano Moretti & Fioravante Patrone, 2008. "Rejoinder on: Transversality of the Shapley value," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 16(1), pages 60-61, July.
- Stefano Moretti & Fioravante Patrone, 2008. "Transversality of the Shapley value," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 16(1), pages 1-41, July.
- S. C. Littlechild & G. Owen, 1973. "A Simple Expression for the Shapley Value in a Special Case," Management Science, INFORMS, vol. 20(3), pages 370-372, November.
- Faigle, U & Kern, W, 1992. "The Shapley Value for Cooperative Games under Precedence Constraints," International Journal of Game Theory, Springer;Game Theory Society, vol. 21(3), pages 249-266.
- Stefano Moretti & Fioravante Patrone & Stefano Bonassi, 2007. "The class of microarray games and the relevance index for genes," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 15(2), pages 256-280, December.
- Hisao Tamaki, 2019. "Positive-instance driven dynamic programming for treewidth," Journal of Combinatorial Optimization, Springer, vol. 37(4), pages 1283-1311, May.
Most related items
These are the items that most often cite the same works as this one and are cited by the same works as this one.- Hamers, Herbert & Husslage, Bart & Lindelauf, R. & Campen, Tjeerd, 2016. "A New Approximation Method for the Shapley Value Applied to the WTC 9/11 Terrorist Attack," Other publications TiSEM 8a67b416-1091-4efe-a1a6-7, Tilburg University, School of Economics and Management.
- Hamers, Herbert & Husslage, Bart & Lindelauf, R. & Campen, Tjeerd, 2016. "A New Approximation Method for the Shapley Value Applied to the WTC 9/11 Terrorist Attack," Discussion Paper 2016-042, Tilburg University, Center for Economic Research.
- Giulia Cesari & Roberto Lucchetti & Stefano Moretti, 2017. "Generalized additive games," International Journal of Game Theory, Springer;Game Theory Society, vol. 46(4), pages 919-939, November.
- Stefano Moretti & Henk Norde, 2022. "Some new results on generalized additive games," International Journal of Game Theory, Springer;Game Theory Society, vol. 51(1), pages 87-118, March.
- Béal, Sylvain & Ferrières, Sylvain & Rémila, Eric & Solal, Philippe, 2018.
"The proportional Shapley value and applications,"
Games and Economic Behavior, Elsevier, vol. 108(C), pages 93-112.
- Sylvain Béal & Sylvain Ferrières & Eric Rémila & Phillippe Solal, 2016. "The proportional Shapley value and an application," Working Papers 2016-08, CRESE.
- Philippe Solal & Sylvain Béal & Sylvain Ferrières & Éric Rémila, 2017. "The proportional Shapley value and applications," Post-Print halshs-01644830, HAL.
- Sylvain Béal & Éric Rémila & Philippe Solal & Sylvain Ferrières, 2018. "The proportional Shapley value and applications," Post-Print halshs-01612092, HAL.
- Sylvain Béal & Eric Rémila & Philippe Solal & Sylvain Ferrières, 2016. "The proportional Shapley value and an application," Working Papers hal-01362228, HAL.
- van den Brink, René & González-Arangüena, Enrique & Manuel, Conrado & del Pozo, Mónica, 2014.
"Order monotonic solutions for generalized characteristic functions,"
European Journal of Operational Research, Elsevier, vol. 238(3), pages 786-796.
- René van den Brink & Enrique González-Aranguena & Conrado Manuel & Mónica del Pozo, 2013. "Order Monotonic Solutions for Generalized Characteristic Functions," Tinbergen Institute Discussion Papers 13-093/II, Tinbergen Institute.
- Giulia Bernardi & Roberto Lucchetti, 2015. "Generating Semivalues via Unanimity Games," Journal of Optimization Theory and Applications, Springer, vol. 166(3), pages 1051-1062, September.
- Béal, Sylvain & Moyouwou, Issofa & Rémila, Eric & Solal, Philippe, 2020.
"Cooperative games on intersection closed systems and the Shapley value,"
Mathematical Social Sciences, Elsevier, vol. 104(C), pages 15-22.
- Sylvain Béal & Issofa Moyouwou & Eric Rémila & Phillippe Solal, 2018. "Cooperative games on intersection closed systems and the Shapley value," Working Papers 2018-06, CRESE.
- Sylvain Béal & Issofa Moyouwou & Eric Rémila & Philippe Solal, 2020. "Cooperative games on intersection closed systems and the Shapley value," Post-Print halshs-02510071, HAL.
- Encarnacion Algaba & Rene van den Brink, 2021. "Networks, Communication and Hierarchy: Applications to Cooperative Games," Tinbergen Institute Discussion Papers 21-019/IV, Tinbergen Institute.
- García-Martínez, Jose A. & Mayor-Serra, Antonio J. & Meca, Ana, 2023. "Efficient effort equilibrium in cooperation with pairwise cost reduction," Omega, Elsevier, vol. 121(C).
- Arroyo, Federico, 2024. "Cost Allocation in Vehicle Routing Problems with Time Windows," Junior Management Science (JUMS), Junior Management Science e. V., vol. 9(1), pages 1241-1268.
- Algaba, Encarnación & Béal, Sylvain & Fragnelli, Vito & Llorca, Natividad & Sánchez-Soriano, Joaquin, 2019.
"Relationship between labeled network games and other cooperative games arising from attributes situations,"
Economics Letters, Elsevier, vol. 185(C).
- Encarnación Algaba & Vito Fragnelli & Natividad Llorca & Joaquin Sánchez-Soriano & Sylvain Béal, 2019. "Relationship between labeled network games and other cooperative games arising from attributes situations," Post-Print hal-04417764, HAL.
- A. Saavedra-Nieves, 2023. "On stratified sampling for estimating coalitional values," Annals of Operations Research, Springer, vol. 320(1), pages 325-353, January.
- René Brink & P. Herings & Gerard Laan & A. Talman, 2015.
"The Average Tree permission value for games with a permission tree,"
Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 58(1), pages 99-123, January.
- Rene van den Brink & Jean-Jacques Herings & Gerard van der Laan & Dolf Talman, 2012. "The Average Tree Permission Value for Games with a Permission Tree," Tinbergen Institute Discussion Papers 13-023/II, Tinbergen Institute.
- van den Brink, R. & van der Laan, G. & Herings, P.J.J. & Talman, A.J.J., 2015. "The Average Tree permission value for games with a permission tree," Other publications TiSEM 97042492-4b03-4e72-b88d-d, Tilburg University, School of Economics and Management.
- van den Brink, R. & Herings, P.J.J. & van der Laan, G. & Talman, A.J.J., 2013. "The Average Tree Permission Value for Games with a Permission Tree," Discussion Paper 2013-001, Tilburg University, Center for Economic Research.
- van den Brink, J.R. & Herings, P.J.J. & van der Laan, G. & Talman, A.J.J., 2013. "The average tree permission value for games with a permission tree," Research Memorandum 001, Maastricht University, Graduate School of Business and Economics (GSBE).
- van den Brink, R. & Herings, P.J.J. & van der Laan, G. & Talman, A.J.J., 2013. "The Average Tree Permission Value for Games with a Permission Tree," Other publications TiSEM 7f82484a-b6d8-4d2e-90cb-8, Tilburg University, School of Economics and Management.
- José M. Jiménez Gómez & María del Carmen Marco Gil & Pedro Gadea Blanco, 2010.
"Some game-theoretic grounds for meeting people half-way,"
Working Papers. Serie AD
2010-04, Instituto Valenciano de Investigaciones Económicas, S.A. (Ivie).
- Gadea-Blanco, Pedro & Giménez-Gómez, José Manuel & Marco-Gil, María del Carmen, 2013. "Some game-theoretic grounds for meeting people half-way," Working Papers 2072/220217, Universitat Rovira i Virgili, Department of Economics.
- Hougaard, Jens Leth & Moreno-Ternero, Juan D. & Tvede, Mich & Østerdal, Lars Peter, 2017.
"Sharing the proceeds from a hierarchical venture,"
Games and Economic Behavior, Elsevier, vol. 102(C), pages 98-110.
- Hougaard, Jens Leth & Moreno-Ternero, Juan D. & Tvede, Mich & Østerdal, Lars Peter, 2015. "Sharing the proceeds from a hierarchical venture," Discussion Papers on Economics 2/2015, University of Southern Denmark, Department of Economics.
- Hougaard, J. & Moreno-Ternero, J. & Tvede, M. & Osterdal, L., 2015. "Sharing the proceeds from a hierarchical venture," LIDAM Discussion Papers CORE 2015031, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
- Jens L. Hougaard & Juan D. Moreno-Ternero & Mich Tvede & Lars P. Osterdal, 2016. "Sharing the proceeds from a hierarchical venture," Working Papers 16.14, Universidad Pablo de Olavide, Department of Economics.
- Jens Leth HOUGAARD & Juan D. MORENO-TERNERO & Mich TVEDE & Lars Peter OSTERDAL, 2017. "Sharing the proceeds from a hierarchical venture," LIDAM Reprints CORE 2828, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
- Kouladoum, Jean-Claude, 2019. "Décision du mariage des ménages tchadiens et Caractéristiques socio-économiques [Marriage decision of Chadian households and socio-economic characteristics]," MPRA Paper 91590, University Library of Munich, Germany.
- René van den Brink, 2017. "Games with a Permission Structure: a survey on generalizations and applications," Tinbergen Institute Discussion Papers 17-016/II, Tinbergen Institute.
- Perea, Federico & Puerto, Justo & Fernández, Francisco R., 2012. "Avoiding unfairness of Owen allocations in linear production processes," European Journal of Operational Research, Elsevier, vol. 220(1), pages 125-131.
- José M. Alonso-Meijide & Julián Costa & Ignacio García-Jurado, 2019. "Null, Nullifying, and Necessary Agents: Parallel Characterizations of the Banzhaf and Shapley Values," Journal of Optimization Theory and Applications, Springer, vol. 180(3), pages 1027-1035, March.
More about this item
Keywords
Centrality; Social network analysis; Treewidth; Graph theory; Game theory;All these keywords.
Statistics
Access and download statisticsCorrections
All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:operea:v:23:y:2023:i:1:d:10.1007_s12351-023-00742-4. See general information about how to correct material in RePEc.
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .
Please note that corrections may take a couple of weeks to filter through the various RePEc services.