The Shapley value for cooperative games under precedence constraints (Q1202565)

From MaRDI portal
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
    0 references
    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

    Identifiers