Abstract
On the domain of two-sided assignment markets with agents’ reservation values, the nucleolus is axiomatized as the unique solution that satisfies consistency with respect to Owen’s reduced game and symmetry of maximum complaints of the two sides. As an adjunt, we obtain a geometric characterization of the nucleolus by means of a strong form of the bisection property that characterizes the intersection between the core and the kernel of a coalitional game in (Math Opr Res 4:303–338, 1979).
Similar content being viewed by others
Notes
In fact Potters characterizes the nucleolus in a more general class of games.
If \(\gamma \) is an assignment market with \(M'=\emptyset \), then it is easy to see that the associated assignment game \(( M, w_{\gamma })\) given by (2) is the modular game generated by the vector of reservation values \(p\in \mathbb {R}^{\,M},\) that is, \(w_{\gamma }(S)=\sum _{i\in S} p_i,\) for all \(S\subseteq M.\) Similarly, if \(\gamma =(M, M', A, p, q)\) with \(M=\emptyset \), then \(w_{\gamma }(T)=\sum _{j\in T} q_j,\) for all \(T\subseteq M'.\)
Two games \((N, v)\) and \((N, w)\) are strategically equivalent if there exist \(\alpha >0\) and \(d\in \mathbb {R}^{\,N}\) such that \(w(S)=\alpha v(S)+\sum _{i\in S}d_i\). Let \(\gamma =(M, M', A, p, q)\) be an assignment market where \( A=(a_{ij})_{(i,j)\in M \times M'},\) \(p\in \mathbb {R}^M \), \( q\in \mathbb {R}^{M'},\) and let \( \tilde{\gamma }=(M, M', \tilde{A}) \) be an assignment market with null reservation values and matrix \(\tilde{A}=(\tilde{a}_{ij})_{(i,j)\in M\times M'}\) given by \(\tilde{a}_{ij}:=\max \{0, a_{ij}-p_i-q_j\}\), for all \( (i,j)\in M\times M' \). Then, as the reader can easily check, \(w_{\gamma }(S\cup T)=w_{\tilde{\gamma }}(S\cup T)+\sum _{i\in S} p_i +\sum _{j\in T}q_j,\) for all \(S\subseteq M\) and \(T\subseteq M'\).
For properties regarding coalitional games, see Peleg and Sudhölter (2007). In particular, given a coalitional game \((N,v)\), the superadditive cover \((N,\hat{v})\) is the game with the following characteristic function: for all \(S\subseteq N\),
$$\begin{aligned} \hat{v}(S)=\max _{P\in \fancyscript{P}_S}\sum _{T_i\in P}v(T_i), \end{aligned}$$where \(\fancyscript{P}_S\) is the set of partitions of \(S\).
The following property is well known (see, for instance, Potters and Tijs 1992). For any \(n\in \mathbb {N}\) we define the map \(\theta :\mathbb {R}^n \longrightarrow \mathbb {R}^{n}\) which arranges the coordinates of a point in \(\mathbb {R}^{\,n}\) in non-increasing order. Take \(x,y\in \mathbb {R}^{\,n}\) such that \(\theta (x)\) is lexicographically not greater than \(\theta (y)\). Take now any \(z\in \mathbb {R}^{\,p}\) and consider the vectors \((x,z), (y,z)\in \mathbb {R}^{n+p}\). Then, \(\theta (x,z)\) is lexicographically not greater than \(\theta (y,z)\).
The kernel is a set-solution concept for coalitional games that was introduced by Davis and Maschler (1965) . The kernel always contains the nucleolus.
References
Davis M, Maschler M (1965) The kernel of a cooperative game. Nava Res Logist Q 12:223–259
Driessen TSH (1991) A survey of consistency properties in cooperative game theory. SIAM Rev 33:43–59
Driessen TSH (1998) A note on the inclusion of the kernel in the core of the bilateral assignment game. Int J Game Theory 27:301–303
Driessen TSH (1999) Pairwise-bargained consistency and game theory: the case of a two-sided firm. Fields Inst Commun Ser 23:65–82
Hoffmann M, Sudhölter P (2007) The Shapley value of exact assignment games. Int J Game Theory 35:557–568
Llerena F, Núñez M (2011) A geometric characterization of the nucleolus of the assignment game. Econ Bull 31:3275–3285
Martínez de Albéniz FJ, Rafels C, Ybern N (2013a) On the nucleolus of \(2\times 2\) assignment games. Econ Bull 2:1641–1648
Martínez de Albéniz FJ, Rafels C, Ybern N (2013b) A procedure to compute the nucleolus of the assignment game. Oper Res Lett 41:675–678
Maschler M, Peleg B, Shapley S (1979) Geometric properties of the kernel, nucleolus and related solution concepts. Math Oper Res 4:303–338
Miquel S, Núñez M (2011) The maximum and the addition of assignment games. TOP 19:189–212
Núñez M, Rafels C (2013) Von Neumann-Morgenstern solutions to the assignment market. J Econ Theory 148:1282–1291
Owen G (1992) The assignment game: the reduced game. Ann d’Écon Stat 25/26:71–79
Peleg B (1986) On the reduced game property and its converse. Int J Game Theory 15:187–200
Peleg B, Sudhölter P (2007) Introduction to the theory of cooperative games, 2nd edn. Springer, NY
Potters J (1991) An axiomatization of the nucleolus. Int J Game Theory 19:365–373
Potters J, Tijs S (1992) The nucleolus of matrix games and other nucleoli. Math Oper Res 17:164–174
Rochford SC (1984) Symmetrically pairwise-bargained allocations in an assignment market. J Econ Theory 34:262–281
Sasaki H (1995) Consistency and monotonicity in assignment problems. Int J Game Theory 24:373–397
Shapley LS, Shubik M (1972) The assignment game I: the core. Int J Game Theory 1:111–130
Schmeidler D (1969) The nucleolus of a characteristic function game. SIAM J Appl Math 17:1163–1170
Sobolev AI (1975) The characterization of optimality principles in cooperative games by functional equations. In: Vorobiev NN (ed) Math Methods Social Sci 6. Academy of Sciences of the Lithunian SSR, Vilnius, pp 95–151 (in Russian)
Solymosi T, Raghavan TES (1994) An algorithm for finding the nucleolus of assignment games. Int J Game Theory 23:119–143
Toda M (2003) Consistency and its converse in assignment games. Int J Math, Game Theory Algebra 13:1–14
Toda M (2005) Axiomatization of the core of assignment games. Games Econ Behav 53:248–261
Thomson W (2003) Consistent allocation rules. University of Rochester, Mimeo
Thompson GL (1981) Auctions and market games. Essays in game theory and mathematical economics in honour of Oskar Morgenstern. Bibliographisches Institute AG, Zurich, pp 181–196
van den Brink R, Pintér M (2012) On axiomatizations of the Shapley value for assignment games, Tinbergen Institute Discussion Paper n. 12–092/II
Acknowledgments
The authors acknowledge the support from research grants ECO2011-22765 (Ministerio de Ciencia e Innovación and FEDER), 2009SGR900 and 2009SGR960 (Generalitat de Catalunya). We are also grateful to an Associated Editor and anonymous referees for their helpful comments.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Llerena, F., Núñez, M. & Rafels, C. An axiomatization of the nucleolus of assignment markets. Int J Game Theory 44, 1–15 (2015). https://doi.org/10.1007/s00182-014-0416-z
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00182-014-0416-z