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

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.