Document Open Access Logo

Leximax Approximations and Representative Cohort Selection

Authors Monika Henzinger , Charlotte Peale , Omer Reingold , Judy Hanwen Shen

PDF
Thumbnail PDF

File

LIPIcs.FORC.2022.2.pdf
  • Filesize: 0.83 MB
  • 22 pages

Document Identifiers

Author Details

Monika Henzinger
  • Universität Wien, Austria
Charlotte Peale
  • Stanford University, CA, USA
Omer Reingold
  • Stanford University, CA, USA
Judy Hanwen Shen
  • Stanford University, CA, USA

Funding

  • Henzinger, Monika: This work was done in part as Stanford University Distinguished Visiting Austrian Chair. 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. 101019564 "The Design of Modern Fully Dynamic Data Structures (MoDynStruct)" and from the Austrian Science Fund (FWF) project "Fast Algorithms for a Reactive Network Layer (ReactNet)", P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020-2024.
  • Peale, Charlotte: Supported by the Simons Foundation Collaboration on the Theory of Algorithmic Fairness.
  • Reingold, Omer: Supported by the Simons Foundation Collaboration on the Theory of Algorithmic Fairness, the Sloan Foundation Grant 2020-13941 and the Simons Foundation investigators award 689988.
  • Shen, Judy Hanwen: Supported by the Simons Foundation Collaboration on the Theory of Algorithmic Fairness.

Cite As Get BibTex

