Individual and group fairness in geographical partitioning

• URL: http://arxiv.org/abs/2511.19722v1
• Date: Mon, 24 Nov 2025 21:34:51 GMT
• Title: Individual and group fairness in geographical partitioning
• Authors: Ilya O. Ryzhov, John Gunnar Carlsson, Yinchu Zhu,
• Abstract summary: We formulate a new class of geographical partitioning problems in which the population is heterogeneous.<n>We prove that the optimal solution is a novel generalization of the additively weighted Voronoi diagram.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Socioeconomic segregation often arises in school districting and other contexts, causing some groups to be over- or under-represented within a particular district. This phenomenon is closely linked with disparities in opportunities and outcomes. We formulate a new class of geographical partitioning problems in which the population is heterogeneous, and it is necessary to ensure fair representation for each group at each facility. We prove that the optimal solution is a novel generalization of the additively weighted Voronoi diagram, and we propose a simple and efficient algorithm to compute it, thus resolving an open question dating back to Dvoretzky et al. (1951). The efficacy and potential for practical insight of the approach are demonstrated in a realistic case study involving seven demographic groups and $78$ district offices.

Related papers

• Demographic-Agnostic Fairness without Harm [15.171262544838337]
  Machine learning algorithms are increasingly used in social domains to make predictions about humans.<n>There is a growing concern that these algorithms may exhibit biases against certain social groups.<n>We propose a novel textitdemographic-agnostic fairness without harm optimization algorithm.
  arXiv  Detail & Related papers  (2025-09-28T21:23:32Z)
• Accelerating Spectral Clustering under Fairness Constraints [56.865810822418744]
  We present a new efficient method for fair spectral clustering (Fair SC) by casting the Fair SC problem within the difference of convex functions (DC) framework.<n>We show that each associated subproblem can be solved efficiently, resulting in higher computational efficiency compared to prior work.
  arXiv  Detail & Related papers  (2025-06-09T18:46:27Z)
• Fairness of Deep Ensembles: On the interplay between per-group task difficulty and under-representation [9.11104048176204]
  Ensembling is commonly regarded as an effective way to improve the general performance of models in machine learning.<n>We show how a simple and straightforward method is able to mitigate disparities, particularly benefiting under-performing subgroups.<n>We analyzed the interplay between two factors which may result in biases: sub-group under-representation and the inherent difficulty of the task for each group.
  arXiv  Detail & Related papers  (2025-01-24T14:54:01Z)
• What Constitutes a Less Discriminatory Algorithm? [2.842548870013324]
  We argue that formal LDA definitions face fundamental challenges when they attempt to evaluate and compare predictive models in the absence of held-out data.<n>We put forward a framework in which both firms and plaintiffs can search for alternative models that comport with societal goals.
  arXiv  Detail & Related papers  (2024-12-24T03:49:48Z)
• Fair and skill-diverse student group formation via constrained k-way graph partitioning [65.29889537564455]
  This work introduces an unsupervised algorithm for fair and skill-diverse student group formation. The skill sets of students are determined using unsupervised dimensionality reduction of course mark data via the Laplacian eigenmap. The problem is formulated as a constrained graph partitioning problem, whereby the diversity of skill sets in each group are maximised.
  arXiv  Detail & Related papers  (2023-01-12T14:02:49Z)
• Fair Group-Shared Representations with Normalizing Flows [68.29997072804537]
  We develop a fair representation learning algorithm which is able to map individuals belonging to different groups in a single group. We show experimentally that our methodology is competitive with other fair representation learning algorithms.
  arXiv  Detail & Related papers  (2022-01-17T10:49:49Z)
• MultiFair: Multi-Group Fairness in Machine Learning [52.24956510371455]
  We study multi-group fairness in machine learning (MultiFair) We propose a generic end-to-end algorithmic framework to solve it. Our proposed framework is generalizable to many different settings.
  arXiv  Detail & Related papers  (2021-05-24T02:30:22Z)
• Fairmandering: A column generation heuristic for fairness-optimized political districting [0.0]
  American winner-take-all congressional district system empowers politicians to engineer electoral outcomes by manipulating district boundaries. Existing computational solutions mostly focus on drawing unbiased maps by ignoring political and demographic input, and instead simply optimize for compactness. We claim that this is a flawed approach because compactness and fairness are qualities, and introduce a scalable two-stage method to explicitly optimize for arbitrary piecewise-linear definitions of fairness.
  arXiv  Detail & Related papers  (2021-03-21T19:22:42Z)
• A Pairwise Fair and Community-preserving Approach to k-Center Clustering [34.386585230600716]
  Clustering is a foundational problem in machine learning with numerous applications. We define two new types of fairness in the clustering setting, pairwise fairness and community preservation.
  arXiv  Detail & Related papers  (2020-07-14T22:32:27Z)
• Distributional Individual Fairness in Clustering [7.303841123034983]
  We introduce a framework for assigning individuals, embedded in a metric space, to probability distributions over a bounded number of cluster centers. We provide an algorithm for clustering with $p$-norm objective and individual fairness constraints with provable approximation guarantee.
  arXiv  Detail & Related papers  (2020-06-22T20:02:09Z)
• Mitigating Face Recognition Bias via Group Adaptive Classifier [53.15616844833305]
  This work aims to learn a fair face representation, where faces of every group could be more equally represented. Our work is able to mitigate face recognition bias across demographic groups while maintaining the competitive accuracy.
  arXiv  Detail & Related papers  (2020-06-13T06:43:37Z)
• Adaptive Region-Based Active Learning [57.78835999208091]
  We present a new active learning algorithm that adaptively partitions the input space into a finite number of regions. We prove theoretical guarantees for both the generalization error and the label complexity of our algorithm. We report the results of an extensive suite of experiments on several real-world datasets.
  arXiv  Detail & Related papers  (2020-02-18T03:16:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.