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

Improving Community Cohesion in School Choice via Correlated-Lottery Implementation

Author

Listed:
  • Itai Ashlagi

    () (Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139)

  • Peng Shi

    () (Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139)

Abstract

In school choice, children submit a preference ranking over schools to a centralized assignment algorithm, which takes into account schools’ priorities over children and uses randomization to break ties. One criticism of existing school choice mechanisms is that they tend to disperse communities, so children do not go to school with others from their neighborhood. We suggest improving community cohesion by implementing a correlated lottery in a given school choice mechanism: we find a convex combination of deterministic assignments that maintains the original assignment probabilities, thus maintaining choice but improving community cohesion. To analyze the gain in cohesion for a wide class of mechanisms, we first prove the following characterization, which may be of independent interest: any mechanism that, in the large market limit, is nonatomic, Bayesian incentive compatible, symmetric, and efficient within each priority class is a “lottery-plus-cutoff” mechanism. This means that the large market limit can be described as follows: given the distribution of preferences, every student receives an identically distributed lottery number, every school sets a lottery cutoff for each priority class, and a student is assigned to her most preferred school for which she meets the cutoff. This generalizes liu-pycia-2012 to allow arbitrary priorities. Using this, we derive analytic expressions for maximum cohesion under a large market approximation. We show that the benefit of lottery-correlation is greater when students’ preferences are more correlated. In practice, although the correlated-lottery implementation problem is NP-hard, we present a heuristic that does well. We apply this to real data from Boston elementary school choice 2012 and find that we can increase cohesion by 79% for kindergarten 1 (K1) and 37% for kindergarten 2 (K2) new families. Greater cohesion gain is possible (tripling cohesion for K1 and doubling for K2) if we reduce the choice menus on top of applying lottery correlation.

Suggested Citation

  • Itai Ashlagi & Peng Shi, 2014. "Improving Community Cohesion in School Choice via Correlated-Lottery Implementation," Operations Research, INFORMS, vol. 62(6), pages 1247-1264, December.
  • Handle: RePEc:inm:oropre:v:62:y:2014:i:6:p:1247-1264
    DOI: 10.1287/opre.2014.1319
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.2014.1319
    Download Restriction: no

    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. Ehlers, Lars & Hafalir, Isa E. & Yenmez, M. Bumin & Yildirim, Muhammed A., 2014. "School choice with controlled choice constraints: Hard bounds versus soft bounds," Journal of Economic Theory, Elsevier, vol. 153(C), pages 648-683.
    3. Echenique, Federico & Yenmez, M. Bumin, 2007. "A solution to matching with preferences over colleagues," Games and Economic Behavior, Elsevier, vol. 59(1), pages 46-71, April.
    4. Parag A. Pathak, 2011. "The Mechanism Design Approach to Student Assignment," Annual Review of Economics, Annual Reviews, vol. 3(1), pages 513-536, September.
    5. Klaus, Bettina & Klijn, Flip, 2005. "Stable matchings and preferences of couples," Journal of Economic Theory, Elsevier, vol. 121(1), pages 75-106, March.
    6. Mavridou, T. & Pardalos, P.M. & Pitsoulis, L.S. & Resende, Mauricio G.C., 1998. "A GRASP for the biquadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 105(3), pages 613-621, March.
    7. Bettina Klaus & Flip Klijn & Toshifumi Nakamura, 2005. "Corrigendum: Stable Matchings and Preferences of Couples," Working Papers 261, Barcelona Graduate School of Economics.
    8. Federico Echenique & M. Bumin Yenmez, 2015. "How to Control Controlled School Choice," American Economic Review, American Economic Association, vol. 105(8), pages 2679-2694, August.
    9. Mariagiovanna Baccara & Ayse Imrohoroglu & Alistair J. Wilson & Leeat Yariv, 2012. "A Field Study on Matching with Network Externalities," American Economic Review, American Economic Association, vol. 102(5), pages 1773-1804, August.
    10. Aytek Erdil & Haluk Ergin, 2008. "What's the Matter with Tie-Breaking? Improving Efficiency in School Choice," American Economic Review, American Economic Association, vol. 98(3), pages 669-689, June.
    11. Pathak, Parag A. & Sethuraman, Jay, 2011. "Lotteries in student assignment: An equivalence result," Theoretical Economics, Econometric Society, vol. 6(1), January.
    12. Atila Abdulkadiroglu & Parag A. Pathak & Alvin E. Roth & Tayfun Sönmez, 2006. "Changing the Boston School Choice Mechanism," Levine's Bibliography 122247000000001022, UCLA Department of Economics.
    13. Atila Abdulkadiroglu & Parag A. Pathak & Alvin E. Roth & Tayfun Sönmez, 2006. "Changing the Boston School Choice Mechanism," Boston College Working Papers in Economics 639, Boston College Department of Economics.
    14. repec:eee:mateco:v:83:y:2019:i:c:p:101-109 is not listed on IDEAS
    15. Victor Lavy & Edith Sand, 2012. "The Friends Factor: How Students' Social Networks Affect Their Academic Achievement and Well-Being?," NBER Working Papers 18430, National Bureau of Economic Research, Inc.
    16. 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.
    17. Scott Duke Kominers & Tayfun Sönmez, 2012. "Designing for Diversity: Matching with Slot-Specific Priorities," Boston College Working Papers in Economics 806, Boston College Department of Economics.
    18. Eric Budish & Yeon-Koo Che & Fuhito Kojima & Paul Milgrom, 2013. "Designing Random Allocation Mechanisms: Theory and Applications," American Economic Review, American Economic Association, vol. 103(2), pages 585-623, April.
    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. repec:spr:annopr:v:275:y:2019:i:1:d:10.1007_s10479-017-2710-1 is not listed on IDEAS
    2. repec:eee:gamebe:v:110:y:2018:i:c:p:71-89 is not listed on IDEAS
    3. Itai Ashlagi & Peng Shi, 2016. "Optimal Allocation Without Money: An Engineering Approach," Management Science, INFORMS, vol. 62(4), pages 1078-1097, April.
    4. repec:eee:mateco:v:83:y:2019:i:c:p:101-109 is not listed on IDEAS
    5. repec:eee:gamebe:v:115:y:2019:i:c:p:167-187 is not listed on IDEAS

    More about this item

    Keywords

    market design; matchings; school choice;

    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:inm:oropre:v:62:y:2014:i:6:p:1247-1264. 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: (Matthew Walls). General contact details of provider: http://edirc.repec.org/data/inforea.html .

    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.