Document Open Access Logo

On Fairness and Stability in Two-Sided Matchings

Authors Gili Karni, Guy N. Rothblum, Gal Yona

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.92.pdf
  • Filesize: 0.64 MB
  • 17 pages

Document Identifiers

Author Details

Gili Karni
  • Weizmann Institute of Science, Rehovot, Israel
Guy N. Rothblum
  • Weizmann Institute of Science, Rehovot, Israel
Gal Yona
  • Weizmann Institute of Science, Rehovot, Israel

Funding

  • Karni, Gili: Research supported by the Israel Science Foundation (grant number 5219/17), and by the Simons Foundation Collaboration on the Theory of Algorithmic Fairness.
  • Rothblum, Guy N.: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 819702), from the Israel Science Foundation (grant number 5219/17), and from the Simons Foundation Collaboration on the Theory of Algorithmic Fairness.
  • Yona, Gal: Supported by the European Research Council (ERC) (grant agreement No. 819702), by the Israel Science Foundation (grant number 5219/17), by the Simons Foundation Collaboration on the Theory of Algorithmic Fairness, by the Israeli Council for Higher Education via the Weizmann Data Science Research Center, by a Google PhD fellowship, and by a grant from the Estate of Tully and Michele Plesser.

Acknowledgements

We thank Shahar Dobzinski and Moni Naor for helpful conversations and suggestions about this work and its presentation. We also thank the anonymous ITCS 2022 reviewers for their feedback.

Cite AsGet BibTex

Gili Karni, Guy N. Rothblum, and Gal Yona. On Fairness and Stability in Two-Sided Matchings. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 92:1-92:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.92

Abstract

There are growing concerns that algorithms, which increasingly make or influence important decisions pertaining to individuals, might produce outcomes that discriminate against protected groups. We study such fairness concerns in the context of a two-sided market, where there are two sets of agents, and each agent has preferences over the other set. The goal is producing a matching between the sets. Throughout this work, we use the example of matching medical residents (who we call "doctors") to hospitals. This setting has been the focus of a rich body of work. The seminal work of Gale and Shapley formulated a stability desideratum, and showed that a stable matching always exists and can be found in polynomial time. With fairness concerns in mind, it is natural to ask: might a stable matching be discriminatory towards some of the doctors? How can we obtain a fair matching? The question is interesting both when hospital preferences might be discriminatory, and also when each hospital’s preferences are fair. We study this question through the lens of metric-based fairness notions (Dwork et al. [ITCS 2012] and Kim et al. [ITCS 2020]). We formulate appropriate definitions of fairness and stability in the presence of a similarity metric, and ask: does a fair and stable matching always exist? Can such a matching be found in polynomial time? Can classical Gale-Shapley algorithms find such a matching? Our contributions are as follows: - Composition failures for classical algorithms. We show that composing the Gale-Shapley algorithm with fair hospital preferences can produce blatantly unfair outcomes. - New algorithms for finding fair and stable matchings. Our main technical contributions are efficient new algorithms for finding fair and stable matchings when: (i) the hospitals' preferences are fair, and (ii) the fairness metric satisfies a strong "proto-metric" condition: the distance between every two doctors is either zero or one. In particular, these algorithms also show that, in this setting, fairness and stability are compatible. - Barriers for finding fair and stable matchings in the general case. We show that if the hospital preferences can be unfair, or if the metric fails to satisfy the proto-metric condition, then no algorithm in a natural class can find a fair and stable matching. The natural class includes the classical Gale-Shapley algorithms and our new algorithms.

Subject Classification

ACM Subject Classification
  • Theory of computation → Theory and algorithms for application domains
