License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FORC.2022.2
URN: urn:nbn:de:0030-drops-165258
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16525/
Go to the corresponding LIPIcs Volume Portal

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

Leximax Approximations and Representative Cohort Selection

pdf-format:
LIPIcs-FORC-2022-2.pdf (0.8 MB)

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.

BibTeX - Entry

@InProceedings{henzinger_et_al:LIPIcs.FORC.2022.2,
  author =	{Henzinger, Monika and Peale, Charlotte and Reingold, Omer and Shen, Judy Hanwen},
  title =	{{Leximax Approximations and Representative Cohort Selection}},
  booktitle =	{3rd Symposium on Foundations of Responsible Computing (FORC 2022)},
  pages =	{2:1--2:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-226-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{218},
  editor =	{Celis, L. Elisa},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16525},
  URN =		{urn:nbn:de:0030-drops-165258},
  doi =		{10.4230/LIPIcs.FORC.2022.2},
  annote =	{Keywords: fairness, cohort selection, leximin, maxmin}
}

Keywords: fairness, cohort selection, leximin, maxmin
Collection: 3rd Symposium on Foundations of Responsible Computing (FORC 2022)
Issue Date: 2022
Date of publication: 15.07.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI