Document Open Access Logo

The Complexity of Finding Fair Many-To-One Matchings

Authors Niclas Boehmer , Tomohiro Koana

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.27.pdf
  • Filesize: 0.83 MB
  • 18 pages

Document Identifiers

Author Details

Niclas Boehmer
  • Algorithmics and Computational Complexity, Technische Universität Berlin, Germany
Tomohiro Koana
  • Algorithmics and Computational Complexity, Technische Universität Berlin, Germany

Funding

  • Boehmer, Niclas: Supported by the Deutsche Forschungsgemeinschaft (DFG) projects MaMu (NI 369/19) and ComSoc-MPMS (NI 369/22).
  • Koana, Tomohiro: Supported by the Deutsche Forschungsgemeinschaft (DFG) project DiPa (NI 369/21).

Acknowledgements

We are grateful to the anonymous ICALP 2022 reviewers for their thoughtful, constructive, and helpful comments.

Cite As Get BibTex

Niclas Boehmer and Tomohiro Koana. The Complexity of Finding Fair Many-To-One Matchings. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 27:1-27:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ICALP.2022.27

Abstract

We analyze the (parameterized) computational complexity of "fair" variants of bipartite many-to-one matching, where each vertex from the "left" side is matched to exactly one vertex and each vertex from the "right" side may be matched to multiple vertices. We want to find a "fair" matching, in which each vertex from the right side is matched to a "fair" set of vertices. Assuming that each vertex from the left side has one color modeling its attribute, we study two fairness criteria. In one of them, we deem a vertex set fair if for any two colors, the difference between the numbers of their occurrences does not exceed a given threshold. Fairness is relevant when finding many-to-one matchings between students and colleges, voters and constituencies, and applicants and firms. Here colors may model sociodemographic attributes, party memberships, and qualifications, respectively.
We show that finding a fair many-to-one matching is NP-hard even for three colors and maximum degree five. Our main contribution is the design of fixed-parameter tractable algorithms with respect to the number of vertices on the right side. Our algorithms make use of a variety of techniques including color coding. At the core lie integer linear programs encoding Hall like conditions. To establish the correctness of our integer programs, we prove a new separation result, inspired by Frank’s separation theorem [Frank, Discrete Math. 1982], which may also be of independent interest. We further obtain complete complexity dichotomies regarding the number of colors and the maximum degree of each side.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Graph theory
  • polynomial-time algorithms
  • NP-hardness
  • FPT
  • ILP
  • color coding
  • submodular and supermodular functions
  • algorithmic fairness

Metrics

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

Related Versions

References

  1. Saba Ahmadi, Faez Ahmed, John P. Dickerson, Mark Fuge, and Samir Khuller. An algorithm for multi-attribute diverse matching. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI '20), pages 3-9. ijcai.org, 2020. Google Scholar
  2. Sara Ahmadian, Alessandro Epasto, Ravi Kumar, and Mohammad Mahdian. Fair correlation clustering. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS '20), pages 4195-4205. PMLR, 2020. Google Scholar
  3. Faez Ahmed, John Dickerson, and Mark Fuge. Forming diverse teams from sequentially arriving people. J. Mech. Design, 142(11):111401, 2020. Google Scholar
  4. Faez Ahmed, John P. Dickerson, and Mark Fuge. Diverse weighted bipartite b-matching. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI '17), pages 35-41. ijcai.org, 2017. Google Scholar
  5. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844-856, 1995. URL: https://doi.org/10.1145/210332.210337.
  6. Abolfazl Asudeh, Tanya Y. Berger-Wolf, Bhaskar DasGupta, and Anastasios Sidiropoulos. Maximizing coverage while ensuring fairness: a tale of conflicting objective. CoRR, abs/2007.08069, 2020. URL: http://arxiv.org/abs/2007.08069.
  7. Haris Aziz, Serge Gaspers, Zhaohong Sun, and Toby Walsh. From matching with diversity constraints to matching with regional quotas. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS '19), pages 377-385. IFAAMAS, 2019. Google Scholar
  8. Inacio Bo. Fair implementation of diversity in school choice. Games Econ. Behav., 97:54-63, 2016. Google Scholar
  9. Niclas Boehmer, Tomohiro Koana, and Rolf Niedermeier. A refined complexity analysis of fair districting over graphs. CoRR, abs/2102.11864, 2021. Accepted as an extended abstract at AAMAS '22. URL: http://arxiv.org/abs/2102.11864.
  10. Jiehua Chen, Robert Ganian, and Thekla Hamm. Stable matchings with diversity constraints: Affirmative action is beyond NP. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI '20), pages 146-152. ijcai.org, 2020. Google Scholar
  11. Gérard Cornuéjols. General factors of graphs. J. Comb. Theory, Ser. B, 45(2):185-198, 1988. URL: https://doi.org/10.1016/0095-8956(88)90068-8.
  12. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  13. John P. Dickerson, Karthik Abinav Sankararaman, Aravind Srinivasan, and Pan Xu. Balancing relevance and diversity in online bipartite matching via submodularity. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI '19), pages 1877-1884. AAAI Press, 2019. Google Scholar
  14. András Frank. An algorithm for submodular functions on graphs. Discrete Math., 16:97-120, 1982. Google Scholar
  15. Zachary Friggstad and Ramin Mousavi. Fair correlation clustering with global and local guarantees. In Proceedings of the 17th International Symposium on Algorithms and Data Structures (WADS '21), pages 414-427. Springer, 2021. Google Scholar
  16. Isa E Hafalir, M Bumin Yenmez, and Muhammed A Yildirim. Effective affirmative action in school choice. Theor. Econ., 8(2):325-363, 2013. Google Scholar
  17. Philip Hall. On representatives of subsets. Classic Papers in Combinatorics, pages 58-62, 1987. Google Scholar
  18. Chien-Chung Huang. Classified stable matching. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10), pages 1235-1253. SIAM, 2010. Google Scholar
  19. Ravi Kannan. Minkowski’s convex body theorem and integer programming. Math. Oper. Res., 12(3):415-440, 1987. Google Scholar
  20. Hendrik W. Lenstra. Integer programming with a fixed number of variables. Math. Oper. Res., 8:538-548, 1983. Google Scholar
  21. Thành Nguyen and Rakesh Vohra. Stable matching with proportionality constraints. Oper. Res., 67(6):1503-1519, 2019. Google Scholar
  22. Deval Patel, Arindam Khan, and Anand Louis. Group fairness for knapsack problems. In Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS '21), pages 1001-1009. ACM, 2021. Google Scholar
  23. Dana Pessach and Erez Shmueli. Algorithmic fairness. CoRR, abs/2001.09784, 2020. URL: http://arxiv.org/abs/2001.09784.
  24. Ana-Andreea Stoica, Abhijnan Chakraborty, Palash Dey, and Krishna P. Gummadi. Minimizing margin of victory for fair political and educational districting. In Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS '20), pages 1305-1313. IFAAMAS, 2020. 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 About DROPS Imprint Privacy Contact