Candidate selections with proportional fairness constraints | Autonomous Agents and Multi-Agent Systems Skip to main content
Springer Nature Link
Log in

Candidate selections with proportional fairness constraints

  • Published:
Autonomous Agents and Multi-Agent Systems Aims and scope Submit manuscript

Abstract

Selecting a subset of candidates with various attributes under fairness constraints has been attracting considerable attention from the AI community, with applications ranging from school admissions to committee selections. The fairness constraints are usually captured by absolute upper bounds and/or lower bounds on the number of selected candidates in specific attributes. In many scenarios, however, the total number of selected candidates is not predetermined. It is, therefore, more natural to express these fairness constraints in terms of proportions of the final selection size. In this paper, we study the proportional candidate selection problem, where the goal is to select a subset of candidates with maximum cardinality while meeting certain proportional fairness constraints. We first analyze the computational complexity of the problem and show strong inapproximability results. Next, we investigate the algorithmic aspects of the problem in two directions. First, by treating the proportional fairness constraints as soft constraints, we devise two polynomial-time algorithms that could return (near) optimal solutions with bounded violations on each fairness constraint. Second, we design an exact algorithm with a fast running time in practice. Simulations based on both synthetic and publicly available data confirm the effectiveness and efficiency of our proposed algorithms.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. https://diversity.berkeley.edu/reports-data/diversity-data-dashboard.

  2. https://internationaloffice.berkeley.edu/sites/default/files/student-stats2018.pdf.

  3. A sequence of vectors \((\varvec{v_1} , \varvec{v_2}, \ldots ,\varvec{v_k})\) is said to be linearly independent if the equation \(a_1\varvec{v_1} + a_2\varvec{v_2} + \ldots +a_k\varvec{v_k} = 0\) can only be satisfied by \(a_i=0\) for \(i=1, \ldots , k\).

  4. A sequence of vectors \((\varvec{v_1} , \varvec{v_2}, \ldots ,\varvec{v_k})\) is said to be linearly dependent if there exits \(a_1,a_2, \ldots , a_k\), not all zero, such that \(a_1\varvec{v_1} + a_2\varvec{v_2} + \ldots +a_k\varvec{v_k} = 0\).

  5. A similar argument is detailed in the proof of Lemma 4.

  6. The notion \(\widetilde{O}\) is used to hide \(\log ^{O(1)}(n)\) factor.

  7. The notion \(O^*\) is used to hide \(n^{o(1)}\) and \(\log ^{O(1)}(1/\delta )\) factors where \(\delta\) is the relative accuracy.

