On the exhaustiveness of truncation and dropping strategies in many-to-many matching markets
We 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...
| Autores Principales: | , , |
|---|---|
| Formato: | Documento de trabajo (Working Paper) |
| Lenguaje: | Español (Spanish) |
| Publicado: |
Universidad del Rosario
2012
|
| Materias: | |
| Acceso en línea: | http://repository.urosario.edu.co/handle/10336/10830 |
| id |
ir-10336-10830 |
|---|---|
| recordtype |
dspace |
| institution |
EdocUR - Universidad del Rosario |
| collection |
DSpace |
| language |
Español (Spanish) |
| topic |
Economía laboral Economía laboral Mercado laboral::Investigaciones Trabajadores::Investigaciones Matching Many–to–many Stability Manipulability Truncation strategies Dropping strategies |
| spellingShingle |
Economía laboral Economía laboral Mercado laboral::Investigaciones Trabajadores::Investigaciones Matching Many–to–many Stability Manipulability Truncation strategies Dropping strategies Jaramillo, Paula Kayi, Cagatay Klijn, Flip On the exhaustiveness of truncation and dropping strategies in many-to-many matching markets |
| description |
We 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, truncation strategies are exhaustive for each agent with quota 1 (Theorem 1). We show that this result cannot be extended neither to group manipulations (even when all quotas equal 1 – Example 1), nor to individual manipulations when the agent’s quota is larger than 1 (even when all other agents’ quotas equal 1 – Example 2). Finally, we prove that for each stable mechanism, dropping strategies are exhaustive for each group of agents on the same side of the market (Theorem 2), i.e., independently of the quotas. |
| format |
Documento de trabajo (Working Paper) |
| author |
Jaramillo, Paula Kayi, Cagatay Klijn, Flip |
| author_facet |
Jaramillo, Paula Kayi, Cagatay Klijn, Flip |
| author_sort |
Jaramillo, Paula |
| title |
On the exhaustiveness of truncation and dropping strategies in many-to-many matching markets |
| title_short |
On the exhaustiveness of truncation and dropping strategies in many-to-many matching markets |
| title_full |
On the exhaustiveness of truncation and dropping strategies in many-to-many matching markets |
| title_fullStr |
On the exhaustiveness of truncation and dropping strategies in many-to-many matching markets |
| title_full_unstemmed |
On the exhaustiveness of truncation and dropping strategies in many-to-many matching markets |
| title_sort |
on the exhaustiveness of truncation and dropping strategies in many-to-many matching markets |
| publisher |
Universidad del Rosario |
| publishDate |
2012 |
| url |
http://repository.urosario.edu.co/handle/10336/10830 |
| _version_ |
1712098359738630144 |
| spelling |
ir-10336-108302021-09-07T05:00:36Z On the exhaustiveness of truncation and dropping strategies in many-to-many matching markets Jaramillo, Paula Kayi, Cagatay Klijn, Flip Economía laboral Economía laboral Mercado laboral::Investigaciones Trabajadores::Investigaciones Matching Many–to–many Stability Manipulability Truncation strategies Dropping strategies We 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, truncation strategies are exhaustive for each agent with quota 1 (Theorem 1). We show that this result cannot be extended neither to group manipulations (even when all quotas equal 1 – Example 1), nor to individual manipulations when the agent’s quota is larger than 1 (even when all other agents’ quotas equal 1 – Example 2). Finally, we prove that for each stable mechanism, dropping strategies are exhaustive for each group of agents on the same side of the market (Theorem 2), i.e., independently of the quotas. 2012-09 2015-09-18T20:34:41Z info:eu-repo/semantics/workingPaper info:eu-repo/semantics/acceptedVersion Jaramillo, P., Kayi, Ç., & Klijn, F. (2012). On the exhaustiveness of truncation and dropping strategies in many-to-many matching markets. Bogotá: Universidad del Rosario, Facultad de Economía. http://repository.urosario.edu.co/handle/10336/10830 Universidad del Rosario, Facultad de Economía spa info:eu-repo/semantics/openAccess application/pdf Universidad del Rosario Facultad de Economía instname:Universidad del Rosario reponame:Repositorio Institucional EdocUR instname:Universidad del Rosario A. Alkan (1999). On the Properties of Stable Many–to–Many Matchings under Responsive Preferences. In: Alkan, A., Aliprantis, C.D., and N.C. Yannelis (Eds.), Current Trends in Economics: Theory and Applications. Vol. 8. Studies in Economic Theory. Berlin, Heidelberg: Springer. A. Alkan (2001). On Preferences over Subsets and the Lattice Structure of Stable Matchings. Review of Economic Design 6(1): 99–111. A. Alkan (2002). A Class of Multipartner Matching Markets with a Strong Lattice Structure. Economic Theory 19(4): 737–746. M. Ba¨ıou and M. Balinski (2000). Many–to–Many Matchings: Stable Polyandrous Polygamy (or Polygamous Polyandry). Discrete Applied Mathematics 101(1): 1–12. C. Blair (1988). The Lattice Structure of the Set of Stable Matchings with Multiple Partners. Mathematics of Operations Research 13(4): 619–628. P. Coles (2009). Optimal Truncation in Matching Markets. Mimeo. Harvard Business School. L.E. Dubins and D.A. Freedman (1981). Machiavelli and the Gale–Shapley Algorithm. American Mathematical Monthly 88(7): 485–494. F. Echenique and J. Oviedo (2006). A Theory of Stability in Many–to–Many Matching Markets. Theoretical Economics 1(2): 233–273. L. Ehlers (2008). Truncation Strategies in Matching Markets. Mathematics of Operations Research 33(2): 327–335. L. Fleiner (2003). A Fixed–Point Approach to Stable Matchings and Some Applications. Mathematics of Operations Research 28(1): 103–126. B. Klaus and M. Walzl (2009). Stable Many–to–Many Matchings with Contracts. Journal of Mathematical Economics, 45(7): 422–434. F. Kojima and P.A. Pathak (2009). Incentives and Stability in Large Two–Sided Matching Markets. American Economic Review, 99(3): 608–627. H. Konishi and M.U. Unver (2006). Credible Group–Stability in Many–to–Many Matching ¨ Problems. Journal of Economic Theory, 129(1): 57–80. J. Ma (2010). The Singleton Core in the College–admissions Problem and its Application to the National Resident Matching Program (NRMP). Games and Economic Behavior, 69(1): 150–164. R. Mart´ınez, J. Mass´o, A. Neme, and J. Oviedo (2004). An Algorithm to Compute the Set of Many–to–Many Stable Matchings. Mathematical Social Sciences 47(2): 187–210. S. Mongell and A.E. Roth (1991). Sorority Rush as a Two–Sided Matching Mechanism. American Economic Review 81(3): 441–464. A.E. Roth (1982). The Economics of Matching: Stability and Incentives. Mathematics of Operations Research 7(4): 617–628. A.E. Roth (1985a). The College Admission Problem is not Equivalent to the Marriage Problem. Journal of Economic Theory 36(2): 277–288. A.E. Roth and U.G. Rothblum (1999). Truncation Strategies in Matching Markets – In Search of Advice for Participants. Econometrica 67(1): 21–43. A.E. Roth and M.A.O. Sotomayor (1989). The College Admissions Problem Revisited. Econometrica 57(3): 559–570. M.A.O. Sotomayor (1999a). The Lattice Structure of the Set of Stable Outcomes of the Multiple Partners Assignment Game. International Journal of Game Theory 28(4): 567– 583 M.A.O. Sotomayor (1999b). Three Remarks on the Many–to–Many Stable Matching Problem. Mathematical Social Sciences 38(1): 55–70. M.A.O. Sotomayor (2004). Implementation in the Many–to–Many Matching Market. Games and Economic Behavior 46(1): 199–212. |
| score |
12,131701 |