Individual and group fairness in geographical partitioning

Consider a service system in which individuals are served by facilities at different locations within a geographical region. For example, the facilities could represent schools, polling places, or commercial fulfillment centers. The geographical partitioning problem (Carlsson & Devulapalli 2013) divides the region into non-overlapping districts, such that all individuals residing in the same district are served by the same facility. The goal is to choose a partition that optimizes some measure of social welfare, most commonly the average travel cost per individual (Carlsson et al. 2016). We formulate and study a novel variant of this problem where the population is heterogeneous, consisting of multiple demographic groups, each with a different spatial distribution throughout the region. Again we optimize the expected cost, but now we also impose a new group fairness condition: each subpopulation can be neither over-nor under-represented at any facility. In other words, the districts are designed in such a way that the proportion of the population belonging to a particular group in any district must match that group's incidence in the entire population. This condition is also known as "demographic parity" in the literature (Dwork et al. 2012).