Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
71,488 characters · 11 sections · 70 citation commands
Individual and group fairness in geographical partitioning
{.5\baselineskip}
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 CaDe13 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 CaCaDe16.
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 Dwork12.
We are motivated by the well-known phenomenon of socioeconomic segregation in school districts ReBi11. As income inequality increased over the past several decades, both high- and low-income households exhibited a greater tendency to cluster together geographically, resulting in segregation not only between school districts but also between individual schools in the same district OwReJe16. Much of this behavior has been driven by families with children Ow16, for whom school boundaries are a major factor in residential decisions. Income segregation between school districts has been linked to gaps in student achievement RyVa07,Ow18, as many high-income districts receive more resources due to higher revenues from local taxes Baker17. Unequal representation of different socioeconomic groups across districts is thus closely linked with disparities in opportunities and outcomes.
The causes of income segregation are complex and, generally, beyond the scope of what can be “fixed” by a single optimization model. Nonetheless, incorporating demographic parity into districting decisions could be seen as one possible way to remove a perceived incentive for economic segregation. In this connection, it is interesting that Sa17a,Sa17 found empirical evidence that segregation is less pronounced in districts that are “irregularly” shaped, i.e., not contained within a small area. Drawing on these observations, a policy paper by Br19 proposed, “Another option to disrupt the segregating influence of catchment areas is to gerrymander them in reverse -- that is, to draw catchment area lines to purposely include a diverse population.” At the same time, such drastic measures can come at a substantial cost CaSiBrWi24, even for those groups that are meant to benefit from them: for example, some disadvantaged households may experience significant increases in travel time as a result of rezoning. Formulating and solving a fair districting problem, such as the one in this paper, can help quantify the cost of fairness and contribute to a more informed policy.
In addition to group fairness, we also impose the condition of individual fairness, meaning that the assignment of an individual to a facility depends only on the geographical location of the individual, and not on the demographic group to which the individual belongs. It is well-known that these attributes are correlated BaMcRu04, but explicit dependence of the decision on the demographic group is perceived as unfair and has been successfully challenged in court Parents07,Students23. In our setting, individual fairness means that we have a single partition that is universally applied to the entire population.
Individual and group fairness have been extensively studied in very general contexts, and the distinction between them can be made more precise as follows. Suppose that we randomly select an individual from the population. The individual is described by attributes $\left(X,Z\right)$. In our setting, $X$ represents the geographical location of the individual (a point on the map), but in the more general literature it may model other information; for example, ZhRy24 considers a hiring problem where $X$ is a vector describing the qualifications of a job applicant. The protected attribute $Z$ is a categorical variable indicating the demographic or socioeconomic group to which the individual belongs. We act upon the individual with some decision $Y$ (in our setting, an assignment to a facility). Because $Y$ depends on the observed random attributes, it is also a random variable. We then have the following definitions:
One does not at all imply the other, and it is quite uncommon to achieve both individual and group fairness simultaneously in the same problem. In fact, an influential paper by KlMuRa17 argues that this is impossible in general, with unavoidable tradeoffs between different definitions of fairness. In the specific context of partitioning, however, a striking result by DvWaWo51 proved the existence of partitions satisfying both criteria for any number of facilities and subpopulations. Unfortunately, the proof was non-constructive, and the question of how such partitions can be computed remained open. This question is fully resolved in our paper: we provide a complete characterization of partitions that not only satisfy both types of fairness, but are optimal with respect to expected cost.
Our approach is inspired by the theory of semidiscrete optimal transport HaSc20,Vi21, though our problem does not fully fit that framework due to the presence of the group fairness condition. We relax the partitioning problem to allow probabilistic assignments, so that a fixed location can be assigned to any facility randomly according to a distribution to be determined by the decision-maker. This version of the problem can be formulated as an infinite-dimensional linear program. Crucially, however, the dual of this problem can be written as a nonlinear, but finite-dimensional concave program, which can be tractably solved. The dual variables characterize the optimal assignment policy, which turns out to be deterministic; in other words, even with probabilistic assignments allowed, it is still optimal to assign each location to a single facility. The assignment rule has a geometric interpretation as a novel generalization of the additively weighted Voronoi diagram Au91, which is well-known to arise in classical districting problems. In our context, each facility has multiple weights (one for each group) rather than just one, and these weights are mixed differently at each location depending on the relative incidence of each group there.
We then show how the optimal partition can be efficiently computed. Although the objective function of the finite-dimensional dual involves a difficult integral, it turns out that it can be tractably optimized using the method of stochastic approximation PaKi11. We only require the ability to simulate individuals from the spatial distribution of any demographic group; in the case of population densities, these data are publicly available. With simulation, the problem can be solved using a very simple algorithm, which can be coded in several lines, and which provably converges at a near-optimal rate. Because the procedure only requires realizations of costs, we can actually solve the problem without knowing the closed form of the cost function. In fact, in our case study, we obtain costs from a database that uses real network data and accounts for traffic patterns in urban environments.
We demonstrate the efficacy and utility of our method on a subregion of Los Angeles with 78 school district offices and seven demographic groups for which census data were available. The case study starkly illustrates the costs and tradeoffs that arise when imposing demographic parity. We find that the imposition of fairness constraints significantly increases travel costs across the board for all groups, including disadvantaged ones. In addition, the presence of segregation can lead to undesirable geometry in the partition, e.g., discontinuities in the service zones. At the same time, our results also provide insight into how these negative impacts can be mitigated. For example, extreme outliers of the travel cost distribution can be reduced by optimizing expected squared travel time, which is trivial to do under our modeling and algorithmic framework. Furthermore, reducing the number of distinct groups in the model will improve costs across the board for all groups. Potentially, such an analysis could help policymakers decide the set of groups for which fair representation is to be enforced; in some cases, the cost of fairness may outweigh the benefits for certain subpopulations, while also increasing the burden on everyone else. The presence of such cases can also be interpreted as a measure of how much segregation is present in the region under consideration.
In summary, this paper makes the following contributions. 1) We formulate a new class of geographical partitioning problems with a heterogeneous population and demographic parity constraints, neither of which has previously been considered in computational geometry. 2) We prove that the optimal solution is completely characterized by a finite set of weights, which comprise a novel generalization of the additively weighted Voronoi diagram. 3) We show how the optimal weights can be found using a stochastic approximation algorithm, which is trivial to implement, converges at a near-optimal rate, and requires only realizations from the cost function. In this way, we answer a long-standing open question about the computation of fair partitions. 4) We empirically evaluate our approach on a realistic setting, providing insight into the cost of fairness for each subgroup. Overall, our work combines concepts from algorithmic fairness and computational geometry in a novel way, and is of both theoretical and practical interest.
Our work bridges three distinct streams of literature, including elements of algorithmic fairness, optimal transport, and geographical partitioning. Below, we position our work relative to each stream.
Algorithmic fairness. This literature, surveyed by BaGoLo20, has mainly grown out of the computer science community. Both individual JoKeMoRo16,GuKa21 and group Dwork12,KaZh21 fairness, in the sense of our paper, have attracted considerable attention. Only one of these definitions is generally adopted in any given study, due to the widespread belief that the differences between them are irreconcilable. In this respect, our work stands out as an example of a setting where two distinct definitions can be satisfied simultaneously.
Computer scientists and statisticians have also proposed other definitions specialized for prediction problems HaPrPrSr16,Ch17, which are the main focus of machine learning. For example, given a limited sample, one may wish to balance prediction error CaVe10, or reduce prediction bias ZiRo20, across multiple demographic groups. These studies do not explicitly model any decision problem, and thus do not apply to situations where the goal is to design a fair decision rather than a fair prediction. See also ZhRy24 for an in-depth example of a problem where fair decisions are very different from fair predictions.
Optimal transport. Recent work HaSc20 has shown that optimal transport theory PeCu19 offers a useful lens through which to approach geographical partitioning problems. Semidiscrete optimal transport is an infinite-dimensional linear program with a finite-dimensional dual CaCaDe16, which can be solved efficiently using the method of stochastic approximation GeCuPeBa16, a classical technique from the simulation literature PaKi11.
Recently, JoLu19 and Chzhen20 leveraged optimal transport theory to find policies satisfying group fairness conditions, by connecting the latter to the Wasserstein barycenter problem AgCa11. This approach is limited to quadratic cost functions, and also allows the decision to depend directly on the demographic group, thus violating individual fairness. In fact, when both types of fairness are considered, the problem is no longer reducible to classical optimal transport. However, we show that infinite-dimensional duality still applies and provides a roadmap for efficient computation.
Geographical partitioning. The field of computational geometry CaDe13 has extensively studied additively weighted Voronoi diagrams AuKl00, a class of geometric structures where the assignment of an individual to a facility is made by minimizing the sum of travel distance and a facility-specific “weight.” Applications include the design of delivery HaHoLa07 and political RiScSi08 districts, as well as various problems in facility logistics YuJaUk12. Most of these papers, like ours, view partitioning as a central planning problem, with CaPeRy24 being one exception where both centralized and decentralized behavior is considered. While this literature has examined some notions of fairness, mainly in the form of load-balancing constraints between facilities ArCaKa09, our paper is the first to explicitly model multiple demographic groups with different population densities. As a result, we discover a novel generalization of the Voronoi diagram in which each facility uses a location-dependent mixture of weights.
There is also a mature literature on districting that uses mixed-integer programming models; examples include SwKiJa23, ShBu25, OzSmGo25 and other references cited therein. Various measures of fair representation can be incorporated into the constraints of these models ArMaPeRi21. This work is primarily application-driven. While our approach is more stylized, it enables us to derive a clean analytical characterization of partitions satisfying both individual and group fairness, providing an understanding of how group fairness impacts the geometric structure of the optimal partition.
Let $\mathcal{X}$ be a compact subset of $\mathbb{R}^d$ representing the geographical region under consideration (in most practical applications, we will have $d=2$). Let $X$ be a random variable following a probability density $f$ supported on $\mathcal{X}$. We may think of $f$ as the population density and $X$ as the geographical location of a randomly selected individual from the population.
Let $Z$ be a discrete random variable taking values in $\left\{1,...,M\right\}$ with $q_z = P\left(Z=z\right)$. Each $z$ represents a different subgroup of the population, with $f_z\left(x\right) = P\left(X \in dx\mid Z = z\right)$ denoting the conditional density for that group. In this paper, $q_z$ and $f_z$ are all known; in practice, one would extract them from census data.
Suppose that there are $K$ facilities located at points $x_1,...,x_K \in \mathcal{X}$. Let $c\left(x,k\right)$ be the cost of assigning an individual at location $x$ to the $k$th facility. A natural and widely used cost function is the Euclidean distance $c\left(x,k\right) = \|x-x_k\|_2$, but our analysis is not limited to this choice. We only require the condition that the pairwise difference $c\left(X,j\right) - c\left(X,k\right)$, for any $j \neq k$, is absolutely continuous with respect to Lebesgue measure.
We formulate the problem
subject to
This problem partitions $\mathcal{X}$ into sets $\mathcal{A}_k$. Constraints ((ref)) ensure that the sets are disjoint except possibly on a boundary that has measure zero. Constraint ((ref)) ensures that the sets comprise a partition. An individual appearing at a location $x \in \mathcal{A}_k$ is presumed to be assigned to facility $k$, incurring cost $c\left(x,k\right)$. The objective ((ref)) thus chooses the partition to minimize the expected cost incurred by a randomly selected individual. Thus far, these elements of the problem are typical of geographical partitioning problems, e.g., those in CaCaDe16.
In marked contrast with those problems, however, we also include the group fairness constraints ((ref)), which ensure that the region served by facility $k$ is probabilistically independent of $Z$. In other words, each facility must serve the same proportion of each subgroup, or, to put it yet another way, the demographics of the individuals served by facility $k$ should match those of the population as a whole. As discussed in Section (ref), group fairness has been studied in a variety of settings, such as prediction Chzhen20 and hiring ZhRy24. The critical distinction here is that ((ref))-((ref)) also imposes individual fairness, that is, we design only a single partition that is applied to all demographic groups. Another way to say this is that the assignment of an individual is based only on the individual's location $X$ and not their demographic $Z$, whereas virtually all existing papers on group fairness would allow the decision to explicitly depend on both.
In the context of geographical partitioning, it is possible to simultaneously achieve both types of fairness. DvWaWo51 proved that the system ((ref))-((ref)) is feasible, though this paper did not show how the partition could be computed, and indeed it did not explicitly model any objective function. In our framework, the objective ((ref)) introduces the notion of an optimal fair partition. In Sections (ref)-(ref), we will show how such a partition can be characterized and computed. First, however, we present a simple example to illustrate the concept.
Figure (ref) shows an instance where the geographical region $\mathcal{X} = \left[0,1\right]^2$ contains three subpopulations. The population densities $f_z$, for $z \in\left\{1,2,3\right\}$, are shown separately. We see that the “red” group is mainly concentrated in the bottom-right portion of the unit square, with some presence near the left edge; the “green” group mainly resides along the bottom edge, with some presence in the middle; and the “blue” group is heavily concentrated in the top-right. Each subpopulation has some presence in every part of the map, but overall the region is quite segregated.
In Figure (ref), we superimpose the three densities onto the same plots and consider the partitioning problem with four facilities represented by white squares. Figure (ref) shows a partition in which every individual is assigned to the closest facility, i.e., the facility with the smallest Euclidean distance from their location. This type of partition is very well-known in the literature under the name “Voronoi diagram.” Individual fairness is clearly satisfied, because assignment is a deterministic function of location and has no additional dependence on demographic. However, group fairness is not satisfied: for example, the blue group is over-represented at facility 1 and under-represented at facility 4.
On the other hand, Figure (ref) shows the optimal fair partition for this instance. The objective is still to minimize expected travel distance (measured using the Euclidean norm), but we now impose the group fairness constraints ((ref)). The region served by facility $z$ is now labeled. We see that the regions have become non-contiguous: for example, the top-right corner is now divided between facilities $1$, $3$, and $4$, as the latter two have no other way to achieve representation for the blue group. Such geometry is likely undesirable in practice, and, in our case study in Section (ref), we discuss some ways to reduce these effects by changing the cost function $c$. However, if the populations are already very heavily segregated, even an optimal partition will unavoidably have disconnected regions. The most that can be guaranteed is that the enclaves and exclaves will be chosen in a way that minimizes the overall cost at the population level.
If we were to adopt the fair partition in this example, some individuals from the blue group would experience a significant increase in travel cost. At the same time, if the blue group were disadvantaged to begin with, the more distant facilities might be preferable in other ways (e.g., because those schools have more resources). Furthermore, whatever the resulting travel cost might be, the partition in Figure (ref) is optimal, and any attempt to make the borders “nicer” would inevitably make the objective value even worse. One could also make the argument (though this issue is outside the scope of this paper) that group fairness will eventually change the population densities themselves in a manner that reduces segregation. Lastly, a comparison of the two partitions in Figure (ref) could allow policymakers to quantify the cost of eliminating segregation, regardless of whether the fair districting plan is implemented. In other words, the study of ((ref))-((ref)) can be informative and insightful even when not interpreted as a direct “call to action.”
To solve ((ref))-((ref)), we relax the problem to allow probabilistic assignments, analogously to the well-known Kantorovich formulation of semidiscrete optimal transport Vi21. Let $Y$ be a discrete random variable taking values in $\left\{1,...,K\right\}$. The quantity $g\left(x,k\right) = P\left(Y=k\mid X=x\right)$ represents the conditional probability of assigning an individual to facility $k$, given that they appear at location $x$. In the original formulation, this probability would be $1$ if $x \in \mathcal{A}_k$ and $0$ otherwise, but this may no longer be the case in the relaxation. We will eventually show, however, that the optimal solution of the relaxed problem is also feasible for ((ref))-((ref)). This result is similar to the well-known equivalence of the Monge and Kantorovich formulations of optimal transport Pr07, with the difference that neither of those formulations contains fairness constraints.
In Section (ref), we formulate and solve the relaxed problem under the additional assumption that $P\left(Y = k\right) = p_k$ for some pre-specified vector $p$ of probabilities. This is like modifying ((ref)) to require $P\left(X \in \mathcal{A}_k\mid Z\right) = p_k$. Then, in Section (ref), we show how to optimize over $p$. We break the problem down into these two parts for ease of understanding, and also because the case of fixed $p$ may be of stand-alone interest in itself (for example, if the $k$th facility only has enough capacity to handle a proportion $p_k$ of the population).
We formulate the problem
subject to $g \geq 0$ and
The objective function in ((ref)) is simply $\mathbb{E}\left(c\left(X,Y\right)\right)$ written out by conditioning on $Z$. This is the same objective as ((ref)), with the sole difference being that the assignment $Y$ is no longer required to be a deterministic function of $X$. Constraints ((ref)) require every location to be assigned to a facility, analogously to ((ref)). Constraints ((ref)) force $Y$ to be probabilistically independent of $Z$, similarly to ((ref)), but also impose the fixed pmf $p$ on the marginal distribution of $Y$. Individual fairness is ensured by the fact that, for fixed $x$ and $k$, the decision $g\left(x,k\right)$ has no dependence on $Z$.
Problem ((ref))-((ref)) resembles semidiscrete optimal transport HaSc20,ZhRy24b. The difference is that, in the classical semidiscrete formulation, the index $z$ is not present at all, and we can then simply optimize over the joint density of $\left(X,Y\right)$ rather than the conditional pmf of $Y$ given $X$. The constraints in semidiscrete optimal transport fix the marginal distributions of both $X$ and $Y$, without the additional complication of fairness.
These differences notwithstanding, problem ((ref))-((ref)) has one aspect in common with semidiscrete OT, namely, that it is an infinite-dimensional linear program. We may therefore derive its Kantorovich dual using the following result.
The proof of Theorem (ref) is given in the Appendix. The dual variables $\phi\left(x\right)$ and $\psi_z\left(k\right)$ correspond to the primal constraints ((ref)) and ((ref)), respectively. Note that ((ref))-((ref)) is also an infinite-dimensional linear program, with $\phi$ being a functional variable. However, as we will now show, it is possible to reformulate the problem as a nonlinear, but finite-dimensional concave program.
We may optimize $\phi$ by taking
Letting $w_{k,z} = \frac{\psi_z\left(k\right)}{q_z}$, we may rewrite ((ref))-((ref)) as the unconstrained (and finite-dimensional) optimization problem
Observe, furthermore, that
whereas
Consequently, ((ref)) may be further rewritten as
Before proceeding further, let us contrast ((ref)) with the well-known dual reformulation of semidiscrete OT GeCuPeBa16. In that problem, $Z$ is not present (the population is homogeneous), so the primal LP is essentially a special case of ((ref))-((ref)) with $M = 1$. In that case, ((ref)) reduces to
that is, for each facility $k$ there is a single, fixed weight $w_k$. In the presence of group fairness constraints, however, the $k$th facility now has multiple weights $w_{k,z}$ corresponding to different subgroups, and the objective function calculates a mixture of these weights according to the conditional distribution of $Z$ given $X$. However, since the conditional expectation is a linear function of the weights, the function
viewed as a function of $w$, is a minimum of a finite number of linear functions and therefore concave. Since expectations preserve concavity, ((ref)) is an unconstrained concave maximization problem, and therefore tractable in principle.
We can further characterize the optimal solution $w^*$ of ((ref)). Since $\mathcal{X}$ is closed and bounded, we may differentiate under the integral sign and obtain
For fixed $x$ and $k,z$,
Therefore,
where ((ref)) follows by the projection property of conditional expectations (Ci11, ch. IV, sec. 1, eq. (1.4)). Therefore, $w^*$ solves the system
From ((ref)), we can also characterize the optimal primal solution as a function of the optimal dual variables. The following result shows how to construct $Y$ to optimize the relaxation ((ref))-((ref)).
\noindentProof: By definition of $Y^*$, ((ref)) is exactly $P\left(Z=z,Y^*=k\right) = p_k P\left(Z=z\right)$, whence $P\left(Y^*=k\mid Z=z\right) = p_k$ for all $z$. This choice of $Y$ is therefore feasible for ((ref))-((ref)).
By weak duality,
where $g$ is the conditional pmf of $Y$ given $X$, satisfying ((ref))-((ref)) as before. We then write
where ((ref)) again follows by the projection property of conditional expectations (since $Y^*$ is a deterministic function of $X$), whereas ((ref)) uses the independence of $Z$ and $Y^*$. The desired result follows. $\Box$
The optimal $Y^*$ from Proposition (ref) then induces the partition
which is feasible for the original problem ((ref))-((ref)) under some mild conditions on the distribution of $X$. Specifically, it suffices for the pairwise differences $c\left(X,j\right) - c\left(X,k\right)$ to have a density for any $j \neq k$.
Once again, it is interesting to compare ((ref)) with the partition obtained in the standard semidiscrete OT problem, where group fairness constraints are not present. Recall that this standard problem has the dual objective ((ref)), where there is no $Z$ variable and only one weight for each $k$ value. Letting $w^*_k$ be the optimal weights for that problem, ((ref)) induces a partition where an individual appearing at location $x$ is assigned to the facility corresponding to $\arg\min_j c\left(x,j\right) - w^*_j$. This geometric structure, where assignments are made by minimizing the sum of travel distance and a facility-specific weight, is precisely the well-known additively weighted Voronoi diagram Au91. In our setting, ((ref)) induces the partition ((ref)), which can be viewed as a novel generalization of this concept. The imposition of group fairness constraints leads to a diagram in which each facility has multiple weights, rather than just one, and the assignment uses a mixture of these weights that depends on the location of the individual. In other words, if a subgroup $z$ is more prevalent at location $x$, then the corresponding weights $w^*_{j,z}$ play a greater role in determining the facility serving that location.
We will now show how the vector $p$ may be eliminated entirely, yielding an optimal solution to ((ref))-((ref)) under the best possible marginal distribution of $Y$. Let $w^*\left(p\right)$ denote the optimal weights for problem ((ref)) with a fixed $p$, and let
By the envelope theorem,
because the only direct dependence of ((ref)) on $p$ occurs in the last term.
Consider the outer optimization problem
subject to $p_k \geq 0$ and $\sum_k p_k = 1$. Let $\nu_k$ and $\lambda$ be the Lagrange multipliers of the inequality and equality constraints, respectively. Then, the optimal $p^*,\lambda^*,\nu^*$ satisfy the first-order optimality conditions
Adding a constant $\lambda^*$ to all the weights will not affect the partition, so we may assume $\lambda^* = 0$ without loss of generality. Then, the complementary slackness conditions imply that
For $k$ satisfying $p^*_k = 0$, define the modified weights $\bar{w}_{k,z} = w^*_{k,z}\left(p^*\right) - \nu^*_k$. Then, clearly $\sum_z q_z \bar{w}_{k,z} = 0$. To show that the modified weights do not change the partition, it is sufficient to show that the set $\mathcal{A}_k$ induced by $w^*_{k,z}\left(p^*\right)$ according to ((ref)) remains unchanged by the modification. Since $p^*_k = 0$, we have
that is, for any $x$ there is always one facility that is preferable to $k$. Suppose now that, under the modified weights, ((ref)) is violated: that is, there exists $x_0$ such that
However,
which leads to a contradiction with ((ref)). Thus, the modified weights do not change the original partition; the objective value is also unchanged since it is determined only by the non-empty regions. Therefore, the optimality conditions ((ref))-((ref)) of the outer problem can be rewritten more succinctly as
that is, $\mathbb{E}\left(w^*_{k,Z}\right) = 0$ for all $k$.
We may now combine the results of Sections (ref)-(ref) and give a complete characterization of the optimal partition. Our goal is to find a solution $\left(w^*,p^*\right)$ of the system of nonlinear equations
Note that the left-hand side of ((ref)) is $P\left(Z=z,Y=k\right)$, so this constraint implies $p_k \geq 0$, $\sum_k p_k = 1$ and we may omit those conditions.
It can be readily seen that ((ref))-((ref)) are precisely the KKT conditions of the constrained concave program
subject to the linear equalities ((ref)). Here, the optimal region sizes $p^*_k$ become the Lagrange multipliers of the equality constraints. This problem trivially satisfies Slater's condition, so ((ref))-((ref)) are necessary and sufficient for optimality. Even if there are multiple $\left(w^*,p^*\right)$ satisfying ((ref))-((ref)), each solution achieves the same value of ((ref)) as well as $V^*\left(p^*\right)$.
We may eliminate the constraints entirely by using the transformation
which projects any arbitrary $\left(v_{k,1},...,v_{k,M}\right)$ onto the orthogonal complement of $q$. This yields the unconstrained optimization problem
Since ((ref)) is a linear function of $v$, the objective function in ((ref)) is still concave. Note that $\mathbb{E}\left(q_Z\mid X\right)$ does not depend on $v$. Therefore, for fixed $k$, $z$, and $x$,
Applying the projection property of conditional expectation once more, the optimality conditions of ((ref)) are
for $k = 1,...,K$ and $z = 1,...,M$.
The system ((ref)) may be approached as a stochastic root-finding problem PaKi11. Because the expectation in ((ref)) is difficult to compute, we may instead approximate it using simulation, in a procedure known as stochastic approximation KuYi03. Given an approximation $v^n$ of the solution, we observe a sample $\left(X^{n+1},Z^{n+1}\right)$ from the underlying joint distribution, and evaluate the random variable inside the expectation in ((ref)) using these values. On average, this random variable will point us toward the root. We then compute $v^{n+1}$ by adjusting $v^n$ in the indicated (noisy) direction, using a stepsize to smooth out noise. Algorithm (ref) formally states the procedure.
Since the random variable in ((ref)) is bounded, the convergence of $\left\{v^n\right\}$ to an optimum of ((ref)) easily follows by classical SA theory. It is possible to characterize the convergence rate in greater depth. The following theorem (proved in the Appendix) derives a bound that matches the near-optimal rates in BaMo11, but uses weaker conditions. More precisely, Thms. 4-7 in BaMo11 require the stochastic gradient to be Lipschitz continuous, which does not hold in our setting because ((ref)) uses indicator functions. We drop this requirement, but obtain the same guarantee. It is worth noting that the rate bound is obtained, not on the sequence $\left\{v^n\right\}$ directly, but on the average of these iterates. This technique, known as Polyak averaging, has been known to speed up convergence since PoJu92. From an implementation perspective, it is quite simple to incorporate averaging into Algorithm (ref).
In this section, we demonstrate the practicability of our approach on real population and demographic data. Our setting is the San Fernando Valley (SFV) region of Los Angeles County, a diverse area with significant demographic variation across neighborhoods. Some areas show high concentrations of specific demographic groups, a pattern typical of urban segregation documented in the literature ReBi11.
The census distinguishes between seven\footnote[1]{Unfortunately, “Hispanic” is not among the available options in the census, and therefore we were not able to include it as a distinct category in this study.} racial/ethnic categories: Multiracial ($13.43\%$ of the total population in the region), White ($45.39\%$), Black ($3.86\%$), American Indian ($1.30\%$), Asian ($11.41\%$), Pacific Islander ($0.11\%$), and Other ($24.50\%$). In Section (ref), we apply our modeling and algorithmic framework to construct a partition that achieves fair representation for all seven categories, to demonstrate the capabilities of our approach. In Section (ref), we repeat the same analysis with three groups: Black, Asian, and all the others combined into one. Our intention here is simply to demonstrate how the number of groups influences the costs for the population as a whole. For example, a comparison between the two versions of the case study will show that, when we require fair representation for all seven groups, costs increase for everyone across the board, including the disadvantaged populations whom the fair partition aims to benefit. This should be an important consideration for policymakers when deliberating the issue of fair representation.
We obtained latitude and longitude coordinates for school district administrative offices from the National Center for Education Statistics Education Demographic and Geographic Estimates Program geocoded data files nces. From this dataset, we selected $78$ administrative offices located within the SFV boundary using a San Fernando Valley shapefile obtained from ArcGIS Online esri. We also incorporated detailed census tract population data from the American Community Survey for all seven demographic groups.
The cost $c\left(x,k\right)$ of traveling to district office $k$ for a household located at coordinates $x$ was computed using the Open Source Routing Machine (OSRM) with real road network data, providing realistic driving times and distances rather than simply Euclidean norms. This approach captures the true cost of travel in an urban environment with complex street networks and traffic patterns. Using real costs does not create any additional challenges for our solution technique since Algorithm (ref) only requires the ability to evaluate $c\left(X,k\right)$ for a realization $X$ from the population. We ran our algorithm for two variants of the optimization problem: one where $c\left(x,k\right)$ was set equal to the real travel distance (which we also refer to as “regular distance”), and another one where it was set equal to the squared travel distance. In computational geometry, partitions based on squared distance are known as “power diagrams” and tend to create more compact and balanced regions, because they heavily penalize extreme deviations from district centers CoKlYo18.
Both variants include group fairness constraints. As a baseline, we also compute a standard Voronoi diagram where facility $k$ serves the set $\left\{x : k = \arg\min_j c\left(x,j\right)\right\}$, that is, each household is assigned to the closest district office. This “unconstrained” partition will clearly not achieve demographic parity. Of course, in practice, the determination of school district boundaries involves other factors aside from simply travel distance. Nonetheless, Voronoi diagrams have been previously studied for this purpose Pe00,GoAr20, and because our focus here is on evaluating the price of fairness, they provide a natural basis for comparison. In these experiments, we do not fix the capacity of each facility (that is, we optimize over $p_k$), but if one wished to fix them in advance, this could be done using the techniques of Section (ref).
Table (ref) shows the mean and 90th percentile of the travel distance for each demographic group under each of the three models (for the model that optimizes squared cost, we still report statistics for the unsquared distance). Figure (ref) further shows the empirical cumulative distribution functions of the travel distance for each demographic group/model combination. We see that the price of fairness is quite substantial, with all seven demographic groups experiencing significant increases in travel time relative to the unconstrained model. Optimizing the squared distance reduces outliers on both the low and high ends: the median travel time increases for each group relative to the standard equity-constrained model, with the benefit of reducing extremely high times.
Additional insights can be obtained by examining individual district boundaries. Figure (ref) shows four representative districts under both cost functions (a complete set of plots for all $78$ facilities is included in the Appendix). The district offices are represented by white squares, and the census tracts assigned to the office in question are shown as pie charts whose size reflects the local population. Thus, for example, Facility 12 is located in the center-west of the map (along Route 101, east of Calabasas). Under regular distance, several census tracts from the other side of I-405 are assigned to this office, leading to high travel times for those households; under squared distance, these assignments are no longer made. Similar behavior can be observed for Facilities 34, 63, and 76: in all three cases, switching to squared distance eliminates the worst outliers, though it may not eliminate discontinuities completely. The optimal district sizes (that is, the optimal choices of $p_k$) need not the same for both cost functions. We will revisit these four examples in Section (ref) when the entire case study is rerun for a reduced set of demographic groups.
It is also noteworthy that fair partitioning may result in the closure of school administrative offices. This does not happen for the unconstrained model, since for any facility, there is always some subset of the population that is closest to it. However, under equity constraints and regular cost, $7$ out of $78$ district offices receive no student assignments, and this number increases to $12$ when we optimize the squared distance. Five offices are closed under both models. These situations can arise when a particular demographic group is hyper-concentrated in a small geographical area: if that area is very far away from a certain office, it may be more cost-effective to close that office entirely rather than shuttle individuals across the map to it.
While the results of this analysis may not be directly implementable, they can nonetheless be useful to inform discussion of equity in districting. First, it bears repeating that an equitable partition is shown to be feasible, which is not obvious without our analysis. Second, we are able to quantify the cost paid by each demographic group for fair representation. As Table (ref) shows, the cost may even be higher for disadvantaged groups: for example, median travel times (under regular distance) increase by $54\%$ for the white population, but by $59\%$ for the Black population. This is a serious concern, and potentially a governing body might elect not to change district boundaries at all on such grounds. Third, if the authorities wished to adjust boundaries without fully adopting our approach, visuals such as those in Figure (ref) may help guide these modifications by suggesting where representation of certain groups might be drawn from geographically. Finally, it is important to note that certain undesirable aspects of the boundaries (such as non-contiguity) are a consequence of a high level of segregation in the population. In a sense, the difficulty of creating an equitable partition is itself an illustration of how much segregation is already present.
As mentioned previously, we also ran a version of the same case study in which only three demographic groups were considered: Black, Asian, and all the others combined. Thus, every facility must have $84.73\%$ of its assigned population coming from this last group, but the precise breakdown within that group (White, Multiracial, Other and so on) is no longer constrained. The main purpose of these additional experiments is to show how the number of groups included in the model influences travel costs for all groups, whether explicitly included or not.
Table (ref) presents the median and 90th percentile of the travel time for each group. Note that, while the model only distinguishes between three groups, we report results for all seven of the groups from the original analysis. Once more, the baseline is a model with no fairness constraints (Voronoi diagram), so those statistics are the same as in Table (ref).
When fairness constraints are included, the results are very different between Tables (ref) and (ref). Let us first consider the two groups (Black and Asian) that achieve fair representation under both versions of the case study. In Table (ref) (seven groups), the median travel cost for the Black subpopulation increases by $59.6\%$ relative to the baseline (under the regular cost function), but in Table (ref), this increase is only $38.5\%$. Likewise, for the Asian subpopulation, the increase in the median is $60.9\%$ with seven groups in the model, but only $32.9\%$ with three groups.
For the remaining five groups, the difference is even greater. In Table (ref), the median travel cost increases by over $54\%$ for each of the five relative to the baseline model (again, under the regular cost function). In Table (ref), the increase in the median is below $30\%$ for all five groups. A more detailed comparison of the cdfs for various groups and models can be seen in Figure (ref); in general, the distributions for the constrained models are closer to the baseline than they were in Figure (ref).
Figure (ref) revisits the four representative facilities from Figure (ref) in the three-group context; a complete set of plots can be found in the Appendix. It is especially instructive to compare the district boundaries between the seven-group and three-group settings. For example, in the seven-group case (Figure (ref)), Facility 63 had three outlying census tracts under regular distance and one under squared distance. In the three-group case (Figure (ref)), the most distant outliers have disappeared and the census tracts are now closer to the office. Similarly, in the seven-group case, Facility 76 had several very distant outliers, far southwest and southeast of the district office, under regular distance; in the three-group case, only the southwestern outlier is still present, while the southeastern ones are no longer assigned to this facility. Under squared distance, the census tracts were closer to the facility to begin with, and again the most distant ones have been removed in the three-group case. In other words, running the model with three groups does not guarantee that the districts will become contiguous, but it significantly reduces the fragmentation of the boundaries. It is worth noting that district closures are also reduced: under three groups, $3$ and $5$ offices are closed, respectively, for regular and squared distance (in the seven-group case these numbers were $7$ and $12$). A single office (\#16) is closed in all four versions of the case study.
This discussion shows how our analysis can be used, not only to assess the cost of fairness in a general sense, but to make a more fine-grained determination of which subpopulations could be included in the model. For example, the Pacific Islander population is known to be disadvantaged in education PaHaPa11. At the same time, when all seven groups are included in the model, Pacific Islanders suffer disproportionately from increased travel costs, with the median going up by $102\%$ relative to the baseline (under unsquared costs). In the three-group version of the analysis, the increase for that subpopulation is only $29\%$. The precise considerations behind the decision to require fair representation for a particular group are far beyond the scope of our work, but it is conceivable that, in some cases, the cost of representation may be judged to be too prohibitive for the disadvantaged group itself. In such cases, reducing the total number of groups can also alleviate the burden on other groups that remain in the model.
We have introduced a new class of geographical partitioning problems in which the population is heterogeneous, and different subgroups are required to be represented fairly (i.e., proportionally to their incidence in the population as a whole) in each district. Our study is motivated by the phenomenon of socioeconomic segregation in school districts, where some demographic groups are over- or under-represented in certain areas. This problem has been a subject of discussion for many years among social scientists and policymakers, with some authors even recommending a kind of “reverse gerrymandering” as a means to achieve integration. Essentially, our work shows how this can be done in a principled and optimal way, constructing a fair partition that minimizes expected cost.
We have provided a complete mathematical characterization of this optimal fair partition, showing that it is a novel generalization of a classical geometric structure known as the additively weighted Voronoi diagram. Although the optimization problem we are solving is infinite-dimensional, it has a finite-dimensional dual, whose decision variables are sufficient to fully describe the optimal primal solution. Furthermore, the optimal dual variables can be computed using a stochastic approximation algorithm that is trivial to code, runs efficiently, and does not require a closed form for the cost function. Together, all of these developments answer an open question dating back to DvWaWo51, which proved the existence of fair partitions but did not offer any guidance as to how they may be computed.
Our case study sheds light on some of the practical challenges that may arise when considering the implementation of such a model. Fair representation can have unintended consequences, creating non-contiguous districts and significantly increasing travel times for the entire population, particularly for the very subgroups that policymakers aim to help. Nonetheless, our analysis can also be used to explore ways to mitigate these problems, for example by changing the cost function in a manner that reduces very high travel times. There are also difficult political and ethical considerations involved in determining the precise set of subgroups to include in the model. However, we believe that the main value of our paper is in offering a rigorous, evidence-based, politically neutral framework for assessing the feasibility of fair representation in complex regions that are often highly segregated to begin with.