Abstract
We show that the family of assignment matrices which give rise to the same nucleolus forms a compact join-semilattice with one maximal element. The above family is, in general, not a convex set, but path-connected.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Given a coalition \(S \subseteq N,\) and an allocation \(x \in \mathbb {R}^N\), the excess of a coalition is defined as \(e\left( S , x\right) := v\left( S \right) -\sum _{i\in S}x_{i}. \) Notice that they can be considered as complaints.
In a valuation matrix, any \(2 \times 2\) submatrix has two optimal matchings. A formal definition is found after the proof of Theorem 1.
The lexicographic order\(\ge _{lex}\) on \(\mathbb {R}^d \) is defined in the following way: \( x \ge _{lex} y,\) where \(x, y \in \mathbb {R}^d, \) if \(x=y\) or if there exists \(1 \le t \le d\), such that \(x_k = y_k\) for all \(1\le k < t\) and \(x_t > y_t.\)
A family \(\mathcal {F} \subseteq \mathrm {M}^{+}_{m \times m'}\) is a join-semilattice if \(A \vee B \in \mathcal {F} \) for all \(A, B \in \mathcal {F}.\)
Following Topkis (1998), a function is a valuation if it is submodular and supermodular.
\(A \in \mathrm {M}^{+}_{m \times m'}\) is a fully optimal matrix if all matchings are optimal, i.e., \(\mathcal {M}_{A}^{*}\left( M,M^{\prime }\right) = \mathcal {M}\left( M,M^{\prime }\right) \).
A path in \(\mathcal {X} \subseteq M_{m\times m^{\prime }}^{+}\) from A to \(B, \ A,B \in \mathcal {X} ,\) is a continuous function f from the unit interval \(I=[0,1]\) to \(\mathcal {X} ,\) i.e., \( f: [0,1] \rightarrow \mathcal {X} ,\) with \(f(0)=A\) and \(f(1) =B.\) Moreover, a subset \(\mathcal {X} \subseteq M_{m\times m^{\prime }}^{+}\) is path-connected if, for any two elements \(A,B \in \mathcal {X} \), there exists a path from A to B entirely contained in \(\mathcal {X} .\)
If \(B,C \in \mathrm {M}^{+}_{m \times m'}\), \( B < C\) if and only if \(B \le C\) and \(B \ne C.\)
References
Greco G, Malizia E, Palopoli L, Scarcello F (2015) The complexity of the nucleolus in compact games. ACM Trans Comput Theory (TOCT) 7(1):3
Llerena F, Núñez M (2011) A geometric characterization of the nucleolus of the assignment game. Econ Bull 31(4):3275–3285
Llerena F, Núñez M, Rafels C (2015) An axiomatization of the nucleolus of assignment games. Int J Game Theory 44:1–15
Martínez-de-Albéniz FJ, Rafels C, Ybern N (2013a) On the nucleolus of \(2 \times 2\) assignment games. Econ Bull 33(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
Martínez-de-Albéniz FJ, Rafels C, Ybern N (2015) Insights into the nucleolus of the assignment game. Working paper E15/333 Universitat de Barcelona, pp 1–32
Núñez M (2004) A note on the nucleolus and the kernel of the assignment game. Int J Game Theory 33:55–65
Núñez M, Rafels C (2002) Buyer-seller exactness in the assignment game. Int J Game Theory 31:423–436
Núñez M, Rafels C (2015) A survey on assignment markets. J Dyn Games 3&4:227–256
Schmeidler D (1969) The nucleolus of a characteristic function game. SIAM J Appl Math 17:1163–1170
Shapley LS, Shubik M (1972) The assignment game I: the core. Int J Game Theory 1:111–130
Solymosi T, Raghavan TES (1994) An algorithm for finding the nucleolus of assignment games. Int J Game Theory 23:119–143
Topkis DM (1998) Supermodularity and complementarity. Princeton University Press, Princeton
Acknowledgements
Financial support from research grant ECO2017-86481-P (Ministerio de Economía y Competitividad, AEI/FEDER, UE) is gratefully acknowledged, and from the Generalitat de Catalunya, through grant 2017 SGR 778.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Martínez-de-Albéniz, F.J., Rafels, C. & Ybern, N. A note on assignment games with the same nucleolus. TOP 27, 187–198 (2019). https://doi.org/10.1007/s11750-019-00498-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-019-00498-1