Shapley Value for Cooperative Games under Precedence Constraints

摘要

Cooperative games where only those coalitions of players are feasible thatrespect a given precedence structure on the set of players are considered. Strengthening the classical symmetry axiom, three axioms that give rise to a unique Shapley value in this model are obtained. The Shapley value is seen to reflect the expected marginal contribution of a player to a feasible random coalition, which allows the Shapley value to be evaluated nondeterministically. Every exact algorithm for the Shapley value is shown to require an exponential number of operations already in the classical case and even restriction to simple games is shown to be hash-P-hard in general. The multi choice cooperative games of Hsiao and Raghavan can be treated in this context, which leads to a Shapley value that does not depend on preassigned weights.