×

Clique games: a family of games with coincidence between the nucleolus and the Shapley value. (English) Zbl 1437.91040

Summary: 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 belongs 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 examine multiple games defined on graphs that provide a fertile ground for applications of our results.

MSC:

91A12 Cooperative games
91A43 Games involving graphs
05C57 Games on graphs (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Béal, S.; Rémila, E.; Solal, P., Axioms of invariance for TU-games, Internat. J. Game Theory, 44, 4, 891-902 (2015) · Zbl 1388.91019
[2] Bergantiños, G.; Vidal-Puga, J., A fair rule in minimum cost spanning tree problems, J. Econom. Theory, 137, 1, 326-352 (2007) · Zbl 1132.91366
[3] Bird, C., On cost allocation for a spanning tree: a game theoretic approach, Networks, 6, 335-350 (1976) · Zbl 0357.90083
[4] Bogomolnaia, A.; Moulin, H., Sharing the cost of a minimal cost spanning tree: Beyond the folk solution, Games Econom. Behav., 69, 238-248 (2010) · Zbl 1230.91019
[5] Chun, Y.; Park, N.; Yengin, D., Coincidence of cooperative game theoretic solutions in the appointment problem, Internat. J. Game Theory, 45, 3, 699-708 (2016) · Zbl 1388.91021
[6] Csóka, P.; Herings, P. J.-J., Bankruptcy games where the estate is a player, (Moretti, S., Abstracts of 13th European (Formerly Spain-Italy-Netherlands) Meeting on Game Theory. Abstracts of 13th European (Formerly Spain-Italy-Netherlands) Meeting on Game Theory, SING13 (2017), Paris-Dauphine University), 42
[7] Deng, X.; Ibaraki, T.; Nagamochi, H., Algorithmic aspects of the core of combinatorial optimization games, Math. Oper. Res., 24, 3, 751-766 (1999) · Zbl 1064.91505
[8] Deng, X.; Papadimitriou, C. H., On the complexity of cooperative solution concepts, Math. Oper. Res., 19, 2, 257-266 (1994) · Zbl 0824.90146
[9] Dong, Y.; Shan, E.; Kang, L.; Li, S., Domination in intersecting hypergraphs, Discrete Appl. Math., 251, 155-159 (2018) · Zbl 1401.05216
[10] Dutta, B.; Kar, A., Cost monotonicity, consistency and minimum cost spanning tree games, Games Econom. Behav., 48, 2, 223-248 (2004) · Zbl 1117.91308
[11] Gomez, D.; Gonzalez-Aranguena, E.; Manuel, C.; Owen, G.; del Pozo, M.; Tejada, J., Centrality and power in social networks: a game theoretic approach, Math. Social Sci., 46, 1, 27-54 (2003) · Zbl 1040.91089
[12] Gonzalez-Aranguena, E.; Manuel, C.; Owen, G.; del Pozo, M., The within groups and the between groups Myerson values, European J. Oper. Res., 257, 2, 586-600 (2017) · Zbl 1394.91059
[13] González-Díaz, J.; Sánchez-Rodríguez, E., Understanding the coincidence of allocation rules: symmetry and orthogonality in TU-games, Internat. J. Game Theory, 43, 4, 821-843 (2014) · Zbl 1308.91023
[14] Graham, D. A.; Marshall, R. C.; Richard, J.-F., Differential payments within a bidder coalition and the Shapley value, Amer. Econ. Rev., 80, 3, 493-510 (1990)
[15] Ichiishi, T., Super-modularity: Applications to convex games and to the greedy algorithm for LP, J. Econom. Theory, 25, 2, 283-286 (1981) · Zbl 0478.90092
[16] Jégou, P.; Ndiaye, S. N., On the notion of cycles in hypergraphs, Discrete Math., 309, 23, 6535-6543 (2009) · Zbl 1229.05172
[17] Kar, A.; Mitra, M.; Mutuswami, S., On the coincidence of the prenucleolus with the Shapley value, Math. Social Sci., 57, 1, 16-25 (2009) · Zbl 1155.91314
[18] Kuipers, J., On the core of information graph games, Internat. J. Game Theory, 21, 4, 339-350 (1993) · Zbl 0801.90149
[19] Littlechild, S.; Owen, G., A simple expression for the Shapley value in a special case, Manage. Sci., 20, 3, 370-372 (1973) · Zbl 0307.90095
[20] Montero, M., On the nucleolus as a power index, (Holler, M. J.; Nurmi, H., Power, Voting, and Voting Power: 30 Years After (2013), Springer: Springer Berlin, Heidelberg), 283-299 · Zbl 1419.91048
[21] Myerson, R. B., Graphs and cooperation in games, Math. Oper. Res., 2, 3, 225-229 (1977) · Zbl 0402.90106
[22] Ni, D.; Wang, Y., Sharing a polluted river, Games Econom. Behav., 60, 176-186 (2007) · Zbl 1155.91449
[23] Okamoto, Y., Fair cost allocations under conflicts - a game-theoretic point of view, Discrete Optim., 5, 1, 1-18 (2008) · Zbl 1137.91506
[24] Schmeidler, D., The nucleolus of a characteristic function game, SIAM J. Appl. Math., 17, 6, 1163-1170 (1969) · Zbl 0191.49502
[25] Shapley, L., A value for n-person games, (Kuhn, H. K.; Tucker, A., Contributions to the Theory of Games. Contributions to the Theory of Games, Annals of Mathematics Studies, vol. II (1953), Princeton University Press: Princeton University Press Princeton NJ), 307-317 · Zbl 0050.14404
[26] Shapley, L. S., Cores of convex games, Internat. J. Game Theory, 1, 1, 11-26 (1971) · Zbl 0222.90054
[27] Tijs, S. H., The First Steps with Alexia, the Average Lexicographic Value (2005), Tilburg University, CentER DP 2005-12
[28] Trudeau, C., A new stable and more responsible cost sharing solution for mcst problems, Games Econom. Behav., 75, 1, 402-412 (2012) · Zbl 1280.91099
[29] Trudeau, C.; Vidal-Puga, J., On the set of extreme core allocations for minimal cost spanning tree problems, J. Econom. Theory, 169, 425-452 (2017) · Zbl 1400.91263
[30] van den Nouweland, A.; Borm, P.; van Golstein Brouwers, W.; Bruinderink, R. G.; Tijs, S., A game theoretic approach to problems in telecommunication, Manage. Sci., 42, 2, 294-303 (1996) · Zbl 0881.90152
[31] Vidal-Puga, J., Bargaining with commitments, Internat. J. Game Theory, 33, 1, 129-144 (2004) · Zbl 1133.91394
[32] Yokote, K.; Funaki, Y.; Kamijo, Y., Coincidence of the Shapley value with other solutions satisfying covariance, Math. Social Sci., 89, 1-9 (2017) · Zbl 1415.91032
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.