[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Log in

An axiomatization of the nucleolus of assignment markets

  • Published:
International Journal of Game Theory Aims and scope Submit manuscript

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).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Fig. 1
Fig. 2

Similar content being viewed by others

Notes

  1. In fact Potters characterizes the nucleolus in a more general class of games.

  2. 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'.\)

  3. 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'\).

  4. For comprehensive surveys on the consistency principles, the reader is referred to Driessen (1991) and Thomson (2003) .

  5. 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\).

  6. 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)\).

  7. 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

    Article  Google Scholar 

  • Driessen TSH (1991) A survey of consistency properties in cooperative game theory. SIAM Rev 33:43–59

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Driessen TSH (1999) Pairwise-bargained consistency and game theory: the case of a two-sided firm. Fields Inst Commun Ser 23:65–82

    Google Scholar 

  • Hoffmann M, Sudhölter P (2007) The Shapley value of exact assignment games. Int J Game Theory 35:557–568

    Article  Google Scholar 

  • Llerena F, Núñez M (2011) A geometric characterization of the nucleolus of the assignment game. Econ Bull 31:3275–3285

    Google Scholar 

  • 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

    Google Scholar 

  • 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

    Article  Google Scholar 

  • Maschler M, Peleg B, Shapley S (1979) Geometric properties of the kernel, nucleolus and related solution concepts. Math Oper Res 4:303–338

    Article  Google Scholar 

  • Miquel S, Núñez M (2011) The maximum and the addition of assignment games. TOP 19:189–212

    Article  Google Scholar 

  • Núñez M, Rafels C (2013) Von Neumann-Morgenstern solutions to the assignment market. J Econ Theory 148:1282–1291

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Potters J, Tijs S (1992) The nucleolus of matrix games and other nucleoli. Math Oper Res 17:164–174

    Article  Google Scholar 

  • Rochford SC (1984) Symmetrically pairwise-bargained allocations in an assignment market. J Econ Theory 34:262–281

    Article  Google Scholar 

  • Sasaki H (1995) Consistency and monotonicity in assignment problems. Int J Game Theory 24:373–397

    Article  Google Scholar 

  • Shapley LS, Shubik M (1972) The assignment game I: the core. Int J Game Theory 1:111–130

    Article  Google Scholar 

  • Schmeidler D (1969) The nucleolus of a characteristic function game. SIAM J Appl Math 17:1163–1170

    Article  Google Scholar 

  • 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)

    Google Scholar 

  • Solymosi T, Raghavan TES (1994) An algorithm for finding the nucleolus of assignment games. Int J Game Theory 23:119–143

    Article  Google Scholar 

  • Toda M (2003) Consistency and its converse in assignment games. Int J Math, Game Theory Algebra 13:1–14

    Google Scholar 

  • Toda M (2005) Axiomatization of the core of assignment games. Games Econ Behav 53:248–261

    Article  Google Scholar 

  • Thomson W (2003) Consistent allocation rules. University of Rochester, Mimeo

    Google Scholar 

  • 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

    Google Scholar 

  • 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

Download references

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

Authors

Corresponding author

Correspondence to Marina Núñez.

Rights and permissions

Reprints 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

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00182-014-0416-z

Keywords

Navigation