On computing the nucleolus of a balanced connected game

The question of "fairly" allocating costs or cost-savings among the participants of a joint enterprise is frequently answered by finding the nucleolus of a related cooperative game. In connection with various routing, sequencing and scheduling situations, connected games often arise. Their common feature is that all the essential coalitions (whose breaking up into subcoalitions is disadvantageous for its members) are connected with respect to a fixed order of the players (any player between two members of a coalition is also a member of the coalition). In the literature, several special classes of connected games are discussed that are shown to be balanced. In this paper, an algorithm is presented that computes the nucleolus of a general n-person balanced connected game. The input is the array of the explicitly given values of the n(n + 1 )/ 2 connected coalitions. The algorithm generates a sequence of at most n(n - 1 )/2 payoff vectors starting from a special vertex of the nonempty core and ending in the nucleolus. By exploiting the special structure of connected games, the initial as well as the subsequent payoff vectors are obtained by evaluating some simple recursive formulas. It is shown that the algorithm requires at most θ(n4) time and θ(n2) space. A 5-person illustrative example is also given