The Shapley value for cooperative games under precedence constraints (Q1202565): Difference between revisions
From MaRDI portal
Latest revision as of 13:23, 17 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The Shapley value for cooperative games under precedence constraints |
scientific article |
Statements
The Shapley value for cooperative games under precedence constraints (English)
0 references
14 February 1993
0 references
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 \textit{R. P. Gilles}, \textit{G. Owen} and \textit{R. van den Brink} [Int. J. Game Theory 20, No. 3, 277-293 (1992; Zbl 0764.90106)] 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.
0 references
precedence structure
0 references
Shapley value
0 references
marginal contribution
0 references
multi-choice cooperative games
0 references
0 references