Abstract
The aim of this paper consists of constructing accessibility measures to the nodes of directed graphs using methods of Game Theory. Since digraphs without a predefined game are considered, the main part of the paper is devoted to establish conditions on cooperative games so that they can be used to measure accessibility. Games that satisfy desirable properties are called test games. Each ranking on the nodes is then obtained according to a pair formed by a test game and a solution defined on cooperative games whose utilities are given on ordered coalitions. The solutions proposed here are extensions of the wide family of semivalues to games in generalized characteristic function form.
This is a preview of subscription content,log in via an institution to check access.
Access this article
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
Price includes VAT (Japan)
Instant access to the full article PDF.
Similar content being viewed by others
References
Amer R, Giménez JM (2003) Modification of semivalues for games with coalition structures. Theory Decis 54: 185–205
Amer R, Giménez JM, Magaña A (2007) Accessibility in oriented networks. Eur J Oper Res 180: 700–712
Aziz H, Lachish O, Paterson M, Savani R (2009) Power indices in spanning connectivity games. In: Proceedings of algorithmic aspects in information and management, 5th international conference, AAIM 2009. Springer, Berlin, pp 55–67
Bachrach Y, Rosenschein JS (2007) Computing the Banzhaf power index in network flow games. In: Proceedings of the 8th international conference on autonomous agents and multiagent systems, AAMAS, pp 335–341
Banzhaf JF (1965) Weigthed voting doesn’t work: a mathematical analysis. Rutgers Law Rev 19: 317–343
Derks JJM, Gilles RP (1995) Hierarchical organization structures and constraints on coalition formation. Int J Game Theory 24: 147–163
Dubey P, Neyman A, Weber RJ (1981) Value theory without efficiency. Math Oper Res 6: 122–128
Gilles RP, Owen G, van den Brink R (1992) Games with permission structures: the conjunctive approach. Int J Game Theory 20: 277–293
Giménez JM (2001) Contributions to the study of solutions for cooperative games (in Spanish). Ph.D. Thesis. Technical University of Catalonia, Spain
Gómez D, et al (2001) Centrality and power in social networks. A game theoretic approach. In: Proceedings of the XXVI national congress of statistic and operations research, Úbeda, Spain
Herings PJJ, van der Laan G, Talman D (2005) The positional power of nodes in digraphs. Social Choice Welfare 24: 439–454
Kendall MG (1955) Further contributions to the theory of paired comparisons. Biometrics 11: 43–62
Laffond G, Laslier JF, Le Breton M (1993) The bipartisan set of a tournament game. Games Econ Behav 5: 182–201
Laslier JF (1997) Tournament solutions and majority voting. Springer, Berlin
Nowak A, Radzik T (1994) The Shapley value for n-person games in generalized characteristic function form. Games Econ Behav 6: 150–161
Owen G (1975) Multilinear extensions and the Banzhaf value. Naval Res Logist Q 22: 741–750
Puente MA (2000) Contributions to the representability of simple games and to the calculus of solutions for this class of games (in Spanish). Ph.D. Thesis. Technical University of Catalonia, Spain
Sanchez E, Bergantiños G (1997) On values for generalized characteristic functions. OR Spektrum 19: 229–234
Shapley LS (1953) A value for n-person games. In: Kuhn HW, Tucker AW (eds) Contributions to the theory of games II. Princeton University Press, Princeton, pp 307–317
van den Brink R, Borm P (2002) Digraph competitions and cooperative games. Theory Decis 53: 327–342
van der Laan G, van den Brink R (1998) Axiomatization of a class of share functions for n-person games. Theory Decis 44: 117–148
Wei TH (1952) The algebraic foundations of ranking theory. Cambridge University Press, Cambridge
Author information
Authors and Affiliations
Department of Applied Mathematics II, Industrial and Aeronautic Engineering School of Terrassa, Technical University of Catalonia, Catalonia, Spain
Rafael Amer & Antonio Magaña
Department of Applied Mathematics III, Engineering School of Manresa, Technical University of Catalonia, Catalonia, Spain
José Miguel Giménez
EPSEM, Avda. Bases de Manresa 61, 08242, Manresa, Spain
José Miguel Giménez
- Rafael Amer
You can also search for this author inPubMed Google Scholar
- José Miguel Giménez
You can also search for this author inPubMed Google Scholar
- Antonio Magaña
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toJosé Miguel Giménez.
Additional information
Research partially supported by Grant SGR 2009-01029 of the Catalonian Government (Generalitat de Catalunya) and Grant MTM 2009-08037 of the Science and Innovation Spanish Ministry.
Rights and permissions
About this article
Cite this article
Amer, R., Giménez, J.M. & Magaña, A. Accessibility measures to nodes of directed graphs using solutions for generalized cooperative games.Math Meth Oper Res75, 105–134 (2012). https://doi.org/10.1007/s00186-011-0378-x
Received:
Accepted:
Published:
Issue Date:
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative