Balanced Spanning Tree Distributions Have Separation Fairness

• URL: http://arxiv.org/abs/2509.15137v1
• Date: Thu, 18 Sep 2025 16:48:43 GMT
• Title: Balanced Spanning Tree Distributions Have Separation Fairness
• Authors: Harry Chen, Kamesh Munagala, Govind S. Sankar,
• Abstract summary: We introduce the notion of separation fairness, which asks whether adjacent geographic units are separated with at most a constant probability (bounded away from one) in sampled redistricting plans.<n>We prove that a smooth variant of the balanced spanning tree distribution satisfies separation fairness.<n>Our results also provide theoretical support for popular MCMC methods like ReCom, suggesting that they maintain fairness at a granular level in the sampling process.
• Score: 9.543463140987361
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Sampling-based methods such as ReCom are widely used to audit redistricting plans for fairness, with the balanced spanning tree distribution playing a central role since it favors compact, contiguous, and population-balanced districts. However, whether such samples are truly representative or exhibit hidden biases remains an open question. In this work, we introduce the notion of separation fairness, which asks whether adjacent geographic units are separated with at most a constant probability (bounded away from one) in sampled redistricting plans. Focusing on grid graphs and two-district partitions, we prove that a smooth variant of the balanced spanning tree distribution satisfies separation fairness. Our results also provide theoretical support for popular MCMC methods like ReCom, suggesting that they maintain fairness at a granular level in the sampling process. Along the way, we develop tools for analyzing loop-erased random walks and partitions that may be of independent interest.

Related papers

• Learning Centre Partitions from Summaries [0.21748200848556343]
  Homogeneity of parameters across centres is often violated, motivating methods that both emphtest for equality and emphlearn centre groupings before estimation.<n>We develop a sequential, test-driven emphClusters-of-Centres (CoC) algorithm that merges centres (or blocks) only when equality is not rejected.
  arXiv  Detail & Related papers  (2025-09-19T18:25:06Z)
• Fine-Grained Bias Exploration and Mitigation for Group-Robust Classification [11.525201208566925]
  Bias Exploration via Overfitting (BEO) captures each distribution in greater detail by modeling it as a mixture of latent groups.<n>We introduce a fine-grained variant of CCDB, termed FG-CCDB, which performs more precise distribution matching and balancing within each group.<n>Our method performs on par with bias-supervised approaches on binary classification tasks and significantly outperforms them in highly biased multi-class scenarios.
  arXiv  Detail & Related papers  (2025-05-11T04:01:34Z)
• Enhanced Importance Sampling through Latent Space Exploration in Normalizing Flows [69.8873421870522]
  importance sampling is a rare event simulation technique used in Monte Carlo simulations.<n>We propose a method for more efficient sampling by updating the proposal distribution in the latent space of a normalizing flow.
  arXiv  Detail & Related papers  (2025-01-06T21:18:02Z)
• Theory on Score-Mismatched Diffusion Models and Zero-Shot Conditional Samplers [49.97755400231656]
  We present the first performance guarantee with explicit dimensional dependencies for general score-mismatched diffusion samplers.<n>We show that score mismatches result in an distributional bias between the target and sampling distributions, proportional to the accumulated mismatch between the target and training distributions.<n>This result can be directly applied to zero-shot conditional samplers for any conditional model, irrespective of measurement noise.
  arXiv  Detail & Related papers  (2024-10-17T16:42:12Z)
• 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)
• Standardized Interpretable Fairness Measures for Continuous Risk Scores [4.192037827105842]
  We propose a standardized version of fairness measures for continuous scores with a reasonable interpretation based on the Wasserstein distance. Our measures are easily computable and well suited for quantifying and interpreting the strength of group disparities as well as for comparing biases across different models, datasets, or time points.
  arXiv  Detail & Related papers  (2023-08-22T12:01:49Z)
• Unsupervised Hashing with Similarity Distribution Calibration [127.34239817201549]
  Unsupervised hashing methods aim to preserve the similarity between data points in a feature space by mapping them to binary hash codes. These methods often overlook the fact that the similarity between data points in the continuous feature space may not be preserved in the discrete hash code space. The similarity range is bounded by the code length and can lead to a problem known as similarity collapse. This paper introduces a novel Similarity Distribution (SDC) method to alleviate this problem.
  arXiv  Detail & Related papers  (2023-02-15T14:06:39Z)
• Disentanglement of Correlated Factors via Hausdorff Factorized Support [53.23740352226391]
  We propose a relaxed disentanglement criterion - the Hausdorff Factorized Support (HFS) criterion - that encourages a factorized support, rather than a factorial distribution. We show that the use of HFS consistently facilitates disentanglement and recovery of ground-truth factors across a variety of correlation settings and benchmarks.
  arXiv  Detail & Related papers  (2022-10-13T20:46:42Z)
• 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)
• Compact Redistricting Plans Have Many Spanning Trees [39.779544988993294]
  In the design and analysis of political redistricting maps, it is often useful to be able to sample from the space of all partitions of the graph of census blocks into connected subgraphs of equal population. In this paper, we establish an inverse exponential relationship between the total length of the boundaries separating districts and the probability that such a map will be sampled.
  arXiv  Detail & Related papers  (2021-09-27T23:36:01Z)
• Decentralized Local Stochastic Extra-Gradient for Variational Inequalities [125.62877849447729]
  We consider distributed variational inequalities (VIs) on domains with the problem data that is heterogeneous (non-IID) and distributed across many devices. We make a very general assumption on the computational network that covers the settings of fully decentralized calculations. We theoretically analyze its convergence rate in the strongly-monotone, monotone, and non-monotone settings.
  arXiv  Detail & Related papers  (2021-06-15T17:45:51Z)
• Distributional Reinforcement Learning via Moment Matching [54.16108052278444]
  We formulate a method that learns a finite set of statistics from each return distribution via neural networks. Our method can be interpreted as implicitly matching all orders of moments between a return distribution and its Bellman target. Experiments on the suite of Atari games show that our method outperforms the standard distributional RL baselines.
  arXiv  Detail & Related papers  (2020-07-24T05:18:17Z)
• Global Distance-distributions Separation for Unsupervised Person Re-identification [93.39253443415392]
  Existing unsupervised ReID approaches often fail in correctly identifying the positive samples and negative samples through the distance-based matching/ranking. We introduce a global distance-distributions separation constraint over the two distributions to encourage the clear separation of positive and negative samples from a global view. We show that our method leads to significant improvement over the baselines and achieves the state-of-the-art performance.
  arXiv  Detail & Related papers  (2020-06-01T07:05:39Z)

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.