Monika Henzinger, Charlotte Peale, Omer Reingold, and Judy Hanwen Shen. Leximax Approximations and Representative Cohort Selection. In 3rd Symposium on Foundations of Responsible Computing (FORC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 218, pp. 2:1-2:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.FORC.2022.2

Abstract

Finding a representative cohort from a broad pool of candidates is a goal that arises in many contexts such as choosing governing committees and consumer panels. While there are many ways to define the degree to which a cohort represents a population, a very appealing solution concept is lexicographic maximality (leximax) which offers a natural (pareto-optimal like) interpretation that the utility of no population can be increased without decreasing the utility of a population that is already worse off. However, finding a leximax solution can be highly dependent on small variations in the utility of certain groups. In this work, we explore new notions of approximate leximax solutions with three distinct motivations: better algorithmic efficiency, exploiting significant utility improvements, and robustness to noise. Among other definitional contributions, we give a new notion of an approximate leximax that satisfies a similarly appealing semantic interpretation and relate it to algorithmically-feasible approximate leximax notions. When group utilities are linear over cohort candidates, we give an efficient polynomial-time algorithm for finding a leximax distribution over cohort candidates in the exact as well as in the approximate setting. Furthermore, we show that finding an integer solution to leximax cohort selection with linear utilities is NP-Hard.

Subject Classification

ACM Subject Classification
  • Theory of computation → Theory and algorithms for application domains
Keywords
  • fairness
  • cohort selection
  • leximin
  • maxmin

Metrics

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

Related Versions

References

  1. Miriam Allalouf and Yuval Shavitt. Centralized and Distributed Algorithms for Routing and Weighted Max-Min Fair Bandwidth Allocation. IEEE/ACM Transactions on Networking, 16(5):1015-1024, October 2008. URL: https://doi.org/10.1109/TNET.2007.905605.
  2. Konstantina Bairaktari, Huy Le Nguyen, and Jonathan Ullman. Fair and optimal cohort selection for linear utilities. arXiv preprint, 2021. URL: http://arxiv.org/abs/2102.07684.
  3. Gabriel Balan, Dana Richards, and Sean Luke. Algorithms for leximin-optimal fair policies in repeated games. Technical Report GMU-CS-TR-2008-1, George Mason University, 2008. Google Scholar
  4. Robert G Bland, Donald Goldfarb, and Michael J Todd. The ellipsoid method: A survey. Operations research, 29(6):1039-1091, 1981. Google Scholar
  5. Robert Bredereck, Piotr Faliszewski, Ayumi Igarashi, Martin Lackner, and Piotr Skowron. Multiwinner elections with diversity constraints. arXiv preprint, 2017. URL: http://arxiv.org/abs/1711.06527.
  6. Rainer E Burkard and Franz Rendl. Lexicographic bottleneck problems. Operations Research Letters, 10(5):303-308, 1991. Google Scholar
  7. Elisa Celis, Vijay Keswani, Damian Straszak, Amit Deshpande, Tarun Kathuria, and Nisheeth Vishnoi. Fair and diverse dpp-based data summarization. In International Conference on Machine Learning, pages 716-725. PMLR, 2018. Google Scholar
  8. L Elisa Celis, Lingxiao Huang, and Nisheeth K Vishnoi. Multiwinner voting with fairness constraints. arXiv preprint, 2017. URL: http://arxiv.org/abs/1710.10057.
  9. Federico Della Croce, Vangelis Th Paschos, and Alexis Tsoukias. An improved general procedure for lexicographic bottleneck problems. Operations research letters, 24(4):187-194, 1999. Google Scholar
  10. Emily Diana, Wesley Gill, Ira Globus-Harris, Michael Kearns, Aaron Roth, and Saeed Sharifi-Malvajerdi. Lexicographically Fair Learning: Algorithms and Generalization. arXiv:2102.08454 [cs, stat], February 2021. URL: http://arxiv.org/abs/2102.08454.
  11. Benjamin Doerr. Probabilistic Tools for the Analysis of Randomized Optimization Heuristics, pages 1-87. Springer, January 2020. URL: https://doi.org/10.1007/978-3-030-29414-4_1.
  12. Vitalii Emelianov, Nicolas Gast, Krishna P Gummadi, and Patrick Loiseau. On fair selection in the presence of implicit variance. In Proceedings of the 21st ACM Conference on Economics and Computation, pages 649-675, 2020. Google Scholar
  13. Bailey Flanigan, Paul Gölz, Anupam Gupta, Brett Hennig, and Ariel D Procaccia. Fair algorithms for selecting citizens’ assemblies. Nature, 596(7873):548-552, 2021. Google Scholar
  14. Rupert Freeman, Sujoy Sikdar, Rohit Vaish, and Lirong Xia. Equitable allocations of indivisible goods. In Sarit Kraus, editor, Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pages 280-286. ijcai.org, 2019. URL: https://doi.org/10.24963/ijcai.2019/40.
  15. Mohammad Mahdi Kamani, Rana Forsati, James Z Wang, and Mehrdad Mahdavi. Pareto efficient fairness in supervised learning: From extraction to tracing. arXiv preprint, 2021. URL: http://arxiv.org/abs/2104.01634.
  16. Jon Kleinberg, Yuval Rabani, and Éva Tardos. Fairness in routing and load balancing. In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pages 568-578. IEEE, 1999. Google Scholar
  17. Jon Kleinberg and Manish Raghavan. Selection problems in the presence of implicit bias. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  18. Matthäus Kleindessner, Pranjal Awasthi, and Jamie Morgenstern. Fair k-center clustering for data summarization. In International Conference on Machine Learning, pages 3448-3457. PMLR, 2019. Google Scholar
  19. David Kurokawa, Ariel D. Procaccia, and Nisarg Shah. Leximin Allocations in the Real World. ACM Transactions on Economics and Computation, 6(3-4):11:1-11:24, October 2018. URL: https://doi.org/10.1145/3274641.
  20. Natalia Martinez, Martin Bertran, and Guillermo Sapiro. Minimax pareto fairness: A multi objective perspective. In International Conference on Machine Learning, pages 6755-6764. PMLR, 2020. Google Scholar
  21. Natalia L Martinez, Martin A Bertran, Afroditi Papadaki, Miguel Rodrigues, and Guillermo Sapiro. Blind pareto fairness and subgroup robustness. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 7492-7501. PMLR, 18-24 July 2021. URL: https://proceedings.mlr.press/v139/martinez21a.html.
  22. Nimrod Megiddo. Optimal flows in networks with multiple sources and sinks. Mathematical Programming: Series A and B, 7(1):97-107, December 1974. URL: https://doi.org/10.1007/BF01585506.
  23. Nimrod Megiddo. A good algorithm for lexicographically optimal flows in multi-terminal networks. Bulletin of the American Mathematical Society, 83(3):407-409, 1977. Google Scholar
  24. Margaret Mitchell, Dylan Baker, Nyalleng Moorosi, Emily Denton, Ben Hutchinson, Alex Hanna, Timnit Gebru, and Jamie Morgenstern. Diversity and inclusion metrics in subset selection. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, pages 117-123, 2020. Google Scholar
  25. Dritan Nace and Michal Pióro. Max-min fairness and its applications to routing and load-balancing in communication networks: A tutorial. IEEE Communications Surveys & Tutorials, 10(4):5-17, 2008. Google Scholar
  26. Wlodzimierz Ogryczak, Michal Pióro, and Artur Tomaszewski. Telecommunications network design and max-min optimization problem. Journal of telecommunications and information technology, pages 43-56, 2005. Google Scholar
  27. Candice Schumann, Samsara N Counts, Jeffrey S Foster, and John P Dickerson. The diverse cohort selection problem. arXiv preprint, 2017. URL: http://arxiv.org/abs/1709.03441.
  28. Aravind Srinivasan. Distributions on level-sets with applications to approximation algorithms. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 588-597. IEEE, 2001. 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