×

Compromises and rewards: stable and non-manipulable probabilistic matching. (English) Zbl 1417.91382

Summary: Can we reconcile stability with non-manipulability in two-sided matching problems by selecting lotteries over matchings? We parameterize, through sets of utility functions, how ordinal preferences induce preferences over lotteries and develop corresponding notions of ex-ante stability and non-manipulability. For most sets, the properties are incompatible. However, for the set of utility functions with increasing differences, stability and non-manipulability characterize compromises and rewards. This novel rule is fundamentally different from the one that has attracted most attention in the literature, deferred acceptance. We then derive complementary negative results that show that increasing differences essentially is a necessary condition for the properties to be compatible.

MSC:

91B68 Matching models
91B16 Utility theory
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Abdulkadiroğlu A, Sönmez T (1998) Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica 66:689-701 · Zbl 1019.91016
[2] Abdulkadiroğlu A, Sönmez T (1999) House allocation with existing tenants. J Econ Theory 88:233-260 · Zbl 0939.91068
[3] Abeledo HG, Rothblum UG (1994) Stable matchings and linear inequalities. Discret Appl Math 54(1):1-27 · Zbl 0820.90090
[4] Abeledo HG, Rothblum UG (1996) Stable matchings and linear programming. Linear Algebra Appl 245:321-333 · Zbl 0858.90093
[5] Alcalde J, Barberà S (1994) Top dominance and the possibility of strategy-proof stable solutions to matching problems. Econ Theory 4(3):417-435 · Zbl 0830.90004
[6] Azevedo EM, Budish E (2013) Strategy-proofness in the large. Research Paper 13-35, Chicago Booth · Zbl 1409.91115
[7] Aziz H (2015) Generalizing top trading cycles for housing markets with fractional endowments. Mimeo
[8] Bernheim BD, Slavov SN (2009) A solution concept for majority rule in dynamic settings. Rev Econ Stud 76(1):33-62 · Zbl 1153.91395
[9] Birkhoff G (1946) Three observations on linear algebra. Revi Univ Nac Tucuman Ser A 5:147-151
[10] Biró P, Fleiner T (2010) Fractional Solutions for NTU-games. In: Proceedings of COMSOC 2010: 3rd international workshop on computational social choice, pp 283-294
[11] Bogomolnaia A, Moulin H (2001) A new solution to the random assignment problem. J Econ Theory 100(2):295-328 · Zbl 1134.91357
[12] Bogomolnaia A, Moulin H (2004) Random matching under dichotomous preferences. Econometrica 72(1):257-279 · Zbl 1142.91691
[13] Bronfman S, Hassidim A, Afek A, Romm A, Sherberk R, Hassidim A, Massler A (2015) Assigning Israeli medical graduates to internships. Isr J Health Policy Res 4:6
[14] Chiappori P-A, Galichon A, Salanié B (2014) The roommate problem—is more stable than you think. CESifo Working Paper Series 4676, CESifo Group Munich
[15] Chung K-S (2000) On the existence of stable roommate matchings. Games Econ Behav 33:9-15
[16] Damiano E, Lam R (2005) Stability in dynamic matching markets. Games Econ Behav 52:34-53 · Zbl 1099.91076
[17] d’Aspremont C, Gérard-Varet L-A (1979) Incentives and incomplete information. J Public Econ 11:25-45
[18] Doğan B, Yildiz K (2015) Efficiency and stability of probabilistic assignments in marriage problems. Games Econ Behav 95:47-58 · Zbl 1347.91203
[19] Ehlers L, Majumdar D, Mishra D, Sen A (2016) Continuity and incentive compatibility in cardinal voting mechanisms. Working Paper · Zbl 1437.91128
[20] Gale D, Shapley LS (1962) College admissions and the stability of marriage. Am Math Mon 69:9-15 · Zbl 0109.24403
[21] Gudmundsson J (2014a) Sequences in pairing problems: a new approach to reconcile stability with strategy-proofness for elementary matching problems. Working Papers 2014:40, Lund University, Department of Economics
[22] Gudmundsson J (2014b) When do stable roommate matchings exist? A review. Rev Econ Design 18(2):151-161 · Zbl 1302.91155
[23] Jackson MO, Sonnenschein HF (2007) Overcoming incentive constraints by linking decisions. Econometrica 75(1):241-257 · Zbl 1201.91036
[24] Kadam SV, Kotowski MH (2016) Time horizons, lattice structures, and welfare in multi-period matching markets. Mimeo · Zbl 1419.91528
[25] Kesten O (2009) Why do popular mechanisms lack efficiency in random environments? J Econ Theory 144(5):2209-2226 · Zbl 1195.91119
[26] Kurino M (2009) Credibility, efficiency, and stability: a theory of dynamic matching markets. Mimeo
[27] Manjunath V (2013) Stability and the core of probabilistic marriage problems. Working Paper
[28] Manjunath V (2016) Markets for fractional partnerships. Games Econ Behav (forthcoming) · Zbl 1394.91305
[29] Mennle T, Seuken S (2017a) Hybrid mechanisms: trading off strategyproofness and efficiency of random assignment mechanisms. Working paper · Zbl 1458.91110
[30] Mennle T, Seuken S (2017b) Partial strategyproofness: relaxing strategyproofness for the random assignment problem. Working paper · Zbl 1458.91110
[31] Özkal-Sanver I (2004) A note on gender fairness in matching problems. Math Soc Sci 47(2):211-217 · Zbl 1076.91029
[32] Roth AE (1982) The economics of matching: stability and incentives. Math Oper Res 7(4):617-628 · Zbl 0496.90008
[33] Roth AE (1984) The evolution of the labor market for medical interns and residents: a case study in game theory. J Polit Econ 92(6):991-1016
[34] Roth AE (1991) A natural experiment in the organization of entry-level labor markets: regional markets for new physicians and surgeons in the United Kingdom. Am Econ Rev 81(3):415-440
[35] Roth AE, Peranson E (1999) The redesign of the matching market for American physicians: some engineering aspects of economic design. Am Econ Rev 89(4):748-780
[36] Roth AE, Shorrer RI (2015) The redesign of the medical intern assignment mechanism in Israel. Isr J Health Policy Res 4:11
[37] Roth AE, Sotomayor M (1990) Two-sided matching: a study in game-theoretic modeling and analysis. Econometric Society Monographs. Cambridge University Press, New York
[38] Roth AE, Rothblum UG, Vande Vate JH (1993) Stable matchings, optimal assignments, and linear programming. Math Oper Res 18:803-828 · Zbl 0806.90085
[39] Rothblum UG (1992) Characterization of stable matchings as extreme points of a polytope. Math Program 54:57-67 · Zbl 0773.90059
[40] Rubinstein A (1979) A note about the “Nowhere Denseness” of societies having an equilibrium under majority rule. Econometrica 47(2):511-514 · Zbl 0416.90006
[41] Shapley LS, Scarf HE (1974) On cores and indivisibility. J Math Econ 1:23-27 · Zbl 0281.90014
[42] Stasz C, van Stolk C (2007) The use of lottery systems in school admissions. Working Papers 460, RAND Europe
[43] Tan JJM (1991) A necessary and sufficient condition for the existence of a complete stable matching. J Algorithms 12:154-178 · Zbl 0715.68069
[44] Taylor BA, Trogdon JG (2007) Losing to win: tournament incentives in the National Basketball Association. J Labor Econ 20(1):23-41
[45] Teo C-P, Sethuraman J (1998) The geometry of fractional stable matchings and its application. Math Oper Res 23:874-891 · Zbl 0977.90046
[46] Valiant LG (1982) A scheme for fast parallel communication. SIAM J Comput 11(2):350-361 · Zbl 0478.94034
[47] Vande Vate JH (1989) Linear programming brings marital bliss. Oper Res Lett 8:147-153 · Zbl 0675.90058
[48] von Neumann J (1953) A certain zero-sum two-person game equivalent to the optimal assignment problem. In: Kuhn HW, Tucker AW (eds) Contributions to the theory of games (AM-28), vol. 2, Princeton University Press, pp 5-12 · Zbl 0050.14105
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.