Seminar on March 26th, 2016

Topic: "The Shapley value for directed graph games"
Place and time of the event: 3 Kantemirovskaya st.,  room 255, 15:20

The Shapley value for directed graph games

Anna Khmelnitskaya (SPb State University), Ozer Selcuk (University of Portsmouth, UK), Dolf Talman (Tilburg University, The Netherlands)

In classical cooperative game theory it is assumed that any coalition of players may form and is able to obtain payoffs for its members. Problem is how much payoff each player should receive. However, in many practical situations the set of feasible coalitions is limited by some social, economical, hierarchical, or technical structure. One of the most famous singleton solutions for cooperative games with transferable utility (TU games), where payoffs can be distributed freely among the players, is the Shapley value (Shapley, 1953) defined as the average of the marginal contribution vectors corresponding to all permutations on the players. Several adaptations of the Shapley value for models of games with limited cooperation among the players are well known in the literature, cf. Aumann and Drèze (1974) and Owen (1977) for games with coalition structure, Myerson (1977) for games with cooperation structure introduced by means of undirected graphs in which only the connected players are able to cooperate. For games with limited cooperation that is described in terms of (cycle-free) directed graphs (digraphs) we mention Gilles and Owen (1991) for games with permission structure using the disjunctive approach and Gilles at al. (1992) for such games using the conjunctive approach, and Faigle and Kern (1992)} for games with precedence constraints.

In this paper we assume that restricted cooperation is determined by an arbitrary digraph on the player set, the directed links of which prescribe the subordination among the players. For example, consider a society consisting of individuals with different opinions, possibly incomplete preferences, about the importance of several proposals or tasks that need to be completed. If the preferences of the individuals are aggregated by using majority voting, then it is well known that the resulting structure will be a directed graph on the set of alternatives. In this directed graph, a directed link from one proposal to another proposal means that the majority of the society thinks that the former one is more important than the latter one. If it is assumed that at each moment only one proposal or task can be performed, then when one is completed, the next one to be performed can be any of its immediate successors in the digraph or one of those the performance of which does not depend on it. In this example the digraph might not be cycle-free because directed cycles may stand for the well known Condorcet paradox.

On the class of digraph games, which are games with restricted cooperation determined by a digraph prescribing the dominance relation on the set of players, we introduce the so-called Shapley value for digraph games as the average of marginal contribution vectors corresponding to all permutations not violating the subordination of players. Contrary to the Myerson model, the feasible coalitions are not necessarily connected. We show that the Shapley value for digraph games meets efficiency, linearity, the restricted null player property, the restricted equal treatment property, is independent of inessential links, and is stable with respect to the appropriate core concept under a convexity type condition which is weaker than the usual convexity guaranteeing the core stability of the classical Shapley value. On the subclass of cycle digraph games for which the digraphs are directed cycles an axiomatization is provided.

Since precedence constraints are determined by a partial ordering on the player set which can be represented by a cycle-free digraph, the games under precedence constraints form a subclass of cycle-free digraph games on which the Shapley value for digraph games coincides with the Shapley value for games under precedence constraints of Faigle and Kern (1992). There is no straightforward relation of permission values for games with permission structure with the newly introduced Shapley value for digraph games. In games with permission structure players need permission from their predecessors in order to cooperate, at least one of them for disjunctive approach and all of them for conjunctive approach. In both cases a permission-restricted TU game is derived from the given TU game taking into account the permission structure and the disjunctive and conjunctive permission values for games with permission structure are defined as the Shapley value of the corresponding permission-restricted games.