Clique games: a family of games with coincidence between the nucleolus and the Shapley value

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

Abstract

We introduce a new family of cooperative games for which there is coincidence between the nucleolus and the Shapley value. These so-called 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 non-adjacent agents in the chain belonging to disjoint sets of cliques. We provide multiple examples for clique games. Graph-induced 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 correspondence 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
• 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

References

Béal, S., Rémila, E., and Solal, P. (2015). Axioms of invariance for TU-games. International Journal of Game Theory, 44(4):891-902.

Bergantiños, G. and Vidal-Puga, J. (2007a). A fair rule in minimum cost spanning tree problems. Journal of Economic Theory, 137(1):326-352.

Bergantiños, G. and Vidal-Puga, 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 Spain-Italy-Netherlands) Meeting on Game Theory (SING13), page 42. Paris-Dauphine 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., Gonzalez-Aranguena, 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.

Gonzalez-Aranguena, 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ález-Dı́az, J. and Sánchez-Rodrı́guez, E. (2014). Understanding the coincidence of allocation rules: symmetry and orthogonality in TU-games. 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). Super-modularity: 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 game-theoretic 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 n-person 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énez-Gó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 2005-12, 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 Vidal-Puga, 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.

Vidal-Puga, 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.