Abstract
Cooperative games are considered where only those coalitions of players are feasible that respect a given precedence structure on the set of players. Strengthening the classical symmetry axiom, we obtain three axioms that give rise to a unique Shapley value in this model. The Shapley value is seen to reflect the expected marginal contribution of a player to a feasible random coalition, which allows us to evaluate the Shapley value nondeterministically. We show that every exact algorithm for the Shapley value requires an exponential number of operations already in the classical case and that even restriction to simple games is #P-hard in general. Furthermore, we outline how the multi-choice cooperative games of Hsiao and Raghavan can be treated in our context, which leads to a Shapley value that does not depend on pre-assigned weights. Finally, the relationship between the Shapley value and the permission value of Gilles, Owen and van den Brink is discussed. Both refer to formally similar models of cooperative games but reflect complementary interpretations of the precedence constraints and thus give rise to fundamentally different solution concepts.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aigner M (1979) Combinatorial Theory. Grundlehren der Math. Wiss. 234., Springer-Verlag, Berlin-New York.
Borm B, Owen G, Tijs S (1990) Values of points and arcs in communication situations. KUN Rapportnr. 9004, Department of Mathematics, University of Nijmegen.
Brightwell G, Winkler P (1991) Counting linear extensions is #P-complete. Proc. 23rd ACM Symp. on the Theory of Computing, 175–181.
van den Brink R, Gilles RG (1991) Axiomatizations of the conjunctive permission value for games with permission structures. Res. Memorandum FEW 485, Tilburg University.
Dyer M, Frieze A (1991) Computing the volume of convex bodies: A case where randomness provably helps. Preprint, Dept. of Mathematics, Carnegie-Mellon University, Pittsburgh, U.S.A.
Faigle U (1989) Cores of games with restricted cooperation. ZOR-Methods and Models of Operations Research 33, 405–422.
Faigle U, Kern W (1990) The position value of general communication games. Proc. 15th Symp. Oper. Res. (1990), Vienna.
Gilles RP, Owen G, van den Brink R (1992) Games with permission structures: the conjunctive approach. Intern. J. Game Theory 20, 277–293.
Hsiao C-R, Raghavan TES (1990) Shapley value for multi-choice cooperative games. Preprint 1991, to appear: J. Game Theory and Economic Behaviour.
Kalai E, Samet D (1988) Weighted Shapley values. In: The Shapley Value (A. E. Roth, ed.), Cambridge University Press, 83–99.
Myerson RB (1977) Graphs and cooperation in games. Math, of Oper. Res. 2, 225–229.
Myerson RB (1980) Conference structures and fair allocation rules. Intern. J. Game Theory 9, 169–182.
von Neumann J, Morgenstern O (1944) Theory of Games and Economic Behavior. Princeton University Press, Princeton, 1944, 1947.
van den Nouweland A, Potters J, Tijs S, Zarzuelo J (1991) Cores and related solution concepts for multi-choice games. Res. Memorandum FEW 478, Tilburg University.
Owen G (1985) Game Theory. Academic Press, New York.
Owen G (1986) Values of graph-restricted games. SIAM J. Alg. Discr. Meth. 7, 210–220.
Roth AE (1988) The Shapley Value. Essays in honor of L. S. Shapley (A. E. Roth, ed.), Cambridge University Press.
Rosenthal EC (1988) Communication and its cost in graph-restricted games. Theory and Decision 25, 275–286.
Shapley LS (1953) A value for n-person games. In: Contributions to the Theory of Games, vol. II (H. W. Kuhn and A. W. Tucker, eds), Ann. Math. Studies 28, Princeton University Press, 307–317.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Faigle, U., Kern, W. The Shapley value for cooperative games under precedence constraints. Int J Game Theory 21, 249–266 (1992). https://doi.org/10.1007/BF01258278
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01258278