IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v65y2017i2p314-336.html
   My bibliography  Save this article

Course Match: A Large-Scale Implementation of Approximate Competitive Equilibrium from Equal Incomes for Combinatorial Allocation

Author

Listed:
  • Eric Budish

    (University of Chicago, Chicago, Illinois 60637)

  • Gérard P. Cachon

    (University of Pennsylvania, Philadelphia, Pennsylvania 19104)

  • Judd B. Kessler

    (University of Pennsylvania, Philadelphia, Pennsylvania 19104)

  • Abraham Othman

    (University of Pennsylvania, Philadelphia, Pennsylvania 19104)

Abstract

Combinatorial allocation involves assigning bundles of items to agents when the use of money is not allowed. Course allocation is one common application of combinatorial allocation, in which the bundles are schedules of courses and the assignees are students. Existing mechanisms used in practice have been shown to have serious flaws, which lead to allocations that are inefficient, unfair, or both. A recently developed mechanism is attractive in theory but has several features that limit its feasibility for practice. This paper reports on the design and implementation of a new course allocation mechanism, Course Match, that is suitable in practice. To find allocations, Course Match performs a massive parallel heuristic search that solves billions of mixed-integer programs to output an approximate competitive equilibrium in a fake-money economy for courses. Quantitative summary statistics for two semesters of full-scale use at a large business school (the Wharton School of Business, which has about 1,700 students and up to 350 courses in each semester) demonstrate that Course Match is both fair and efficient, a finding reinforced by student surveys showing large gains in satisfaction and perceived fairness.

