Population Monotonic Path Schemes for Simple Games

A path scheme for a game is composed of a path, i.e., a sequence of coalitions that is formed during the coalition formation process and a scheme, i.e., a payoff vector for each coalition in the path. A path scheme is called population monotonic if a player’s payoff does not decrease as the path coalition grows. In this study, we focus on Shapley path schemes of simple games in which for every path coalition the Shapley value of the associated subgame provides the allocation at hand. Obviously, each Shapley path scheme of a game is population monotonic if and only if the Shapley allocation scheme of the game is population monotonic in the sense of Sprumont (Games Econ Behav 2:378–394, 1990). We prove that a simple game allows for population monotonic Shapley path schemes if and only if the game is balanced. Moreover, the Shapley path scheme of a specific path is population monotonic if and only if the first winning coalition that is formed along the path contains every minimal winning coalition. We also show that each Shapley path scheme of a simple game is population monotonic if and only if the set of veto players of the game is a winning coalition. Extensions of these results to other efficient probabilistic values are discussed.