Assignment games with population monotonic allocation schemes
Tóm tắt
We characterize the assignment games which admit a population monotonic allocation scheme (PMAS) in terms of efficiently verifiable structural properties of the nonnegative matrix that induces the game. We prove that an assignment game is PMAS-admissible if and only if the positive elements of the underlying nonnegative matrix form orthogonal submatrices of three special types. In game theoretic terms it means that an assignment game is PMAS-admissible if and only if it contains either a veto player or a dominant veto mixed pair, or the game is a composition of these two types of special assignment games. We also show that in PMAS-admissible assignment games all core allocations can be extended to a PMAS, and the nucleolus coincides with the tau-value.
Tài liệu tham khảo
Abe T, Liu S (2019) Monotonic core allocation paths for assignment games. Soc Choice Welfare 53:557–573
Bahel E (2019) On the properties of the nucleolus of a veto game. Econ Theory Bull 7:221–234
Çiftçi B, Borm P, Hamers H (2010) Population monotonic path schemes in simple games. Theor Decis 69:205–218
Driessen T (1988) Cooperative games, solutions and applications. Kluwer Academic Publishers, Dordrect
El Obadi S, Miquel S (2019) Assignment games with a central player. Group Decis Negot 28:1129–1148
Grahn S, Voorneveld M (2002) Population monotonic allocation schemes in bankruptcy games. Ann Oper Res 109:317–329
Huberman G (1980) The nucleolus and the essential coalitions. In: Bensoussan A, Lions J (eds) Analysis and optimization of systems, vol 28. Lecture Notes in Control and Information Sciences. Springer, Berlin, pp 416–422
Kohlberg E (1971) On the nucleolus of a characteristic function game. SIAM J Appl Math 20:62–66
Miquel S, Núñez M (2011) The maximum and the addition of assignment games. TOP 19:189–212
Moretti S, Norde H (2021) A note on weighted multi-glove games. Soc Choice Welfare 57:721–732
Norde H, Reijnierse H (2002) A dual description of the class of games with a population monotonic allocation scheme. Games Econom Behav 41:322–343
Norde H, Moretti S, Tijs S (2004) Minimum cost spanning tree games and population monotonic allocation schemes. Eur J Oper Res 154:84–97
Núñez M, Rafels C (2002) The assignment game: the tau-value. Int J Game Theory 31:411–422
Schmeidler D (1969) The nucleolus of a characteristic function game. SIAM J Appl Math 17:1163–1170
Shapley L, Shubik M (1972) The assignment game I: the core. Int J Game Theory 1:111–130
Solymosi T, Raghavan T (1994) An algorithm for finding the nucleolus of assignment games. Int J Game Theory 23:119–143
Solymosi T, Raghavan T (2001) Assignment games with stable core. Int J Game Theory 30:177–185
Sprumont Y (1990) Population monotonic allocation schemes for cooperative games with transferable utility. Games Econom Behav 2(4):378–394
Thompson GL (1981) Auctions and market games. In: Institut Bibliographisches (ed) Essays in game theory and mathematical economics in honor of Oskar Morgenstern. Wissenschaftsverlag, Mannheim, pp 181–196
Tijs S (1981) Bounds for the core and the tau-value. In: Moeschlin O, D Pallaschke D (eds) Game Theory and Mathematical Economics. North Holland Publishing Company pp 123–132
Wang L, Xiao H, Du D et al (2022) On the population monotonicity of independent set games. Oper Res Lett 50:470–474
Xiao H, Fang Q (2022) Population monotonicity in matching games. J Comb Optim 43(4):699–709
Xiao H, Fang Q, Du DZ (2020) Population monotonic allocation schemes for vertex cover games. Theoret Comput Sci 842:41–49