The nucleolus of trees with revenues (Q857952)

In many real-life situations, spatial locations have a natural tree structure: as a root of this tree, we have a central location (e.g., a capital), second-order centers (e.g., capitals of smaller administrative units), etc., all the way to the individual nodes (e.g., homes). In such situations, if we want to have all (or at least many) nodes connected to the root, it is reasonable to connect them in the same hierarchical way: a second-order center is connected to the capital, etc. This may be reasonable when we design a transportation network, or when we design a cable connection. In the ideal world, we should connect everyone. In such situations, the only problem is to how to fairly divide the connection costs between the participants. Such games have been analyzed under the name of standard tree networks. In some practical cases, however, connecting remote nodes is prohibitively expensive and unprofitable. In such cases, it is desirable to connect only those nodes which are profitable to connect, and divide the resulting profits between all the participants. Specifically, for each set \(C\) of connected nodes, we know the resulting benefit \(b(C)\), and for each node, we know the cost of connecting it to the parent node. Thus, for each set of connected nodes, we can determine the profit \(p(C)\) as the difference between the benefit and the connection costs. We select a set of nodes for which this profit is the largest possible. The problem is how to divide the resulting profit \(v(N)\) between the participants, i.e., how to select an appropriate imputation \(x_i\) for which \(\sum_{i\in N} x_i=v(N)\). This problem can be naturally formulated as a cooperative game: if a coalition \(S\subseteq N\) acts on its own, it will gain \(v(S)=\max_{C\subseteq S} p(C)\). In turns out that in such ``trees with revenues'' games, there is always a non-empty core -- i.e., the set of imputations for which \(\sum_{i\in S} x_i\geq v(S)\) for each \(S\). For such games, one of the natural choices of \(x_i\) is the nucleolus, the (unique) imputation that lexicographically minimizes the vector of (non-strictly) decreasingly ordered differences \(v(S)-\sum_{i\in S} x_i\). A motivation is, e.g., that we should not allow any coalition to gain too much more than its minimal gain \(v(S)\) -- because this excess can only happen at the expense of other coalitions getting too close to their minimal gain \(v(S)\). In the paper under review, the authors provide an algorithm for computing such a nucleolus. This algorithm is based on a known algorithm for computing the nucleolus of a standard tree.