Proceedings

Mechanism Design for School Choice with Soft Diversity Constraints

Video Download BibTeX Cite

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. Main track. Pages 153-159.

https://doi.org/10.24963/ijcai.2020/22

© 2020 International Joint Conferences on Artificial Intelligence

Abstract

We study the controlled school choice problem where students may belong to overlapping types and schools have soft target quotas for each type. We formalize fairness concepts for the setting that extend fairness concepts considered for restricted settings without overlapping types. Our central contribution is presenting a new class of algorithms that takes into account the representations of combinations of student types. The algorithms return matchings that are non-wasteful and satisfy fairness for same types. We further prove that the algorithms are strategyproof for the students and yield a fair outcome with respect to the induced quotas for type combinations. We experimentally compare our algorithms with two existing approaches in terms of achieving diversity goals and satisfying fairness.

  1. [Abdulkadiroglu and Sönmez, 2003] Atila Abdulkadiroglu and Tayfun Sönmez. School choice: A mechanism de- sign approach. American Economic Review, 93(3):729- 747, 2003.
  2. [Ahmed et al., 2017] Faez Ahmed, John P. Dickerson, and Mark Fuge. Diverse weighted bipartite b-matching. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, pages 35-41. AAAI Press, 2017. IJCAI
  3. [Aygün and Turhan, 2016] Orhan Aygün and Bertan Turhan. Dynamic reserves in matching markets: Theory and appli- cations. 2016.
  4. [Aziz et al., 2019] Haris Aziz, Serge Gaspers, Zhaohong Sun, and Toby Walsh. From matching with diversity con- straints to matching with regional quotas. In Proceed- ings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pages 377-385, 2019.
  5. [Baswana et al., 2019] Surender Baswana, Partha Pratim Chakrabarti, Sharat Chandran, Yashodhan Kanoria, and Utkarsh Patange. Centralized admissions for engineering colleges in india. In Proceedings of the 20th ACM Con- ference on Economics and Computation, pages 323-324, 2019.
  6. [Dickerson et al., 2019] John P. Dickerson, Karthik Abinav Sankararaman, Aravind Srinivasan, and Pan Xu. Balanc- ing relevance and diversity in online bipartite matching via submodularity. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1877-1884, 2019.
  7. [Echenique and Yenmez, 2015] Federico Echenique and M Bumin Yenmez. How to control controlled school choice. American Economic Review, 105(8):2679-94, August 2015.
  8. [Ehlers et al., 2014] Lars Ehlers, Isa E. Hafalir, M Bumin Yenmez, and Muhammed A. Yildirim. School choice with controlled choice constraints: Hard bounds versus soft bounds. Journal of Economic Theory, 153:648-683, 2014.
  9. [Gonczarowski et al., 2019] Yannai A. Gonczarowski, Lior Kovalio, Noam Nisan, and Assaf Romm. Matching for the Israeli "Mechinot" gap year: Handling rich diversity re- quirements. In Proceedings of the 20th ACM Conference on Economics and Computation, pages 321-321, 2019.
  10. [Hafalir et al., 2013] Isa E. Hafalir, M. Bumin Yenmez, and Muhammed A. Yildirim. Effective affirmative action in school choice. Theoretical Economics, 8(2):325-363, 2013.
  11. [Hatfield and Milgrom, 2005] John William Hatfield and Paul R. Milgrom. Matching with contracts. American Eco- nomic Review, 95(4):913-935, 2005.
  12. [Kearns et al., 2018] Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing fairness gerry- mandering: Auditing and learning for subgroup fairness. In Proceedings of the 35th International Conference on Machine Learning, pages 2569-2577, 2018.
  13. [Kojima, 2012] Fuhito Kojima. School choice: Impossibili- ties for affirmative action. Games and Economic Behavior, 75(2):685-693, 2012.
  14. [Kominers and Sönmez, 2013] Scott Duke Kominers and Tayfun Sönmez. Designing for diversity in matching. In Proceedings of the fourteenth ACM Conference on Elec- tronic Commerce, pages 603-604, 2013.
  15. [Kominers and Sönmez, 2016] Scott Duke Kominers and Tayfun Sönmez. Matching with slot-specific priorities: Theory. Theoretical Economics, 11(2):683-710, 2016.
  16. [Kurata et al., 2015] Ryoji Kurata, Naoto Hamada, Atsushi Iwasaki, and Makoto Yokoo. Controlled school choice with soft bounds and overlapping types. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelli- gence, pages 951-957, 2015.
  17. [Kurata et al., 2017] Ryoji Kurata, Naoto Hamada, Atsushi Iwasaki, and Makoto Yokoo. Controlled school choice with soft bounds and overlapping types. Journal of Ar- tificial Intelligence Research, 58:153-184, 2017.
  18. [Lu and Boutilier, 2011] Tyler Lu and Craig Boutilier. Learning Mallows models with pairwise preferences. In Proceedings of the 28th International Conference on Ma- chine Learning (ICML-11), pages 145-152, 2011.
  19. [Roth and Sotomayor, 1990] Alvin E. Roth and Marilda A. Oliveira Sotomayor. Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Cambridge Uni- versity Press, 1990.
  20. [Sönmez et al., 2019] Tayfun Sönmez, M Bumin Yenmez, et al. Constitutional implementation of vertical and hori- zontal reservations in India: A unified mechanism for civil service allocation and college admissions. 2019.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards