Computing the nucleolus of cyclic permutation games

The question of allocating costs or benefits among the participants of a joint enterprise is frequently answered by determining the nucleolus of a related cooperative game. We discuss this issue in connection with multi-person decision situations in which finding the best course of joint action for a group of participants can be modeled by the well-known assignment optimization problem. The related transferable utility cooperative games are called permutation games. We consider the large subclass of so-called cyclic permutation games, and show how the nucleolus of an n-player cyclic permutation game can be computed by a known O(n⁴) algorithm directly from the underlying data. We also demonstrate that this approach might not work if for the group of all participants the optimal course of action is not given by a permutation consisting of a single cycle.