On computing the nucleolus of a balanced connected game

Tamás Solymosi, Harry Aarts, Theo Driessen

    Research output: Book/ReportReportProfessional


    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.
    Original languageEnglish
    Place of PublicationEnschede
    PublisherUniversity of Twente, Faculty of Mathematical Sciences
    Number of pages35
    Publication statusPublished - 1995

    Publication series

    PublisherUniversity of Twente, Faculty of Mathematical Sciences


    Dive into the research topics of 'On computing the nucleolus of a balanced connected game'. Together they form a unique fingerprint.

    Cite this