[go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Proportionally Fair Matching with Multiple Groups

  • Conference paper
  • First Online:
Graph-Theoretic Concepts in Computer Science (WG 2023)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14093))

Included in the following conference series:

  • 409 Accesses

Abstract

We study matching problems with the notion of proportional fairness. Proportional fairness is one of the most popular notions of group fairness where every group is represented up to an extent proportional to the final selection size. Matching with proportional fairness or more commonly, proportionally fair matching, was introduced in [Chierichetti et al., AISTATS, 2019]. In this problem, we are given a graph G whose edges are colored with colors from a set C. The task is for given \(0\le \alpha \le \beta \le 1\), to find a maximum \((\alpha ,\beta )\)-balanced matching M in G, that is a matching where for every color \(c\in C\) the number of edges in M of color c is between \(\alpha |M|\) and \(\beta |M|\). Chierichetti et al. initiated the study of this problem with two colors and in the context of bipartite graphs only. However, in many practical applications, the number of colors—although often a small constant—is larger than two. In this work, we make the first step towards understanding the computational complexity of proportionally fair matching with more than two colors. We design exact and approximation algorithms achieving reasonable guarantees on the quality of the matching as well as on the time complexity, and our algorithms work in general graphs. Our algorithms are also supported by suitable hardness bounds.