Suggested Citation

  • Eric Budish & Gérard P. Cachon & Judd B. Kessler & Abraham Othman, 2017. "Course Match: A Large-Scale Implementation of Approximate Competitive Equilibrium from Equal Incomes for Combinatorial Allocation," Operations Research, INFORMS, vol. 65(2), pages 314-336, April.
    • Handle: RePEc:inm:oropre:v:65:y:2017:i:2:p:314-336
    DOI: 10.1287/opre.2016.1544
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/opre.2016.1544
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2016.1544?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Eric Budish & Estelle Cantillon, 2012. "The Multi-unit Assignment Problem: Theory and Evidence from Course Allocation at Harvard," American Economic Review, American Economic Association, vol. 102(5), pages 2237-2271, August.
    2. Aradhna Krishna & M. Utku Ünver, 2008. "Research Note—Improving the Efficiency of Course Bidding at Business Schools: Field and Laboratory Studies," Marketing Science, INFORMS, vol. 27(2), pages 262-282, 03-04.
    3. Alvin E. Roth, 2002. "The Economist as Engineer: Game Theory, Experimentation, and Computation as Tools for Design Economics," Econometrica, Econometric Society, vol. 70(4), pages 1341-1378, July.
    4. Eric Budish, 2011. "The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes," Journal of Political Economy, University of Chicago Press, vol. 119(6), pages 1061-1103.
    5. 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.
    Full references (including those not matched with items on IDEAS)

    Citations

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


    Cited by:

    1. Alexander Teytelboym & Shengwu Li & Scott Duke Kominers & Mohammad Akbarpour & Piotr Dworczak, 2021. "Discovering Auctions: Contributions of Paul Milgrom and Robert Wilson," Scandinavian Journal of Economics, Wiley Blackwell, vol. 123(3), pages 709-750, July.
    2. Kyle Greenberg & Parag A. Pathak & Tayfun Sönmez, 2020. "Mechanism Design meets Priority Design: Redesigning the US Army’s Branching Process Through Market Design," Boston College Working Papers in Economics 1035, Boston College Department of Economics.
    3. Battal Dou{g}an & Kenzo Imamura & M. Bumin Yenmez, 2022. "Market Design with Deferred Acceptance: A Recipe for Policymaking," Papers 2209.06777, arXiv.org.
    4. Eric Budish & Peter Cramton & Albert S. Kyle & Jeongmin Lee & David Malec, 2022. "Flow Trading," ECONtribute Discussion Papers Series 146, University of Bonn and University of Cologne, Germany.
      • Eric Budish & Peter Cramton & Albert S. Kyle & Jeongmin Lee & David Malec, 2023. "Flow Trading," NBER Working Papers 31098, National Bureau of Economic Research, Inc.
    5. Nikhil Agarwal & Eric Budish, 2021. "Market Design," NBER Working Papers 29367, National Bureau of Economic Research, Inc.
    6. P'eter Bir'o & M'arton Gyetvai, 2021. "Online voluntary mentoring: Optimising the assignment of students and mentors," Papers 2102.06671, arXiv.org.
    7. Julien Combe & Vladyslav Nora & Olivier Tercieux, 2021. "Dynamic assignment without money: Optimality of spot mechanisms," Working Papers 2021-11, Center for Research in Economics and Statistics.
    8. Andrea Canidio, 2023. "Auctions with Tokens: Monetary Policy as a Mechanism Design Choice," Papers 2301.13794, arXiv.org, revised Aug 2023.
    9. Eric Budish & Judd B. Kessler, 2022. "Can Market Participants Report Their Preferences Accurately (Enough)?," Management Science, INFORMS, vol. 68(2), pages 1107-1130, February.
    10. Biró, Péter & Klijn, Flip & Pápai, Szilvia, 2022. "Serial Rules in a Multi-Unit Shapley-Scarf Market," Games and Economic Behavior, Elsevier, vol. 136(C), pages 428-453.
    11. Federico Echenique & Sumit Goel & SangMok Lee, 2022. "Stable allocations in discrete exchange economies," Papers 2202.04706, arXiv.org, revised Feb 2024.
    12. Eric Budish & Robin S. Lee & John J. Shim, 2024. "A Theory of Stock Exchange Competition and Innovation: Will the Market Fix the Market?," Journal of Political Economy, University of Chicago Press, vol. 132(4), pages 1209-1246.
    13. Matteo Aquilina & Eric Budish & Peter O'Neill, 2021. "Quantifying the high-frequency trading "arms race"," BIS Working Papers 955, Bank for International Settlements.
    14. Combe, Julien & Nora, Vladyslav & Tercieux, Olivier, 0. "Dynamic assignment without money: optimality of spot mechanisms," Theoretical Economics, Econometric Society.
    15. Kyle Greenberg & Parag A. Pathak & Tayfun Sonmez, 2021. "Mechanism Design meets Priority Design: Redesigning the US Army's Branching Process," Papers 2106.06582, arXiv.org.
    16. Martin Bichler & Soeren Merting, 2021. "Randomized Scheduling Mechanisms: Assigning Course Seats in a Fair and Efficient Way," Production and Operations Management, Production and Operations Management Society, vol. 30(10), pages 3540-3559, October.
    17. Yan Chen & Peter Cramton & John A. List & Axel Ockenfels, 2021. "Market Design, Human Behavior, and Management," Management Science, INFORMS, vol. 67(9), pages 5317-5348, September.
    18. Shivam Gupta & Wei Chen & Milind Dawande & Ganesh Janakiraman, 2023. "Three Years, Two Papers, One Course Off: Optimal Nonmonetary Reward Policies," Management Science, INFORMS, vol. 69(5), pages 2852-2869, May.
    19. Biró, Péter & Gyetvai, Márton, 2023. "Online voluntary mentoring: Optimising the assignment of students and mentors," European Journal of Operational Research, Elsevier, vol. 307(1), pages 392-405.
    20. Laschever, Ron A. & Weinstein, Russell, 2021. "Preference Signaling and Worker-Firm Matching: Evidence from Interview Auctions," IZA Discussion Papers 14622, Institute of Labor Economics (IZA).
    21. Thomas L. Magnanti & Karthik Natarajan, 2018. "Allocating Students to Multidisciplinary Capstone Projects Using Discrete Optimization," Interfaces, INFORMS, vol. 48(3), pages 204-216, June.
    22. Budish, Eric & Reny, Philip J., 2020. "An improved bound for the Shapley–Folkman theorem," Journal of Mathematical Economics, Elsevier, vol. 89(C), pages 48-52.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Eric Budish & Estelle Cantillon, 2012. "The Multi-unit Assignment Problem: Theory and Evidence from Course Allocation at Harvard," American Economic Review, American Economic Association, vol. 102(5), pages 2237-2271, August.
    2. Yan Chen & Peter Cramton & John A. List & Axel Ockenfels, 2021. "Market Design, Human Behavior, and Management," Management Science, INFORMS, vol. 67(9), pages 5317-5348, September.
    3. Scott Duke Kominers & Alexander Teytelboym & Vincent P Crawford, 2017. "An invitation to market design," Oxford Review of Economic Policy, Oxford University Press and Oxford Review of Economic Policy Limited, vol. 33(4), pages 541-571.
    4. Kojima, Fuhito, 2013. "Efficient resource allocation under multi-unit demand," Games and Economic Behavior, Elsevier, vol. 82(C), pages 1-14.
    5. Franz Diebold & Haris Aziz & Martin Bichler & Florian Matthes & Alexander Schneider, 2014. "Course Allocation via Stable Matching," Business & Information Systems Engineering: The International Journal of WIRTSCHAFTSINFORMATIK, Springer;Gesellschaft für Informatik e.V. (GI), vol. 6(2), pages 97-110, April.
    6. Li, Mengling, 2020. "Ties matter: Improving efficiency in course allocation by allowing ties," Journal of Economic Behavior & Organization, Elsevier, vol. 178(C), pages 354-384.
    7. Dur, Umut Mert & Wiseman, Thomas, 2019. "School choice with neighbors," Journal of Mathematical Economics, Elsevier, vol. 83(C), pages 101-109.
    8. Eric Budish & Judd B. Kessler, 2022. "Can Market Participants Report Their Preferences Accurately (Enough)?," Management Science, INFORMS, vol. 68(2), pages 1107-1130, February.
    9. Ortega, Josué, 2020. "Multi-unit assignment under dichotomous preferences," Mathematical Social Sciences, Elsevier, vol. 103(C), pages 15-24.
    10. Hoda Atef Yekta & Robert Day, 2020. "Optimization-based Mechanisms for the Course Allocation Problem," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 641-660, July.
    11. Trifunović Dejan, 2019. "The Review of Methods for Assignment of Elective Courses at Universities," Economic Themes, Sciendo, vol. 57(4), pages 511-526, December.
    12. Kyle Greenberg & Parag A. Pathak & Tayfun Sönmez, 2020. "Mechanism Design meets Priority Design: Redesigning the US Army’s Branching Process Through Market Design," Boston College Working Papers in Economics 1035, Boston College Department of Economics.
    13. Kyle Greenberg & Parag A. Pathak & Tayfun Sonmez, 2021. "Mechanism Design meets Priority Design: Redesigning the US Army's Branching Process," Papers 2106.06582, arXiv.org.
    14. Eric Budish & Judd B. Kessler, 2016. "Can Market Participants Report their Preferences Accurately (Enough)?," NBER Working Papers 22448, National Bureau of Economic Research, Inc.
    15. Shengwu Li, 2017. "Ethics and market design," Oxford Review of Economic Policy, Oxford University Press and Oxford Review of Economic Policy Limited, vol. 33(4), pages 705-720.
    16. Marta Boczoń & Alistair J. Wilson, 2023. "Goals, Constraints, and Transparently Fair Assignments: A Field Study of Randomization Design in the UEFA Champions League," Management Science, INFORMS, vol. 69(6), pages 3474-3491, June.
    17. Fuhito Kojima & Hiroaki Odahara, 2022. "Toward market design in practice: a progress report," The Japanese Economic Review, Springer, vol. 73(3), pages 463-480, July.
    18. Alvin E. Roth & Tayfun Sönmez & M. Utku Ünver, 2004. "Kidney Exchange," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 119(2), pages 457-488.
    19. Muriel Niederle & Alvin E. Roth, 2009. "The Effects of a Centralized Clearinghouse on Job Placement, Wages, and Hiring Practices," NBER Chapters, in: Studies of Labor Market Intermediation, pages 235-271, National Bureau of Economic Research, Inc.
    20. Erlanson, Albin & Szwagrzak, Karol, 2013. "Strategy-Proof Package Assignment," Working Papers 2013:43, Lund University, Department of Economics.

    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:inm:oropre:v:65:y:2017:i:2:p:314-336. See general information about how to correct material in RePEc.

    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 bibliographic 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.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

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

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.