Abstract
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.
Article PDF
Similar content being viewed by others
References
Banzhaf J.F. (1965). Weighted voting does not work: A mathematical analysis. Rutgers Law Review 19: 317–343
Baron D.P. and Ferejohn J.A. (1989). Bargaining in legislatures. American Political Science Review 83: 1181–1206
Cruijssen, F., Borm, P., Fleuren, H., & Hamers, H. (2005). Insinking: A methodology to exploit synergy in transportation. CentER Discussion Paper 2005-121, Tilburg University, The Netherlands.
Derks J.J.M. and Haller H.H. (1999). Null player out? Linear values for games with variable supports. International Game Theory Review 1: 301–314
Laver K. and Schofield N.J. (1990). Multiparty governments: The politics of coalitions in Europe. Oxford University Press, Oxford
Monderer D. and Samet D. (2002). Variations of the Shapley value. In: Aumann, R. and Hart, S. (eds) Handbook of game theory with economic applications vol. III, pp 2055–2076. Elsevier, Amsterdam
Norde H. and Reijnierse H. (2002). A dual description of the class of games with a population monotonic allocation scheme. Games and Economic Behavior 41: 322–343
Riker W. (1962). The theory of political coalitions. Yale University Press, New Haven
Shapley, L. S. (1953). A value for n-person games. In H.W. Kuhn & A.W. Tucker (Eds.), Contributions to the theory of games II. Annals of mathematics studies (vol. 28, pp. 307–317). Princeton, NJ: Princeton University Press.
Shapley L.S. and Shubik M. (1954). A method for evaluating the distribution of power in a committee system. American Political Science Review 48: 787–792
Shenoy P.P. (1979). On coalition formation: A game-theoretical approach. International Journal of Game Theory 8: 133–164
Slikker M., Norde H. and Tijs S. (2003). Information sharing games. International Game Theory Review 5: 1–12
Sprumont Y. (1990). Population monotonic allocation schemes for cooperative games with transferable utility. Games and Economic Behavior 2: 378–394
Straffin, P. D. (1994). Power and stability in politics. In R. Aumann & S. Hart (Eds.), Handbook of game theory with economic applications (vol. II, pp. 1127–1151). Amsterdam: Elsevier.
Weber R.J. (1988). Probabilistic values for games. In: Roth A. (eds). The Shapley value: Essays in honor of Lloyd S. Shapley. Cambridge, Cambridge University Press, pp 101–120
Winter, E. (2002). The Shapley value. In R. Aumann & S. Hart (Eds.), Handbook of game theory with economic applications (vol. III, pp. 2025–2054). Amsterdam: Elsevier.
Acknowledgment
The authors would like to thank an anonymous referee for helpful comments on the paper.
Open Access
This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution,and reproduction in any medium, provided the original author(s) and source are credited.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Çiftçi, B., Borm, P. & Hamers, H. Population monotonic path schemes for simple games. Theory Decis 69, 205–218 (2010). https://doi.org/10.1007/s11238-008-9125-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11238-008-9125-z
Keywords
- Cooperative games
- Simple games
- Population monotonic path schemes
- Population monotonic allocation schemes
- Coalition formation
- Probabilistic values