  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.
