Preserving Diversity When Partitioning: A Geometric Approach
Alfredo Torrico – Polytechnique Montréal, Canada
Séminaire hybrique sur Zoom et dans la salle de séminaire du GERAD.
Diversity plays a crucial role in team formation, representation of minority groups and generally when allocating resources fairly. Given a community composed by individuals of different types, we study the problem of dividing this community such that the global diversity is preserved as much as possible in each subgroup. We consider the diversity metric introduced by Simpson in his influential work that, roughly speaking, corresponds to the inverse of the probability that two individuals are from the same type when taken at random, with replacement. We provide a novel perspective by reinterpreting this quantity in geometric terms. We characterize the instances in which the optimal partition exactly preserves the global diversity in each subgroup. When this is not possible, we provide an efficient polynomial-time algorithm that outputs an optimal partition for the problem with two types. Finally, we discuss further challenges and open questions for the problem that considers more than two types.
Campus de l'Université de Montréal
2920, chemin de la Tour
Montréal Québec H3T 1J4