IDEAS home Printed from https://ideas.repec.org/p/aah/aarhec/2015-23.html
   My bibliography  Save this paper

Dynamic Matching Markets and the Deferred Acceptance Mechanism

Author

Listed:
  • John Kennes

    () (Department of Economics and Business Economics, Aarhus University, Denmark)

  • Daniel Monte

    (Department of Economics and Business Economics, Aarhus University, Denmark and Sao Paulo School of Economics, Brazil)

  • Norovsambuu Tumennasan

    (Department of Economics and Business Economics, Aarhus University, Denmark and Department of Economics, Dalhousie University, Canada)

Abstract

In many dynamic matching markets, priorities depend on previous allocations. In such environments, agents on the proposing side can manipulate the period-by-period deferred acceptance (DA) mechanism. We show that the fraction of agents with incentives to manipulate the DA mechanism approaches zero as the market size increases. In addition, we provide a novel al- gorithm to calculate the percentage of markets that can be manipulated. Based on randomly generated data, we find that the DA becomes approximately non-manipulable when the schools capacity reaches 20. Our theoretical and simulation results together justify the implementation of the period-by-period DA mechanism in dynamic markets.

Suggested Citation

  • John Kennes & Daniel Monte & Norovsambuu Tumennasan, 2015. "Dynamic Matching Markets and the Deferred Acceptance Mechanism," Economics Working Papers 2015-23, Department of Economics and Business Economics, Aarhus University.
  • Handle: RePEc:aah:aarhec:2015-23
    as

    Download full text from publisher

    File URL: ftp://ftp.econ.au.dk/afn/wp/15/wp15_23.pdf
    Download Restriction: no

    References listed on IDEAS

    as
    1. Roth, Alvin E. & Sonmez, Tayfun & Utku Unver, M., 2005. "Pairwise kidney exchange," Journal of Economic Theory, Elsevier, vol. 125(2), pages 151-188, December.
    2. Manea, Mihai, 2009. "Asymptotic ordinal inefficiency of random serial dictatorship," Theoretical Economics, Econometric Society, vol. 4(2), June.
    3. Kojima, Fuhito & Manea, Mihai, 2010. "Incentives in the probabilistic serial mechanism," Journal of Economic Theory, Elsevier, vol. 145(1), pages 106-123, January.
    4. Damiano, Ettore & Lam, Ricky, 2005. "Stability in dynamic matching markets," Games and Economic Behavior, Elsevier, vol. 52(1), pages 34-53, July.
    5. Tayfun Sönmez & Alvin E. Roth & M. Utku Ünver, 2007. "Efficient Kidney Exchange: Coincidence of Wants in Markets with Compatibility-Based Preferences," American Economic Review, American Economic Association, vol. 97(3), pages 828-851, June.
    6. Monte, Daniel & Tumennasan, Norovsambuu, 2015. "Centralized allocation in multiple markets," Journal of Mathematical Economics, Elsevier, vol. 61(C), pages 74-85.
    7. repec:hrv:faseco:30831454 is not listed on IDEAS
    8. Kojima, Fuhito, 2010. "Impossibility of stable and nonbossy matching mechanisms," Economics Letters, Elsevier, vol. 107(1), pages 69-70, April.
    9. Kadam, Sangram V. & Kotowski, Maciej H., 2015. "Multi-period Matching," Working Paper Series rwp15-030, Harvard University, John F. Kennedy School of Government.
    10. Yeon-Koo Che & Fuhito Kojima, 2010. "Asymptotic Equivalence of Probabilistic Serial and Random Priority Mechanisms," Econometrica, Econometric Society, vol. 78(5), pages 1625-1672, September.
    11. John Kennes Jr. & Daniel Monte Jr. & Norovsambuu Tumennasan Jr., 2014. "The Day Care Assignment: A Dynamic Matching Problem," American Economic Journal: Microeconomics, American Economic Association, vol. 6(4), pages 362-406, November.
    12. Alvin E. Roth & Tayfun Sönmez & M. Utku Ünver, 2004. "Kidney Exchange," The Quarterly Journal of Economics, Oxford University Press, vol. 119(2), pages 457-488.
    13. Francis Bloch & David Cantala, 2013. "Markovian assignment rules," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 40(1), pages 1-25, January.
    14. Pereyra, Juan Sebastián, 2013. "A dynamic school choice model," Games and Economic Behavior, Elsevier, vol. 80(C), pages 100-114.
    15. Parag A. Pathak & Alvin E. Roth, 2013. "Matching with Couples: Stability and Incentives in Large Markets," The Quarterly Journal of Economics, Oxford University Press, vol. 128(4), pages 1585-1632.
    16. Atila Abdulkadiroglu & Parag A. Pathak & Alvin E. Roth, 2009. "Strategy-proofness versus Efficiency in Matching with Indifferences: Redesigning the New York City High School Match," NBER Working Papers 14864, National Bureau of Economic Research, Inc.
    17. M. Utku Ünver, 2010. "Dynamic Kidney Exchange," Review of Economic Studies, Oxford University Press, vol. 77(1), pages 372-414.
    18. Atila Abdulkadiroglu & Tayfun Sönmez, 2003. "School Choice: A Mechanism Design Approach," American Economic Review, American Economic Association, vol. 93(3), pages 729-747, June.
    19. Morimitsu Kurino, 2014. "House Allocation with Overlapping Generations," American Economic Journal: Microeconomics, American Economic Association, vol. 6(1), pages 258-289, February.
    20. Elliott Peranson & Alvin E. Roth, 1999. "The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design," American Economic Review, American Economic Association, vol. 89(4), pages 748-780, September.
    21. Atila Abdulkadiroglu & Parag A. Pathak & Alvin E. Roth, 2009. "Strategy-Proofness versus Efficiency in Matching with Indifferences: Redesigning the NYC High School Match," American Economic Review, American Economic Association, vol. 99(5), pages 1954-1978, December.
    22. 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.
    23. Eduardo M. Azevedo & Jacob D. Leshno, 2016. "A Supply and Demand Framework for Two-Sided Matching Markets," Journal of Political Economy, University of Chicago Press, vol. 124(5), pages 1235-1268.
    24. Balinski, Michel & Sonmez, Tayfun, 1999. "A Tale of Two Mechanisms: Student Placement," Journal of Economic Theory, Elsevier, vol. 84(1), pages 73-94, January.
    Full references (including those not matched with items on IDEAS)

    Citations

    Blog mentions

    As found by EconAcademics.org, the blog aggregator for Economics research:
    1. Dynamic matching when what you get now may determine your future priorities
      by Al Roth in Market Design on 2016-02-15 17:46:00

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Andersson, Tommy & Ehlers, Lars & Martinello, Alessandro, 2018. "Dynamic Refugee Matching," Working Papers 2018:7, Lund University, Department of Economics.
    2. Kotowski, Maciej H., 2015. "A Note on Stability in One-to-One, Multi-period Matching Markets," Working Paper Series rwp15-042, Harvard University, John F. Kennedy School of Government.

    More about this item

    Keywords

    Large market; dynamic school choice; deferred acceptance mechanism;

    JEL classification:

    • C78 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Bargaining Theory; Matching Theory
    • D61 - Microeconomics - - Welfare Economics - - - Allocative Efficiency; Cost-Benefit Analysis
    • D78 - Microeconomics - - Analysis of Collective Decision-Making - - - Positive Analysis of Policy Formulation and Implementation
    • I20 - Health, Education, and Welfare - - Education - - - General

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:aah:aarhec:2015-23. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (). General contact details of provider: http://www.econ.au.dk/afn/ .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.