Keywords
  • algorithmic fairness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Muhammad Ali, Piotr Sapiezynski, Miranda Bogen, Aleksandra Korolova, Alan Mislove, and Aaron Rieke. Discrimination through optimization: How facebook’s ad delivery can lead to biased outcomes. Proceedings of the ACM on Human-Computer Interaction, 3(CSCW):1-30, 2019. Google Scholar
  2. Solon Barocas and Andrew D Selbst. Big data’s disparate impact. Calif. L. Rev., 104:671, 2016. Google Scholar
  3. Miranda Bogen. All the ways hiring algorithms can introduce bias. Harvard Business Review, 6:2019, 2019. Google Scholar
  4. Anna Bogomolnaia and Hervé Moulin. A new solution to the random assignment problem. Journal of Economic theory, 100(2):295-328, 2001. Google Scholar
  5. Slava Bronfman, Avinatan Hassidim, Arnon Afek, Assaf Romm, Rony Shreberk, Ayal Hassidim, and Anda Massler. Assigning israeli medical graduates to internships. Israel journal of health policy research, 4(1):1-7, 2015. Google Scholar
  6. Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big data, 5(2):153-163, 2017. Google Scholar
  7. Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pages 214-226, 2012. Google Scholar
  8. Cynthia Dwork and Christina Ilvento. Fairness under composition. arXiv preprint arXiv:1806.06122, 2018. Google Scholar
  9. Cynthia Dwork, Christina Ilvento, and Meena Jagadeesan. Individual fairness in pipelines. arXiv preprint arXiv:2004.05167, 2020. Google Scholar
  10. Duncan K Foley. Resource allocation and the public sector. PhD thesis, Yale University, 1967. Google Scholar
  11. Rupert Freeman, Evi Micha, and Nisarg Shah. Two-sided matching meets fair division. arXiv preprint arXiv:2107.07404, 2021. Google Scholar
  12. David Gale and Lloyd S Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9-15, 1962. Google Scholar
  13. Ioannis Giannakopoulos, Panagiotis Karras, Dimitrios Tsoumakos, Katerina Doka, and Nectarios Koziris. An equitable solution to the stable marriage problem. In 2015 ieee 27th international conference on tools with artificial intelligence (ictai), pages 989-996. IEEE, 2015. Google Scholar
  14. Dan Gusfield and Robert W Irving. The stable marriage problem: structure and algorithms. MIT press, 1989. Google Scholar
  15. Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In Advances in neural information processing systems, pages 3315-3323, 2016. Google Scholar
  16. Robert W Irving. Stable marriage and indifference. Discrete Applied Mathematics, 48(3):261-272, 1994. Google Scholar
  17. Michael P Kim, Aleksandra Korolova, Guy N Rothblum, and Gal Yona. Preference-informed fairness. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  18. S Kiselgof. Matchings with interval order preferences: efficiency vs strategy-proofness. Procedia Computer Science, 31:807-813, 2014. Google Scholar
  19. Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs in the fair determination of risk scores. arXiv preprint arXiv:1609.05807, 2016. Google Scholar
  20. Donald Ervin Knuth. Stable marriage and its relation to other combinatorial problems: An introduction to the mathematical analysis of algorithms, volume 10. American Mathematical Soc., 1997. Google Scholar
  21. Ziad Obermeyer, Brian Powers, Christine Vogeli, and Sendhil Mullainathan. Dissecting racial bias in an algorithm used to manage the health of populations. Science, 366(6464):447-453, 2019. Google Scholar
  22. Cathy O'neil. Weapons of math destruction: How big data increases inequality and threatens democracy. Crown, 2016. Google Scholar
  23. Alvin Rajkomar, Michaela Hardt, Michael D Howell, Greg Corrado, and Marshall H Chin. Ensuring fairness in machine learning to advance health equity. Annals of internal medicine, 169(12):866-872, 2018. Google Scholar
  24. Alvin E Roth. The evolution of the labor market for medical interns and residents: a case study in game theory. Journal of political Economy, 92(6):991-1016, 1984. Google Scholar
  25. Alvin E Roth. On the allocation of residents to rural hospitals: a general property of two-sided matching markets. Econometrica: Journal of the Econometric Society, pages 425-427, 1986. Google Scholar
  26. Alvin E Roth and Marilda Sotomayor. Two-sided matching. Handbook of game theory with economic applications, 1:485-541, 1992. Google Scholar
  27. Tom Sühr, Asia J Biega, Meike Zehlike, Krishna P Gummadi, and Abhijnan Chakraborty. Two-sided fairness for repeated matchings in two-sided markets: A case study of a ride-hailing platform. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 3082-3092, 2019. Google Scholar
  28. Edward G Thurber. Concerning the maximum number of stable matchings in the stable marriage problem. Discrete Mathematics, 248(1-3):195-219, 2002. Google Scholar
  29. Ariana Tobin. Hud sues facebook over housing discrimination and says the company’s algorithms have made the problem worse. ProPublica (March 28, 2019). Available at https://www. propublica. org/article/hud-sues-facebook-housing-discrimination-advertising-algorithms (last accessed April 29, 2019), 2019. Google Scholar
  30. Hal Varian. Efficiency, equity and envy. Journal of Economic Theory, 9:63-91, 1974. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact