zbMATH — the first resource for mathematics

Implementation in generalized matching problems. (English) Zbl 0876.90012
Summary: We search for (Nash) implementable solutions on a class of one-to-one matching problems which includes both the housing market and marriage problems. We show that the core correspondence is implementable. We show, furthermore, that any solution that is Pareto efficient, individually rational, and implementable is a supersolution of the core correspondence. That is, the core correspondence is the minimal solution that is Pareto efficient, individually rational, and implementable. A corollary of independent interest in the context of the housing market is that the core correspondence is the only single-valued solution that is Pareto efficient, individually rational, and implementable.

91B14 Social choice
Full Text: DOI
[1] Alcalde, J., Implementation of stable solutions to marriage problems, (), 240-254 · Zbl 0852.90011
[2] Alcalde, J.; Barberà, S., Top dominance and the possibility of strategy-proof stable solutions to matching problems, Economic theory, 4, 417-435, (1994) · Zbl 0830.90004
[3] Danilov, V., Implementation via Nash equilibria, Econometrica, 60, 43-56, (1992) · Zbl 0761.90004
[4] Dutta, B.; Sen, A., A necessary and sufficient condition of two-person Nash implementation, Review of economic studies, 58, 121-128, (1991) · Zbl 0717.90005
[5] Gale, D.; Shapley, L., College admissions and the stability of marriage, American mathematical monthly, 69, 9-15, (1962) · Zbl 0109.24403
[6] Gibbard, A., Manipulation of voting schemes: A general result, Econometrica, 41, 587-601, (1973) · Zbl 0325.90081
[7] Kara, T.; Sönmez, T., Nash implementation of matching rules, (), 425-439 · Zbl 0854.90002
[8] Ma, J., Strategy-proofness and the strict core in a market with indivisibilities, International journal of game theory, 23, 75-83, (1994) · Zbl 0804.90014
[9] Ma, J., Stable matchings and rematching-proof equilibria in a two-sided matching market, (), 352-369 · Zbl 0852.90015
[10] Maskin, E., Nash equilibrium and welfare optimality, MIT working paper, (1977) · Zbl 0956.91034
[11] Maskin, E., The theory of implementation in Nash equilibrium: A survey, ()
[12] Moore, J., Implementation in environments with complete information, ()
[13] Moore, J.; Repullo, R., Nash implementation: A full characterization, Econometrica, 58, 1083-1099, (1990) · Zbl 0731.90009
[14] Roth, A., Incentive compatibility in a market with indivisibilities, Economics letters, 9, 127-132, (1982) · Zbl 0722.90009
[15] Roth, A., The economics of matching: stability and incentives, Mathematics of operations research, 7, 617-628, (1982) · Zbl 0496.90008
[16] Roth, A.; Postlewaite, A., Weak versus strong domination in a market with indivisible goods, Journal of mathematical economics, 4, 131-137, (1977) · Zbl 0368.90025
[17] Roth, A.; Sotomayor, M., Two-sided matching: A study in game theoretic modeling and analysis, (1990), Cambridge University Press London/New York · Zbl 0726.90003
[18] Saijo, T., Strategy space reductions in Maskin’s theorem: sufficient conditions for Nash implementation, Econometrica, 56, 693-700, (1988) · Zbl 0652.90014
[19] Satterthwaite, M.A., Strategy-proofness and Arrow’s conditions: existence and correspondence theorems for voting procedures and social welfare functions, Journal of economic theory, 10, 187-216, (1975) · Zbl 0315.90088
[20] Shapley, L.; Scarf, H., On cores and indivisibility, Journal of mathematical economics, 1, 23-28, (1974) · Zbl 0281.90014
[21] Sjöström, T., On the necessary and sufficient conditions for Nash implementation, Social choice and welfare, 8, 333-340, (1991) · Zbl 0734.90007
[22] Sönmez, T., Strategy-proofness and singleton cores in generalized matching problems, University of rochester working paper, (1994)
[23] Sönmez, T., Strategy-proofness in many-to-one matching problems, University of rochester working paper, (1996)
[24] Sprumont, Y., Strategyproof collective choice in economic and political environments, Canadian journal of economics, 28, 68-107, (1995)
[25] Thomson, W., Concepts of implementation, University of rochester working paper, (1993)
[26] Thomson, W., Strategy-proof allocation rules, University of rochester working paper, (1994)
[27] Williams, S., Realization and Nash implementation: two aspects of mechanism design, Econometrica, 54, 139-151, (1986) · Zbl 0579.90109
[28] Yamato, T., On Nash implementation of social choice correspondences, Games and economic behavior, 4, 484-492, (1992) · Zbl 0773.90003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.