Trudeau, Christian and VidalPuga, Juan (2018): Clique games: a family of games with coincidence between the nucleolus and the Shapley value.

PDF
MPRA_paper_96710.pdf Download (319kB)  Preview 
Abstract
We introduce a new family of cooperative games for which there is coincidence between the nucleolus and the Shapley value. These socalled clique games are such that agents are divided into cliques, with the value created by a coalition linearly increasing with the number of agents belonging to the same clique. Agents can belong to multiple cliques, but for a pair of cliques, at most a single agent belong to their intersection. Finally, if two agents do not belong to the same clique, there is at most one way to link the two agents through a chain of agents, with any two nonadjacent agents in the chain belonging to disjoint sets of cliques. We provide multiple examples for clique games. Graphinduced games, either when the graph indicates cooperation possibilities or impossibilities, provide us with opportunities to confirm existing results or discover new ones. A particular focus are the minimum cost spanning tree problems. Our result allows us to obtain new coincidence results between the nucleolus and the Shapley value, as well as other cost sharing methods for the minimum cost spanning tree problem.
Item Type:  MPRA Paper 

Original Title:  Clique games: a family of games with coincidence between the nucleolus and the Shapley value 
Language:  English 
Keywords:  nucleolus; Shapley value; clique; minimum cost spanning tree 
Subjects:  C  Mathematical and Quantitative Methods > C7  Game Theory and Bargaining Theory > C71  Cooperative Games 
Item ID:  96710 
Depositing User:  Juan VidalPuga 
Date Deposited:  27 Oct 2019 15:43 
Last Modified:  27 Oct 2019 15:43 
References:  Béal, S., Rémila, E., and Solal, P. (2015). Axioms of invariance for TUgames. International Journal of Game Theory, 44(4):891–902. Bergantiños, G. and VidalPuga, J. (2007a). A fair rule in minimum cost spanning tree problems. Journal of Economic Theory, 137(1):326–352. Bergantiños, G. and VidalPuga, J. (2007b). The optimistic TU game in minimum cost spanning tree problems. International Journal of Game Theory, 36(2):223–239. Bird, C. (1976). On cost allocation for a spanning tree: a game theoretic approach. Networks, 6:335–350. Chun, Y., Park, N., and Yengin, D. (2016). Coincidence of cooperative game theoretic solutions in the appointment problem. International Journal of Game Theory, 45(3):699–708. Csóka, P. and Herings, P. J.J. (2017). Bankruptcy games where the estate is a player. In Moretti, S., editor, Abstracts of 13th European (formerly SpainItalyNetherlands) Meeting on Game Theory (SING13), page 42. ParisDauphine University. Deng, X., Ibaraki, T., and Nagamochi, H. (1999). Algorithmic aspects of the core of combinatorial optimization games. Mathematics of Operations Research, 24(3):751–766. Deng, X. and Papadimitriou, C. H. (1994). On the complexity of cooperative solution concepts. Mathematics of Operations Research, 19(2):257–266. Dutta, B. and Kar, A. (2004). Cost monotonicity, consistency and minimum cost spanning tree games. Games and Economic Behavior, 48(2):223–248. Gomez, D., GonzalezAranguena, E., Manuel, C., Owen, G., del Pozo, M., and Tejada, J. (2003). Centrality and power in social networks: a game theoretic approach. Mathematical Social Sciences, 46(1):27 – 54. GonzalezAranguena, E., Manuel, C., Owen, G., and del Pozo, M. (2017). The within groups and the between groups Myerson values. European Journal of Operational Research, 257(2):586 – 600. GonzálezDı́az, J. and SánchezRodrı́guez, E. (2014). Understanding the coincidence of allocation rules: symmetry and orthogonality in TUgames. International Journal of Game Theory, 43(4):821–843. Graham, D. A., Marshall, R. C., and Richard, J.F. (1990). Differential payments within a bidder coalition and the Shapley value. American Economic Review, 80(3):493–510. Ichiishi, T. (1981). Supermodularity: Applications to convex games and to the greedy algorithm for lp. Journal of Economic Theory, 25(2):283 – 286. Kar, A., Mitra, M., and Mutuswami, S. (2009). On the coincidence of the prenucleolus with the Shapley value. Mathematical Social Sciences, 57(1):16–25. Littlechild, S. and Owen, G. (1973). A simple expression for the Shapley value in a special case. Management Science, 20(3):370–372. Montero, M. (2013). On the nucleolus as a power index. In Holler, M. J. and Nurmi, H., editors, Power, Voting, and Voting Power: 30 Years After, pages 283–299. Springer, Berlin, Heidelberg. Myerson, R. B. (1977). Graphs and cooperation in games. Mathematics of Operations Research, 2(3):225–229. Ni, D. and Wang, Y. (2007). Sharing a polluted river. Games and Economic Behavior, 60:176–186. Okamoto, Y. (2008). Fair cost allocations under conflicts  a gametheoretic point of view . Discrete Optimization, 5(1):1 – 18. Schmeidler, D. (1969). The nucleolus of a characteristic function game. SIAM Journal of Applied Mathematics, 17(6):1163–1170. Shapley, L. (1953). A value for nperson games. In Kuhn, H.K.;Tucker, A., editor, Contributions to the theory of games, volume II of Annals of Mathematics Studies, pages 307–317. Princeton University Press, Princeton NJ. Shapley, L. S. (1971). Cores of convex games. International Journal of Game Theory, 1(1):11–26. Subiza, B., GiménezGómez, J.M., and Peris, J. E. (2016). Folk solution for simple minimum cost spanning tree problems. Operations Research Letters, 44(5):598 – 601. Tijs, S. H. (2005). The first steps with Alexia, the Average lexicographic value. CentER DP 200512, Tilburg University. Trudeau, C. (2012). A new stable and more responsible cost sharing solution for mcst problems. Games and Economic Behavior, 75(1):402–412. Trudeau, C. and VidalPuga, J. (2017). On the set of extreme core allocations for minimal cost spanning tree problems. Journal of Economic Theory, 169:425 – 452. van den Nouweland, A., Borm, P., van Golstein Brouwers, W., Bruinderink, R. G., and Tijs, S. (1996). A game theoretic approach to problems in telecommunication. Management Science, 42(2):294–303. VidalPuga, J. (2004). Bargaining with commitments. International Journal of Game Theory, 33(1):129–144. Yokote, K., Funaki, Y., and Kamijo, Y. (2017). Coincidence of the Shapley value with other solutions satisfying covariance. Mathematical Social Sciences, 89:1–9. 
URI:  https://mpra.ub.unimuenchen.de/id/eprint/96710 