Abstract
In this paper we characterize the nucleolus (which coincides with the kernel) of a tree enterprise. We also provide a new algorithm to compute it, which sheds light on its structure. We show that in particular cases, including a chain enterprise one can compute the nucleolus in O(n) operations, wheren is the number of vertices in the tree.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bird CG (1976) On cost allocation for a spanning tree: A game theoretic approach. Networks 6: 335–350
Claus A, Granot D (1976) Game theory application to cost allocation for a spanning tree. Working paper 402. Faculty of Commerce and Business Administration, University of British Columbia, Vancouver
Galil Z (1980) Applications of efficient mergeable heaps for optimization problems on trees. Acta Informatica 13: 53–58
Granot D, Granot F (1992) Computational complexity of a cost allocation approach to a fixed cost spanning forest problem. Mathematics of Operations Research 17: 765–780
Granot D, Huberman G (1981) Minimum cost spanning tree games. Mathematical Programming 21: 1–18
Granot D, Huberman G (1984) On the core and nucleolus of minimum cost spanning tree games. Mathematical Programming 29: 323–347
Granot D, Maschler M (1994) Spanning network games. Working paper, Faculty of Commerce and Business Administration, The University of British Columbia, Vancouver, BC, Canada.
Littlechild SC (1974) A simple expression for the nucleolus in a special case. International Journal of Game Theory 3: 21–29
Littlechild SC, Owen G (1977) A further note on the nucleolus of the ‘airport game’. International Journal of Game Theory 5: 91–95
Littlechild SC, Thompson GF (1977) Aircraft landing fees: A game theory approach. The Bell Journal of Economics 8: 186–204
Maschler M (1992) The bargaining set, kernel, and nucleolus. In: Aumann RJ, Hart S (eds). Handbook of Game Theory. Vol. I. Elsevier Science Publishers B.V. Amsterdam North Holland 591–667
Maschler M, Peleg B (1967) The structure of the kernel of a cooperative game. SIAM Journal of Applied Mathematics 15: 569–604
Maschler M, Peleg B, Shapley LS (1972) The kernel and the bargaining set of convex games. International Journal of Game Theory 1: 73–93
Megiddo N (1978) Computational complexity of the game theory approach to cost allocation for a tree. Mathematics of Operations Research 3: 189–196
Peleg B (1986) On the reduced game property and its converse. International Journal of Game Theory 15:187–200
Shapley LS (1971) Cores of convex games. International Journal of Game Theory 1: 11–26
Author information
Authors and Affiliations
Additional information
Partially supported by Natural Science and Engineering Council of Canada, grant A4181
Supported by National Science Foundation, grant DMS-9116416.
Partially supported by Natural Science and Engineering Council of Canada, grant A3998.
Rights and permissions
About this article
Cite this article
Granot, D., Maschler, M., Owen, G. et al. The kernel/nucleolus of a standard tree game. Int J Game Theory 25, 219–244 (1996). https://doi.org/10.1007/BF01247104
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01247104