The nucleolus of trees with revenues
type: Item
instance of: scholarly article
title: The nucleolus of trees with revenues
zbMATH Open document ID: 1107.91022
author: M. A. Meertens
author: Jos Potters
published in: Mathematical Methods of Operations Research
publication date: 2007-01-05T00:00:00Z
review text: 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 …
reviewed by: Olga Kosheleva
Mathematics Subject Classification ID: 91A12
zbMATH DE Number: 5082022
zbMATH Keywords: tree games
zbMATH Keywords: revenues
zbMATH Keywords: nucleolus
MaRDI profile type: Publication
full work available at URL: s00186-006-0088-y
OpenAlex ID: W1997881639
cites work: A characterization of the nucleolus for convex games
cites work: The kernel of a cooperative game
cites work: Applications of efficient mergeable heaps for optimization problems on trees
cites work: The kernel/nucleolus of a standard tree game
cites work: A simple expression for the nucleolus in a special case
cites work: A further note on the nucleolus of the `airport game'
cites work: Computational Complexity of the Game Theory Approach to Cost Allocation for a Tree
cites work: The Nucleolus of a Characteristic Function Game
DOI: 10.1007/S00186-006-0088-Y
description: scientific article; zbMATH DE number 5082022