Strategy proofness and unanimity in many-to-one matching markets

Diss, Mostapha and Doghmi, Ahmed and Tlidi, Abdelmonaim (2016): Strategy proofness and unanimity in many-to-one matching markets.

Abstract

In this paper, we consider a standard model of many-to-one matching markets. First, we study the relation between strategy-proofness and unanimity under a certain requirement and we prove these two properties become equivalent. Second, we illustrate that this result has an immediate impact on the relation between strategy-proofness and Maskin monotonicity. Finally, we determine a close connexion between strategy-proofness and implementation literature. We provide under certain minimal requirements the foundation for reasoning the equivalence among dominant strategy implementation, standard Nash implementation, and partially honest Nash implementation.

• Item Type: MPRA Paper
• Language: English
• Keywords: Many-to-one matching markets; strategy-proofness; unanimity; Maskin monotonicity, implementation.
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C72 - Noncooperative Games; C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C78 - Bargaining Theory ; Matching Theory; D - Microeconomics > D7 - Analysis of Collective Decision-Making > D71 - Social Choice ; Clubs ; Committees ; Associations

References

[1] J. Alcalde and S. Barber a. Top dominance and the possibility of strategy-proof stable solutions to matching problems. Economic Theory, 4:417-435, 1994.

[2] K.J Arrow. Social choice and individual values. 2nd Edition. Wiley, New York, 1963.

[3] D. Black. On the rationale of group decision making. The Journal of Political Economy, 561:23-34, 1948.

[4] O. Bochet and T. Storcken. Maximal domains for Maskin monotone Pareto optimal and anonymous rules. In: Collective Decision Making: Views from Social Choice and Game Theory (Van Deemen, A. and Rusinowska, A. Eds), Springer, 43:57-68, 2010.

[5] V. Danilov. Implementation via Nash equilibrium. Econometrica, 60:43-56, 1992. [6] M. Diss, A. Doghmi, and A. Tlidi. Strategy proofness and unanimity in private good economies with single-peaked preferences. Working Paper, 2016.

[7] A. Doghmi. A simple necessary condition for partially honest Nash implementation. Working paper, 2015.

[8] A. Doghmi and A. Ziad. On partial honesty Nash implementation. Center for Research in Economics and Management (CREM), University of Rennes 1, University of Caen and CNRS in its series Economics Working Paper Archive (University of Rennes 1 and University of Caen) with number 201201, 2012.

[9] A. Doghmi and A. Ziad. On partially honest Nash implementation in private good economies with restricted domains: A su cient condition. The B.E.Journal of Theoretical Economics, 13:1-14, 2013a.

[10] A. Doghmi and A. Ziad. Nash implementation in private good economies with singleplateaued preferences and in matching problems. Mathematical Social Sciences, 73:32-39, 2015.

[11] B. Dutta and A. Sen. Nash implementation with partially honest individuals. Games and Economic Behavior, 74:154-169, 2012.

[12] D. Gale and L. Shapley. College admission and the stability of marriage. American Mathematical Monthly, 69:9-15, 1962.

[13] A. Gibbard. Manipulation of voting schemes: a general result. Econometrica, 41:587-601, 1973.

[14] C.J Haake and B. Klaus. Monotonicity and Nash implementation in matching markets with contracts. Economic Theory, 41:393-410, 2009.

[15] M. Hagiwara, H. Yamamura, and T. Yamato. An outcome mechanism for partially honest Nash implementation. Discussion Paper No. 2016-9, 2016.

[16] K. Hashimoto. Strategy-proofness versus e ciency on the Cobb-Douglas domain of exchange economies. Social Choice and Welfare, 31:457-473, 2008.

[17] J. W. Hat eld and P. Milgrom. Matching with contracts. American Economic Review, 95:913-935, 2005.

[18] T. Kara and T. Sonmez. Nash implementation of matching rules. Journal of Economic Theory, 68:425-439, 1996.

[19] T. Kara and T. Sonmez. Implementation of college admission rules. Economic Theory, 9:197-218, 1997.

[20] N. Kartik, O. Tercieux, and R. Holden. Simple mechanisms and preferences for honesty. Games and Economic Behavior, 83:284-290, 2014.

[21] B. Klaus and O. Bochet. The ralation between monotonicity and strategy-proofness. Social Choice and Welfare, 40:41-63, 2013.

[22] V. Korpela. Nash implementation theory - a note on full characterizations. Economics Letters, 108:283-285, 2010.

[23] V. Korpela. Nash implementation of stable many-to-one matching rules: a full characterization of the case with no externalities. Working paper, 2013.

[24] V. Korpela. Bayesian implementation with partially honest individuals. Social Choice and Welfare, 43:647-658, 2014.

[25] T. Kumano and M. Watabe. Dominant strategy implementation of stable rules. Games and Economic Behavior, 75:428-434, 2012.

[26] E. Maskin. Nash equilibrium and welfare optimality. M.I.T. mimeo, 1977. Published 1999 in the Review of Economic Studies 66, 23-38.

[27] H. Mizukami and T. Wakayama. New necessary and su cient conditions for secure implementation. Working paper, 2016.

[28] J. Moore and R. Repullo. Nash implementation: a full characterization. Econometrica, 58:1083-1100, 1990.

[29] H. Moulin. On strategy-proofness and single peakedness. Public Choice, 35:437-455, 1980.

[30] Satterthwaite M.A. Muller, E. The equivalence of strong positive association and strategy-proofness. Journal of Economic Theory, 14:412{418, 1977.

[31] J. Ortner. Direct implementation with minimal honest individuals. Games and Economic Behavior, 90:1-16, 2015.

[32] A.E. Roth. The economics of matching: stability and incentives. Mathematics of Operations Research, 7:617-628, 1982.

[33] A.E. Roth. The college admissions problem is not equivalent to the marriage problem. Journal of Economic Theory, 36:277-288, 1985.

[34] A.E. Roth and Sotomayor M. Two-sided matching: A study in game-theoretic modeling and analysis. Econometric Society Monographs. Cambridge University Press, 1990.

[35] T. Saijo, T. Sjostrom, and T. Yamato. Secure implementation. Theoritical Economics, 2:203-229, 2007.

[36] A. Saporiti. Securely implementable social choice rules with partially honest agents. Journal of Economic Theory, 154:2016-228, 2014.

[37] M.A. Satterthwaite. Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10:187-217, 1975.

[38] J. Schummer. Strategy-proofness versus e eciency on restricted domains of exchange economies. Social Choice and Welfare, 14:47-56, 1997.

[39] L. S. Shapley and H. Scarf. On cores and indivisibility. Journal of Mathematical Economics, 1:23-28, 1974.

[40] T. Sonmez. Strategy-proofness in many-to-one matching problems. Economic Design, 1:365-380, 1996a.

[41] T. Sonmez. Implementation in generalized matching problems. Journal of Mathematical Economics, 26:429-439, 1996b.

[42] K. Tadenuma and M. Toda. Implementable stable solutions to pure matching problems. Mathematical Social Siences, 35:121-132, 1998.

[43] T. Yamato. On Nash implementation of social choice correspondences. Games and Economic Behavior, 3:484-492, 1992.

[44] H. Yao and J. Yi. Social choice rules implemented in dominant strategies. Economics Letters, 97:197-200, 2007.