Presentation Paper

Title: Core-related Allocations in Tree Enterprise Games

Abstract:
We consider a multi-agent decision situation where cooperation is possible but constrained by a hierarchical structure among the agents. The dependency relations are assumed to form a rooted tree graph. The root of the tree represents a “crucial” resource, while each other node represents an agent with a given profit-making potential that can only be realized if all agents along the path to the root also participate. Accessing the “crucial” resource involves a fixed cost.

We study stable allocations in such tree enterprise situations via solutions of associated cooperative games, called tree enterprise games. The value of a coalition of agents is determined by the total potential profits of its members who are connected to the root through other coalition members, subtracting the fixed cost of the “crucial” resource, which does not depend on the coalition being served. We examine the core of tree enterprise games and show that, under reasonable assumptions, it is non-empty and can be described by a polynomial-size system of linear constraints. This implies that the nucleolus of tree enterprise games can be computed in polynomial time. Furthermore, the algorithm solely requires the parameters of the tree enterprise situation; there is no need to explicitly generate all the exponentially many coalition values and use a general-purpose algorithm for nucleolus computation.

Two well-known special types of tree enterprise games are peer group games and bankruptcy games. The above-mentioned results concerning the core and nucleolus for these games are already well established. In the talk, we present some new observations regarding the less-studied Gately value for both types of games.