Computing the nucleolus of some combinatorially-structured games

In this paper we introduce the ℬ-prenucleolus for a transferable utility game (N, υ), where ℬ ⊆ 2^N. The ℬ-prenucleolus is a straightforward generalization of the ordinary prenucleolus, where only the coalitions in ℬ determine the outcome. We impose a combinatorial structure on the collection ℬ which enables us to compute the ℬ-prenucleolus in 𝒪(n³|ℬ|) time. The algorithm can be used for computing the nucleolus of several classes of games, among which is the class of minimum cost spanning tree games.