Constrained core solutions for totally positive games with ordered players

In many applications of cooperative game theory to economic allocation problems, such as river-, polluted river- and sequencing games, the game is totally positive (i.e., all dividends are nonnegative), and there is some ordering on the set of the players. A totally positive game has a nonempty core. In this paper we introduce constrained core solutions for totally positive games with ordered players which assign to every such a game a subset of the core. These solutions are based on the distribution of dividends taking into account the hierarchical ordering of the players. The Harsanyi constrained core of a totally positive game with ordered players is a subset of the core of the game and contains the Shapley value. For special orderings it coincides with the core or the Shapley value. The selectope constrained core is defined for acyclic orderings and yields a subset of the Harsanyi constrained core. We provide a characterization for both solutions.

1. Besides the examples discussed in Sect. 3, other examples are, e.g. auction- (see Graham et al. 1990), dual airport- (see Littlechild and Owen 1973), telecommunication- (see van den Nouweland et al. 1996) and queueing games (see Maniquet 2003).

2. Finite totally positive games, as well as their infinite analogs, were introduced in Vasil’ev (1975).

3. In fact, \(H(v) = core(v)\) if and only if the dividends of all coalitions with at least two players are nonnegative, see Vasil’ev (1981), Derks et al. (2000) and Vasil’ev and van der Laan (2002).

4. A game \(v^*\) is the dual of a game \(v\) when \(v^*(S) = v(N) -v(N\setminus S)\) for every \(S \subseteq N.\)

5. We could easily define this solution on the class of all totally positive games with ordered players, assigning the empty set whenever the order \(D\) contains a cycle.

6. For single-valued solutions this is weaker than a similar property introduced in van den Brink and Gilles (1996) who do not require the predecessor to be necessary for the successor.

7. Here we should redefine efficiency, the null player property, additivity and nonnegativity for TU-games by adapting the corresponding axioms for games with ordered players in a straightforward way.

8. Note that this also follows immediately since a sharing system assigning zero shares to players that have predecessors in the corresponding coalition satisfies the restrictions of \(P^T_D.\)

9. A similar requirement for simple TU-games is discussed by Napel and Widgrén (2001).

10. However, a solution that satisfies structural exclusion and nonnegativity also satisfies structural monotonicity.

11. The condition that only connected coalitions have nonzero dividend also holds for restricted communication graph games, as introduced by Myerson (1977). Given a game and an undirected (communication) graph, Myerson defines the restricted game as the game which assigns to every coalition the sum of the worths of its maximally connected subsets in the graph.

12. To keep terminology consistent in this paper, we deviated from the terminology of Ni and Wang (2007) who refer to a cost allocation as a solution, and to a solution as a method.

13. Also, \(\widehat{v}\) is the dual auction game corresponding to the auction situation with \(\sum _{j=i}^n~c_j\) being the valuation of agent \(i\) for the object that is auctioned, see Graham et al. (1990).

14. These two axioms are already used by Ni and Wang (2007).

15. Note that on this subclass nonnegativity, meaning that every agent pays a nonnegative share in the cost, is not needed to get uniqueness. A proof can be obtained from the authors on request.

This research has been done while the third author was visiting the Tinbergen Institute, VU University Amsterdam, on NWO-Grant 047.017.017 within the framework of Dutch-Russian Cooperation. This author also appreciates financial support from the Russian Leading Scientific Schools Fund (Grant 4113.2008.6) and Russian Fund for Basic Research (Grant 13-06-00311). We thank two anonymous referees and the associate editor for their valuable comments.

Authors and Affiliations

1. Department of Econometrics and Tinbergen Institute, VU University, De Boelelaan 1105, 1081 HV, Amsterdam, The Netherlands

   René van den Brink & Gerard van der Laan

2. Sobolev Institute of Mathematics, Prosp. Koptyuga 4, Novosibirsk, 630090, Russia

   Valeri A. Vasil’ev

Corresponding author

Correspondence to René van den Brink.

Reprints and permissions