References

  1. Abdulkadiroğlu, A. (2005). College admissions with affirmative action. International Journal of Game Theory, 33(4), 535–549.

    Article  MathSciNet  Google Scholar 

  2. Ashlagi, I., Saberi, A., & Shameli, A. (2019). Assignment mechanisms under distributional constraints. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), (pp. 229–240)

  3. Aziz, H. (2019). A rule for committee selection with soft diversity constraints. Group Decision and Negotiation, 28(6), 1193–1200.

    Article  Google Scholar 

  4. Aziz, H., Gaspers, S., Sun, Z., & Walsh, T. (2019). From matching with diversity constraints to matching with regional quotas. In: Proceedings of the International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), (pp. 377–385)

  5. Bei, X., Liu, S., Poon, C. K., & Wang, H. (2020). Candidate selections with proportional fairness constraints. In: Proceedings of the International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), (pp. 150–158)

  6. Bei, X., Li, Z., Liu, J., Liu, S., & Lu, X. (2021). Fair division of mixed divisible and indivisible goods. Artificial Intelligence, 293, 103436.

    Article  MathSciNet  Google Scholar 

  7. Benabbou, N., Chakraborty, M., Ho, X. V., Sliwinski, J., & Zick, Y. (2018). Diversity constraints in public housing allocation. In: Proceedings of the International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), (pp. 973–981)

  8. Biró, P., Fleiner, T., Irving, R. W., & Manlove, D. F. (2010). The college admissions problem with lower and common quotas. Theoretical Computer Science, 411(34), 3136–3153.

    Article  MathSciNet  Google Scholar 

  9. Bredereck, R., Faliszewski, P., Igarashi, A., Lackner, M., & Skowron, P. (2018). Multiwinner elections with diversity constraints. In: Proceedings of the AAAI Conference on Artificial Intelligence (AAAI) (pp. 933–940)

  10. Budish, E. (2011). The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6), 1061–1103.

    Article  Google Scholar 

  11. Calinescu, G., Chekuri, C., Pál, M., & Vondrák, J. (2011). Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing, 40(6), 1740–1766.

    Article  MathSciNet  Google Scholar 

  12. Celis, L. E., Huang, L., & Vishnoi, N. K. (2018). Multiwinner voting with fairness constraints. In: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), (pp. 144–151)

  13. Chen, J., Ganian, R., & Hamm, T. (2021). Stable matchings with diversity constraints: Affirmative action is beyond NP. In: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), (pp. 146–152)

  14. Cowen Institue (2011) Case studies of school choice and open enrollment in four cities

  15. Ehlers, L., Hafalir, I. E., Yenmez, M. B., & Yildirim, M. A. (2014). School choice with controlled choice constraints: Hard bounds versus soft bounds. Journal of Economic Theory, 153 (C):648–683,

  16. Faliszewski P, Skowron P, Slinko A, & Talmon N (2017) Multiwinner voting: A new challenge for social choice theory. In: Endriss U (ed) Trends in Computational Social Choice, AI Access Foundation, chap 2

  17. Faliszewski, P., Slinko, A., & Talmon, N. (2020). Multiwinner rules with variable number of winners. In: Proceedings of the European Conference on Artificial Intelligence (ECAI), (pp. 67–74)

  18. Fragiadakis, D., & Troyan, P. (2017). Improving matching under hard distributional constraints. Theoretical Economics, 12(2), 863–908.

    Article  MathSciNet  Google Scholar 

  19. Hafalir, I. E., Yenmez, M. B., & Yildirim, M. A. (2013). Effective affirmative action in school choice. Theoretical Economics, 8(2), 325–363.

    Article  MathSciNet  Google Scholar 

  20. Jiang, S., Song, Z., Weinstein, O., & Zhang, H. (2021). A faster algorithm for solving general LPs. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), (pp. 823–832)

  21. Karp, R. M. (1972). Reducibility among combinatorial problems. In: Proceedings of a symposium on the Complexity of Computer Computations, In: Proceedings of a symposium on the Complexity of Computer Computations, (pp. 85–103)

  22. Kilgour, D. M. (2016). Approval elections with a variable number of winners. Theory and Decision, 81(2), 199–211.

    Article  MathSciNet  Google Scholar 

  23. Király, T., Lau, L. C., & Singh, M. (2012). Degree bounded matroids and submodular flows. Combinatorica, 32(6), 703–720.

    Article  MathSciNet  Google Scholar 

  24. Kojima, F., Tamura, A., & Yokoo, M. (2018). Designing matching mechanisms under constraints: An approach from discrete convex analysis. Journal of Economic Theory, 176, 803–833.

    Article  MathSciNet  Google Scholar 

  25. Kurata, R., Hamada, N., Iwasaki, A., & Makoto, Y. (2017). Controlled school choice with soft bounds and overlapping types. Journal of Artificial Intelligent Research, 58, 153–184.

    Article  MathSciNet  Google Scholar 

  26. Lang, J., & Skowron, P. (2018). Multi-attribute proportional representation. Artificial Intelligence, 263, 74–106.

    Article  MathSciNet  Google Scholar 

  27. Lau, L. C., Ravi, R., & Singh, M. (2011). Iterative Methods in Combinatorial Optimization (1st ed.). London: Cambridge University Press.

    Book  Google Scholar 

  28. Nguyen, T., & Vohra, R. (2019). Stable matching with proportionality constraints. Operations Research, 67(6), 1503–1519.

    Article  MathSciNet  Google Scholar 

  29. Steinhaus, H. (1948). The problem of fair division. Econometrica, 16(1), 101–104.

    Google Scholar 

  30. Suzuki, T., Tamura, A., & Yokoo, M. (2018). Efficient allocation mechanism with endowments and distributional constraints. In: Proceedings of the International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), (pp. 50–58)

  31. Yang, Y., & Wang, J. (2018). Multiwinner voting with restricted admissible sets: Complexity and strategyproofness. In: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), (pp. 576–582)

Download references

Acknowledgements

This work was supported in part by the Ministry of Education, Singapore, under its Academic Research Fund Tier 2 (MOE2019-T2-1-045), the National Natural Science Foundation of China under Grant 62102117, and the Deep Learning and Cognitive Computing Centre in The Hang Seng University of Hong Kong.

Author information

Authors and Affiliations

  1. School of Physical and Mathmatical Sciences, Nanyang Technological University, Singapore, Singapore

    Xiaohui Bei & Hongao Wang

  2. School of Computer Science and Technology, Harbin Institute of Technology (Shenzhen), Shenzhen, China

    Shengxin Liu

  3. Department of Computing, The Hang Seng University of Hong Kong, Hong Kong, China

    Chung Keung Poon

Authors
  1. Xiaohui Bei
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shengxin Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Chung Keung Poon
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Hongao Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Shengxin Liu.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

A preliminary version of this paper was presented at the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS) 2020 [5].

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bei, X., Liu, S., Poon, C.K. et al. Candidate selections with proportional fairness constraints. Auton Agent Multi-Agent Syst 36, 5 (2022). https://doi.org/10.1007/s10458-021-09533-7

Download citation

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10458-021-09533-7

Keywords

Search

Navigation