Most of this work was done when all four authors were affiliated with the University of Bergen, Norway. The research leading to these results has received funding from the Research Council of Norway via the project BWCA (grant no. 314528), and the European Research Council (ERC) via grant LOPPRE, reference 819416.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 59.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 79.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Ahmadi, S., Ahmed, F., Dickerson, J.P., Fuge, M., Khuller, S.: An algorithm for multi-attribute diverse matching. In: Bessiere, C. (ed.) Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pp. 3–9. ijcai.org (2020)

    Google Scholar 

  2. Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM (JACM) 42(4), 844–856 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bandyapadhyay, S., Fomin, F.V., Inamdar, T., Simonov, K.: Proportionally fair matching with multiple groups. CoRR abs/2301.03862 (2023). https://doi.org/10.48550/arXiv.2301.03862

  4. Bei, X., Liu, S., Poon, C.K., Wang, H.: Candidate selections with proportional fairness constraints. In: Seghrouchni, A.E.F., Sukthankar, G., An, B., Yorke-Smith, N. (eds.) Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020, Auckland, New Zealand, 9–13 May 2020, pp. 150–158. International Foundation for Autonomous Agents and Multiagent Systems (2020). https://doi.org/10.5555/3398761.3398784, https://dl.acm.org/doi/10.5555/3398761.3398784

  5. Benedek, M., Biró, P., Kern, W., Paulusma, D.: Computing balanced solutions for large international kidney exchange schemes. In: Faliszewski, P., Mascardi, V., Pelachaud, C., Taylor, M.E. (eds.) 21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022, Auckland, New Zealand, 9–13 May 2022, pp. 82–90. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS) (2022). https://doi.org/10.5555/3535850.3535861, https://www.ifaamas.org/Proceedings/aamas2022/pdfs/p82.pdf

  6. Berger, A., Bonifaci, V., Grandoni, F., Schäfer, G.: Budgeted matching and budgeted matroid intersection via the gasoline puzzle. Math. Program. 128(1–2), 355–372 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  7. Boehmer, N., Koana, T.: The complexity of finding fair many-to-one matchings. In: Bojanczyk, M., Merelli, E., Woodruff, D.P. (eds.) 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, 4–8 July 2022, Paris, France. LIPIcs, vol. 229, pp. 27:1–27:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022). https://doi.org/10.4230/LIPIcs.ICALP.2022.27

  8. Charlin, L., Zemel, R.: The toronto paper matching system: an automated paper-reviewer assignment system (2013)

    Google Scholar 

  9. Chierichetti, F., Kumar, R., Lattanzi, S., Vassilvitskii, S.: Fair clustering through fairlets. In: Advances in Neural Information Processing Systems, pp. 5029–5037 (2017)

    Google Scholar 

  10. Chierichetti, F., Kumar, R., Lattanzi, S., Vassilvitskii, S.: Matroids, matchings, and fairness. In: Chaudhuri, K., Sugiyama, M. (eds.) The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16–18 April 2019, Naha, Okinawa, Japan. Proceedings of Machine Learning Research, vol. 89, pp. 2212–2220. PMLR (2019)

    Google Scholar 

  11. Chouldechova, A.: Fair prediction with disparate impact: a study of bias in recidivism prediction instruments. Big Data 5(2), 153–163 (2017)

    Article  Google Scholar 

  12. Corbett-Davies, S., Pierson, E., Feller, A., Goel, S., Huq, A.: Algorithmic decision making and the cost of fairness. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Halifax, NS, Canada, 13–17 August 2017, pp. 797–806. ACM (2017)

    Google Scholar 

  13. Cygan, M., Marx, D., Pilipczuk, M., Pilipczuk, M.: Hitting forbidden subgraphs in graphs of bounded treewidth. Inf. Comput. 256, 62–82 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  14. Czabarka, E., Szekely, L.A., Toroczkai, Z., Walker, S.: An algebraic monte-carlo algorithm for the bipartite partition adjacency matrix realization problem. arXiv preprint arXiv:1708.08242 (2017)

  15. Dwork, C., Hardt, M., Pitassi, T., Reingold, O., Zemel, R.: Fairness through awareness. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pp. 214–226 (2012)

    Google Scholar 

  16. Dwork, C., Ilvento, C.: Group fairness under composition. In: Proceedings of the 2018 Conference on Fairness, Accountability, and Transparency (FAT* 2018) (2018)

    Google Scholar 

  17. Ebadian, S., Kahng, A., Peters, D., Shah, N.: Optimized distortion and proportional fairness in voting. In: Proceedings of the 23rd ACM Conference on Economics and Computation, pp. 563–600 (2022)

    Google Scholar 

  18. Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17(3), 449–467 (1965)

    Article  MathSciNet  MATH  Google Scholar 

  19. Feldman, M., Friedler, S.A., Moeller, J., Scheidegger, C., Venkatasubramanian, S.: Certifying and removing disparate impact. In: proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 259–268 (2015)

    Google Scholar 

  20. Freeman, R., Micha, E., Shah, N.: Two-sided matching meets fair division. In: Zhou, Z. (ed.) Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19–27 August 2021, pp. 203–209. ijcai.org (2021). https://doi.org/10.24963/ijcai.2021/29

  21. García-Soriano, D., Bonchi, F.: Fair-by-design matching. Data Min. Knowl. Disc. 34(5), 1291–1335 (2020). https://doi.org/10.1007/s10618-020-00675-y

    Article  MathSciNet  MATH  Google Scholar 

  22. Goel, N., Yaghini, M., Faltings, B.: Non-discriminatory machine learning through convex fairness criteria. In: Furman, J., Marchant, G.E., Price, H., Rossi, F. (eds.) Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, AIES 2018, New Orleans, LA, USA, 02–03 February 2018, p. 116. ACM (2018). https://doi.org/10.1145/3278721.3278722

  23. Gupta, S., Roy, S., Saurabh, S., Zehavi, M.: Parameterized algorithms and kernels for rainbow matching. Algorithmica 81(4), 1684–1698 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  24. Hall, P.: On representatives of subsets. J. London Math. Soc. 10, 26–30 (1935)

    Article  MathSciNet  MATH  Google Scholar 

  25. Hopcroft, J.E., Karp, R.M.: An \(n^{5/2}\) algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2, 225–231 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  26. Huang, C., Kavitha, T., Mehlhorn, K., Michail, D.: Fair matchings and related problems. Algorithmica 74(3), 1184–1203 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  27. Impagliazzo, R., Paturi, R.: On the complexity of k-sat. J. Comput. Syst. Sci. 62(2), 367–375 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  28. Kamada, Y., Kojima, F.: Fair matching under constraints: theory and applications (2020)

    Google Scholar 

  29. Kamishima, T., Akaho, S., Sakuma, J.: Fairness-aware learning through regularization approach. In: Spiliopoulou, M., et al. (eds.) Data Mining Workshops (ICDMW), 2011 IEEE 11th International Conference on, Vancouver, BC, Canada, 11 December 2011, pp. 643–650. IEEE Computer Society (2011)

    Google Scholar 

  30. Kesavan, D., Periyathambi, E., Chokkalingam, A.: A proportional fair scheduling strategy using multiobjective gradient-based African buffalo optimization algorithm for effective resource allocation and interference minimization. Int. J. Commun Syst 35(1), e5003 (2022)

    Article  Google Scholar 

  31. Klaus, B., Klijn, F.: Procedurally fair and stable matching. Econ. Theory 27(2), 431–447 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  32. Kleinberg, J., Mullainathan, S., Raghavan, M.: Inherent trade-offs in the fair determination of risk scores. In: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017)

    Google Scholar 

  33. Kőnig, D.: Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Math. Ann. 77(4), 453–465 (1916)

    Article  MathSciNet  MATH  Google Scholar 

  34. Kurata, R., Hamada, N., Iwasaki, A., Yokoo, M.: Controlled school choice with soft bounds and overlapping types. J. Artif. Intell. Res. 58, 153–184 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  35. Linhares, A., Olver, N., Swamy, C., Zenklusen, R.: Approximate multi-matroid intersection via iterative refinement. Math. Program. 183(1), 397–418 (2020). https://doi.org/10.1007/s10107-020-01524-y

    Article  MathSciNet  MATH  Google Scholar 

  36. Lokshtanov, D., Misra, P., Panolan, F., Saurabh, S.: Deterministic truncation of linear matroids. ACM Trans. Algorithms 14(2), 14:1-14:20 (2018). https://doi.org/10.1145/3170444

    Article  MathSciNet  MATH  Google Scholar 

  37. Lovász, L., Plummer, M.D.: Matching Theory. AMS (2009)

    Google Scholar 

  38. Lu, Y.: The optimization of automated container terminal scheduling based on proportional fair priority. Math. Probl. Eng. 2022 (2022)

    Google Scholar 

  39. Marx, D.: A parameterized view on matroid optimization problems. Theoret. Comput. Sci. 410(44), 4471–4479 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  40. Mądry, A.: Navigating central path with electrical flows: from flows to matchings, and back. In: FOCS 2013, pp. 253–262. IEEE Computer Society (2013)

    Google Scholar 

  41. Mucha, M., Sankowski, P.: Maximum matchings via Gaussian elimination. In: FOCS 2004, pp. 248–255. IEEE Computer Society (2004)

    Google Scholar 

  42. Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In: Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS 1995), pp. 182–191. IEEE (1995)

    Google Scholar 

  43. Nguyen, M.H., Baiou, M., Nguyen, V.H., Vo, T.Q.T.: Nash fairness solutions for balanced tsp. In: 10th International Network Optimization Conference (INOC) (2022)

    Google Scholar 

  44. Rabin, M.O., Vazirani, V.V.: Maximum matchings in general graphs through randomization. J. Algorithms 10(4), 557–567 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  45. Ristoski, P., Petrovski, P., Mika, P., Paulheim, H.: A machine learning approach for product matching and categorization. Semant. web 9(5), 707–728 (2018)

    Article  Google Scholar 

  46. Roth, A.E., Sönmez, T., Ünver, M.U.: Efficient kidney exchange: coincidence of wants in markets with compatibility-based preferences. Am. Econ. Rev. 97(3), 828–851 (2007)

    Article  Google Scholar 

  47. Schrijver, A.: Combinatorial Optimization. Polyhedra and Efficiency, vol. A. Springer-Verlag, Berlin (2003)

    Google Scholar 

  48. St-Arnaud, W., Carvalho, M., Farnadi, G.: Adaptation, comparison and practical implementation of fairness schemes in kidney exchange programs. arXiv preprint arXiv:2207.00241 (2022)

  49. Stamoulis, G.: Approximation algorithms for bounded color matchings via convex decompositions. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds.) MFCS 2014. LNCS, vol. 8635, pp. 625–636. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44465-8_53

    Chapter  Google Scholar 

  50. Sun, Z., Todo, T., Walsh, T.: Fair pairwise exchange among groups. In: IJCAI, pp. 419–425 (2021)

    Google Scholar 

  51. Thanh, B.L., Ruggieri, S., Turini, F.: k-NN as an implementation of situation testing for discrimination discovery and prevention. In: Apté, C., Ghosh, J., Smyth, P. (eds.) Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA, 21–24 August 2011, pp. 502–510. ACM (2011)

    Google Scholar 

  52. Yannakakis, M.: Node- and edge-deletion np-complete problems. In: Lipton, R.J., Burkhard, W.A., Savitch, W.J., Friedman, E.P., Aho, A.V. (eds.) Proceedings of the 10th Annual ACM Symposium on Theory of Computing, 1–3 May 1978, San Diego, California, USA, pp. 253–264. ACM (1978)

    Google Scholar 

  53. Zhang, G., Malekmohammadi, S., Chen, X., Yu, Y.: Equality is not equity: Proportional fairness in federated learning. arXiv preprint arXiv:2202.01666 (2022)

Download references

Author information

Authors and Affiliations

  1. Portland State University, Portland, USA

    Sayan Bandyapadhyay

  2. University of Bergen, Bergen, Norway

    Fedor V. Fomin & Tanmay Inamdar

  3. Hasso Plattner Institute, University of Potsdam, Potsdam, Germany

    Kirill Simonov

Authors
  1. Sayan Bandyapadhyay
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Fedor V. Fomin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Tanmay Inamdar
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Kirill Simonov
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tanmay Inamdar .

Editor information

Editors and Affiliations

  1. Durham University, Durham, UK

    Daniël Paulusma

  2. University of Fribourg, Fribourg, Fribourg, Switzerland

    Bernard Ries

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Bandyapadhyay, S., Fomin, F.V., Inamdar, T., Simonov, K. (2023). Proportionally Fair Matching with Multiple Groups. In: Paulusma, D., Ries, B. (eds) Graph-Theoretic Concepts in Computer Science. WG 2023. Lecture Notes in Computer Science, vol 14093. Springer, Cham. https://doi.org/10.1007/978-3-031-43380-1_1

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-43380-1_1

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-43379-5

  • Online ISBN: 978-3-031-43380-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation