Fairmandering: A column generation heuristic for fairness-optimized political districting

• URL: http://arxiv.org/abs/2103.11469v2
• Date: Fri, 25 Jun 2021 20:48:15 GMT
• Title: Fairmandering: A column generation heuristic for fairness-optimized political districting
• Authors: Wes Gurnee and David B. Shmoys
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The 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 orthogonal qualities, and introduce a scalable two-stage method to explicitly optimize for arbitrary piecewise-linear definitions of fairness. The first stage is a randomized divide-and-conquer column generation heuristic which produces an exponential number of distinct district plans by exploiting the compositional structure of graph partitioning problems. This district ensemble forms the input to a master selection problem to choose the districts to include in the final plan. Our decoupled design allows for unprecedented flexibility in defining fairness-aligned objective functions. The pipeline is arbitrarily parallelizable, is flexible to support additional redistricting constraints, and can be applied to a wide array of other regionalization problems. In the largest ever ensemble study of congressional districts, we use our method to understand the range of possible expected outcomes and the implications of this range on potential definitions of fairness.

Related papers

• A-FedPD: Aligning Dual-Drift is All Federated Primal-Dual Learning Needs [57.35402286842029]
  We propose a novel Aligned Dual Dual (A-FedPD) method, which constructs virtual dual align global and local clients. We provide a comprehensive analysis of the A-FedPD method's efficiency for those protracted unicipated security consensus.
  arXiv  Detail & Related papers  (2024-09-27T17:00:32Z)
• The Traveling Mailman: Topological Optimization Methods for User-Centric Redistricting [0.0]
  This study introduces a new districting approach using the US Postal Service network to measure community connectivity. We combine Topological Data Analysis with Markov Chain Monte Carlo methods to assess district boundaries' impact on community integrity.
  arXiv  Detail & Related papers  (2024-07-28T16:50:45Z)
• Drawing Competitive Districts in Redistricting [1.5654305985353367]
  We discuss the problem of drawing plans with at least a fixed number of competitive districts. We show that the task of drawing plans with competitive districts is NP-hard, even on very natural instances. We show that a simple hill-climbing procedure can in practice find districtings on real states in which all the districts are competitive.
  arXiv  Detail & Related papers  (2024-04-17T00:09:41Z)
• Multiscale Parallel Tempering for Fast Sampling on Redistricting Plans [1.1233768932957773]
  A persuasive method is to compare the plan with an ensemble of neutrally drawn redistricting plans. To audit the partisan difference between the ensemble and a given plan, one must ensure that the non-partisan criteria are matched. In this work, we generate a multiscale parallel tempering approach that makes local moves at each scale.
  arXiv  Detail & Related papers  (2024-01-30T21:33:05Z)
• Proportional Fairness in Obnoxious Facility Location [70.64736616610202]
  We propose a hierarchy of distance-based proportional fairness concepts for the problem. We consider deterministic and randomized mechanisms, and compute tight bounds on the price of proportional fairness. We prove existence results for two extensions to our model.
  arXiv  Detail & Related papers  (2023-01-11T07:30:35Z)
• Spanning tree methods for sampling graph partitions [0.7658085223797904]
  A districting plan can be viewed as a balanced partition of a graph into connected subsets. RevReCom converges to the simple, natural distribution that ReCom was originally designed to approximate.
  arXiv  Detail & Related papers  (2022-10-04T06:18:33Z)
• Mathematically Quantifying Non-responsiveness of the 2021 Georgia Congressional Districting Plan [3.097163558730473]
  We use a Metropolized-sampling technique through a parallel tempering method combined with ReCom. We develop these improvements through the first case study of district plans in Georgia. Our analysis projects that any election in Georgia will reliably elect 9 Republicans and 5 Democrats under the enacted plan.
  arXiv  Detail & Related papers  (2022-03-13T02:58:32Z)
• Supervised learning of sheared distributions using linearized optimal transport [64.53761005509386]
  In this paper we study supervised learning tasks on the space of probability measures. We approach this problem by embedding the space of probability measures into $L2$ spaces using the optimal transport framework. Regular machine learning techniques are used to achieve linear separability.
  arXiv  Detail & Related papers  (2022-01-25T19:19:59Z)
• Crowd Counting via Perspective-Guided Fractional-Dilation Convolution [75.36662947203192]
  This paper proposes a novel convolution neural network-based crowd counting method, termed Perspective-guided Fractional-Dilation Network (PFDNet) By modeling the continuous scale variations, the proposed PFDNet is able to select the proper fractional dilation kernels for adapting to different spatial locations. It significantly improves the flexibility of the state-of-the-arts that only consider the discrete representative scales.
  arXiv  Detail & Related papers  (2021-07-08T07:57:00Z)
• Partition-Guided GANs [63.980473635585234]
  We design a partitioner that breaks the space into smaller regions, each having a simpler distribution, and training a different generator for each partition. This is done in an unsupervised manner without requiring any labels. Experimental results on various standard benchmarks show that the proposed unsupervised model outperforms several recent methods.
  arXiv  Detail & Related papers  (2021-04-02T00:06:53Z)
• Receptive Multi-granularity Representation for Person Re-Identification [46.99913453669368]
  This paper proposes a receptive multi-granularity learning approach to facilitate stripe-based feature learning. By two-branch network architecture, different scales of discriminative identity representation can be learned. Our approach achieves a state-of-the-art accuracy of 96.2%@Rank-1 or 90.0%@mAP on the challenging Market-1501 benchmark.
  arXiv  Detail & Related papers  (2020-08-31T09:26:08Z)

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.