On the Exhaustiveness of Truncation and Dropping Strategies in Many-to-Many Matching Markets
AbstractWe consider two-sided many-to-many matching markets in which each worker may work for multiple firms and each firm may hire multiple workers. We study individual and group manipulations in centralized markets that employ (pairwise) stable mechanisms and that require participants to submit rank order lists of agents on the other side of the market. We are interested in simple preference manipulations that have been reported and studied in empirical and theoretical work: truncation strategies, which are the lists obtained by removing a tail of least preferred partners from a preference list, and the more general dropping strategies, which are the lists obtained by only removing partners from a preference list (i.e., no reshuffling). We study when truncation/dropping strategies are exhaustive for a group of agents on the same side of the market, i.e., when each match resulting from preference manipulations can be replicated or improved upon by some truncation/dropping strategies. We prove that for each stable mechanism, dropping strategies are exhaustive for each group of agents on the same side of the market (Theorem 1), i.e., independently of the quotas. Then, we show that for each stable mechanism, truncation strategies are exhaustive for each agent with quota 1 (Theorem 2). Finally, we show that this result cannot be extended neither to individual manipulations when the agent's quota is larger than 1 (even when all other agents' quotas equal 1 - Example 1), nor to group manipulations (even when all quotas equal 1 - Example 2).
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Barcelona Graduate School of Economics in its series Working Papers with number 632.
Date of creation: May 2012
Date of revision:
matching; many-to-many; stability; manipulability; truncation strategies; dropping strategies;
Other versions of this item:
- Paula Jaramillo & Cagatay Kay & Flip Klijn, 2012. "On the Exhaustiveness of Truncation and Dropping Strategies in Many-to-Many Matching Markets," DOCUMENTOS CEDE 010316, UNIVERSIDAD DE LOS ANDES-CEDE.
- Paula Jaramillo & Kagi Cagatay & Flip Klijn, 2012. "On the exhaustiveness of truncation and dropping strategies in many-to-many matching markets," DOCUMENTOS DE TRABAJO 009997, UNIVERSIDAD DEL ROSARIO.
- C78 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Bargaining Theory; Matching Theory
- D60 - Microeconomics - - Welfare Economics - - - General
This paper has been announced in the following NEP Reports:
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Klaus, Bettina & Walzl, Markus, 2006.
"Stable Many-to-Many Matchings with Contracts,"
042, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
- Sotomayor, Marilda, 1999. "Three remarks on the many-to-many stable matching problem," Mathematical Social Sciences, Elsevier, vol. 38(1), pages 55-70, July.
- Roth, Alvin E & Sotomayor, Marilda, 1989. "The College Admissions Problem Revisited," Econometrica, Econometric Society, vol. 57(3), pages 559-70, May.
- Flip Klijn & Ayse Yazici, 2014.
"A Many-to-Many "Rural Hospital Theorem","
567, Barcelona Graduate School of Economics.
- Roth, Alvin E, 1991. "A Natural Experiment in the Organization of Entry-Level Labor Markets: Regional Markets for New Physicians and Surgeons in the United Kingdom," American Economic Review, American Economic Association, vol. 81(3), pages 415-40, June.
- Ruth Mart?ez & Jordi MassóAuthor-Name: Alejandro Neme & Jorge Oviedo, . "An Algorithm To Compute The Set Of Many-To-Many Stable Matchings," UFAE and IAE Working Papers 457.00, Unitat de Fonaments de l'Anàlisi Econòmica (UAB) and Institut d'Anàlisi Econòmica (CSIC).
- Kelso, Alexander S, Jr & Crawford, Vincent P, 1982. "Job Matching, Coalition Formation, and Gross Substitutes," Econometrica, Econometric Society, vol. 50(6), pages 1483-1504, November.
- Fuhito Kojima & Parag A. Pathak, 2009. "Incentives and Stability in Large Two-Sided Matching Markets," American Economic Review, American Economic Association, vol. 99(3), pages 608-27, June.
- Roth, Alvin E., 1985. "The college admissions problem is not equivalent to the marriage problem," Journal of Economic Theory, Elsevier, vol. 36(2), pages 277-288, August.
- Marilda Sotomayor, 1999. "The lattice structure of the set of stable outcomes of the multiple partners assignment game," International Journal of Game Theory, Springer, vol. 28(4), pages 567-583.
- Ahmet Alkan, 2001. "original papers : On preferences over subsets and the lattice structure of stable matchings," Review of Economic Design, Springer, vol. 6(1), pages 99-111.
- Hideo Konishi & M. Utku Ünver, 2003.
"Credible Group Stability in Many-to-Many Matching Problems,"
Game Theory and Information
0309005, EconWPA, revised 06 Sep 2003.
- Konishi, Hideo & Unver, M. Utku, 2006. "Credible group stability in many-to-many matching problems," Journal of Economic Theory, Elsevier, vol. 129(1), pages 57-80, July.
- Hideo Konishi & M. Utku Unver, 2003. "Credible Group-Stability in Many-to-Many Matching Problems," Boston College Working Papers in Economics 570, Boston College Department of Economics, revised 19 Jan 2005.
- Roth, Alvin E, 1984. "Stability and Polarization of Interests in Job Matching," Econometrica, Econometric Society, vol. 52(1), pages 47-57, January.
- Roth, Alvin E, 1984. "The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory," Journal of Political Economy, University of Chicago Press, vol. 92(6), pages 991-1016, December.
- Ahmet Alkan, 2002. "A class of multipartner matching markets with a strong lattice structure," Economic Theory, Springer, vol. 19(4), pages 737-746.
- Ma, Jinpeng, 2010. "The singleton core in the college admissions problem and its application to the National Resident Matching Program (NRMP)," Games and Economic Behavior, Elsevier, vol. 69(1), pages 150-164, May.
- Sotomayor, Marilda, 2004. "Implementation in the many-to-many matching market," Games and Economic Behavior, Elsevier, vol. 46(1), pages 199-212, January.
- Mongell, Susan & Roth, Alvin E, 1991. "Sorority Rush as a Two-Sided Matching Mechanism," American Economic Review, American Economic Association, vol. 81(3), pages 441-64, June.
- Sonmez, Tayfun, 1997. "Manipulation via Capacities in Two-Sided Matching Markets," Journal of Economic Theory, Elsevier, vol. 77(1), pages 197-204, November.
- Paula Jaramillo & Çagatay Kayi & Flip Klijn, 2013.
"Equilibria under Deferred Acceptance: Dropping Strategies, Filled Positions, and Welfare,"
010737, UNIVERSIDAD DE LOS ANDES-CEDE.
- Jaramillo, Paula & Kayı, Çaǧatay & Klijn, Flip, 2013. "Equilibria under deferred acceptance: Dropping strategies, filled positions, and welfare," Games and Economic Behavior, Elsevier, vol. 82(C), pages 693-701.
- Paula Jaramillo & Çagatay Kayi & Flip Klijn, 2013. "Equilibria under Deferred Acceptance: Dropping Strategies, Filled Positions, and Welfare," Working Papers 686, Barcelona Graduate School of Economics.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Bruno Guallar).
If references are entirely missing, you can add them using this form.