💻 computer science

Redistricting from the Bottom Up: Sampling Communities of Interest with Differential Privacy

This paper proposes a differentially private redistricting framework using the marked edge walk and exponential mechanism to robustly incorporate community of interest testimonies into Missouri's district maps, demonstrating that such COI-informed sampling outperforms uninformed baselines and the enacted plan while resisting adversarial manipulation.

Original authors: Atticus McWhorter, Caroline Hammond, Nianqiao Phyllis Ju, Daryl DeFord

Published 2026-06-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Atticus McWhorter, Caroline Hammond, Nianqiao Phyllis Ju, Daryl DeFord

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a city trying to draw the lines for its neighborhoods so that everyone gets a fair say in who represents them. Usually, politicians draw these lines themselves, often twisting them to give their own team an unfair advantage. To fix this, some places use Independent Redistricting Commissions (IRCs). These are groups of regular citizens and experts who try to draw fair maps.

However, there's a catch: these commissions ask the public for input. They ask, "What areas should stay together because they share common interests?" (These are called Communities of Interest, or COIs).

The problem is that bad actors can game this system. Imagine a political party hiring a hundred people to all submit fake stories saying, "We are a community that must stay together!" If the commission listens too closely to these fake stories, they might draw a map that actually helps the party rig the election, even though it looks like it's listening to the people.

The Paper's Solution: The "Privacy Shield"

This paper proposes a clever mathematical trick called Differential Privacy to stop this manipulation. Think of it like a "noise machine" for data.

The Analogy: Imagine you are trying to hear a whisper in a crowded room. If you listen to every single voice perfectly, a loud, fake shout from a bad actor can drown out the real whispers. But, if you put on headphones that add a tiny bit of static (noise) to everything, you can still hear the general pattern of the crowd, but one loud, fake shout won't change what you hear.
The Goal: The authors want to build a map that respects the general wishes of the community (the real COIs) without letting any single testimony (real or fake) control the outcome.

How They Did It: The "Random Walk" and the "Score"

The researchers used a computer program to generate thousands of possible maps. But instead of just picking one, they used a method called a Markov Chain Monte Carlo (MCMC) walk.

The Analogy: Imagine a hiker trying to find the best view in a mountain range. Instead of just standing still, the hiker takes steps. Sometimes they step up, sometimes down.
The Twist: They gave the hiker a "scorecard."
1. Compactness: The map shouldn't look like a weird, stretched-out snake. It should be a nice, round blob.
2. Community Score: The map should try to keep the "Communities of Interest" (the areas people said should stay together) inside the same neighborhood.

The hiker (the computer algorithm) tries to find maps with the highest scores. But here is the privacy part: they added a rule that says, "If one person changes their story, the hiker shouldn't change their path too drastically." This ensures that even if a bad actor submits a fake story, the final map won't bend to accommodate it.

They tested two ways to score the "Community" part:

The "All-or-Nothing" Score: Did the map keep the whole group together? If yes, great points. If the map cut the group in half, zero points.
The "Weighted" Score: Even if the group was cut, how much of the group is still together? This is a bit more forgiving and nuanced.

What They Found (The Results)

They tested this on real data from Missouri, using 808 actual stories from citizens.

It Works Better Than the Status Quo: The maps generated by their "privacy shield" method were better at keeping real communities together than the map that was actually passed by the state legislature.
It Stops the Fakes: They ran a "stress test" where they replaced a real group of stories with nine fake, coordinated fake stories.
- When they used the "All-or-Nothing" score, the computer actually ignored the fake group more as it got "louder" (higher privacy budget), sacrificing the fake group to save the real ones.
- When they used the "Weighted" score, the computer tried to keep the fake group together, but only up to a point. The system didn't let the fake group hijack the whole map.
Surprising Side Effect: By trying to keep these communities together, the method actually spread out minority and Democratic voters more evenly across different districts. Instead of packing them all into one district (which can sometimes hurt their overall power), the method helped create more districts where they had a strong voice.

The Bottom Line

This paper shows that you can use math to build a "shield" around the redistricting process. It allows commissions to listen to the public without being held hostage by liars or coordinated groups trying to rig the system. It's like having a judge who listens to every witness but has a rule that says, "No single witness, no matter how loud, can change the verdict on their own."

The authors admit this isn't a magic wand that solves everything forever, but it's a powerful new tool to make the process fairer and more resistant to cheating.

Technical Summary: Redistricting from the Bottom Up with Differential Privacy

Problem Statement
Independent Redistricting Commissions (IRCs) are increasingly utilized to facilitate bottom-up redistricting, aiming to insulate the process from partisan manipulation. However, the public testimony processes used to gather "Communities of Interest" (COI) data are vulnerable to adversarial attacks. Historical examples from California and Florida demonstrate that political operatives can coordinate groups to submit scripted or proxy testimonies to manipulate district boundaries. While ensemble methods (Markov Chain Monte Carlo) are effective for detecting top-down gerrymandering, they lack a mechanism to incorporate COI testimony in a way that is robust to such adversarial inputs. The core challenge is to design a redistricting algorithm that incorporates public testimony data without allowing any single testimony or coordinated group to disproportionately dictate the outcome.

Methodology
The authors propose a framework combining Differential Privacy (DP) with ensemble sampling to generate redistricting plans that respect COI testimonies while bounding the influence of individual data points.

Data Representation:
- The state is modeled as a graph $G=(V, E)$ where vertices are census block groups and edges connect adjacent units.
- Testimonies are encoded as binary vectors indicating which block groups a community wishes to keep together.
- Testimonies are aggregated into geographic clusters based on proximity.
Score Functions:
The authors introduce two distinct scoring functions to measure COI preservation:
- Testimony Score ( $s_t$ ): Measures the proportion of individual testimonies that remain entirely within a single district. This is a binary "all-or-nothing" metric.
- Cluster Score ( $s_c$ ): Measures the fraction of total cluster weight preserved in the "best" district for each cluster. This allows for partial preservation and is more granular.
Sampling Mechanism:
- The authors utilize the Exponential Mechanism to sample redistricting plans from a target distribution proportional to $\exp(-\frac{\epsilon}{2\Delta(s)} s(t, \xi))$ , where $s$ is the chosen score function and $\Delta(s)$ is its sensitivity.
- To sample from this distribution, they employ the Marked Edge Walk (MEW), a lifted Markov Chain Monte Carlo (MCMC) algorithm. MEW operates on tuples of spanning trees and marked edges, allowing it to traverse the state space more efficiently than local flip-walks and converge to distributions independent of spanning tree structures.
- The target distribution also includes a compactness term (Gaussian over cut edges) centered on the enacted plan's value to ensure geometric validity.
Privacy Framework:
- The system is defined as $(\epsilon, \delta)$ -differentially private. The inclusion or exclusion of a single testimony (or a neighboring dataset differing by one testimony) results in a bounded change in the probability of any output plan.
- The sensitivity $\Delta(s)$ is calculated for both score functions. The testimony score has a sensitivity of $1/T$ (where $T$ is the number of testimonies), while the cluster score has a higher sensitivity due to the aggregation of weights.

Key Results
The method was applied to Missouri's mid-cycle redistricting using 808 COI testimonies.

Performance vs. Baseline: COI-informed sampling consistently outperformed an uninformed baseline (sampling based solely on compactness) and the enacted plan. The enacted plan scored 0.62 on the testimony score and 0.71 on the cluster score, while the DP-sampled distributions achieved higher scores as the privacy budget ( $\epsilon$ ) increased.
Privacy-Utility Trade-off: As $\epsilon$ increased, the sampled plans shifted toward higher COI preservation scores. However, at very high $\epsilon$ , the chain struggled to mix because the exponential mechanism assigned vanishingly small probabilities to proposals that decreased the score.
Score Function Comparison:
- The Testimony Score offered stronger formal privacy guarantees (lower sensitivity) but exhibited counterintuitive "sacrifice" behavior: at high $\epsilon$ , the sampler would split some testimonies more frequently to preserve others, due to the discrete nature of the score.
- The Cluster Score provided more intuitive results and better mixing at higher budgets but offered weaker formal privacy guarantees due to higher sensitivity.
Adversarial Robustness: In an experiment where a cluster of 9 testimonies was replaced with adversarial data covering a different geographic area:
- Under the Cluster Score, the adversarial cluster was preserved at rates consistent with the baseline at low $\epsilon$ , and increasingly preserved as $\epsilon$ rose.
- Under the Testimony Score, the adversarial testimonies were increasingly split as $\epsilon$ rose, effectively being sacrificed to preserve the integrity of the remaining 800+ testimonies.
- The results suggest the method is robust to small-scale coordinated attacks, performing better in practice than formal group privacy bounds (which degrade linearly with the number of attackers) might imply.
Demographic Impact: Contrary to the intuition that preserving COIs leads to "packing" minority or Democratic voters into single districts, the results showed that stronger COI preservation in Missouri tended to spread minority and Democratic representation more evenly across the top three districts. This was attributed to the geographic separation of Missouri's two major urban centers (St. Louis and Kansas City); keeping local communities intact prevented the dilution of representation in Kansas City, which was split in the enacted plan.

Significance and Claims
The paper claims to offer a novel framework for "bottom-up" redistricting that balances the incorporation of public testimony with robustness against adversarial manipulation.

Robustness: The primary contribution is demonstrating that differential privacy can be applied to the output distribution of redistricting plans to limit the influence of any single testimony or small coordinated group, without discarding the data entirely.
Practical Application: The study validates the approach using real-world data (Missouri 2021 testimonies) and a specific MCMC algorithm (MEW) capable of sampling from non-standard target distributions.
Limitations: The authors modestly note that the method does not solve the problem entirely; sufficiently large coordinated attacks could still overwhelm the mechanism due to the linear degradation of group privacy. Furthermore, the theoretical mixing guarantees for MEW are limited, requiring reliance on empirical convergence diagnostics. The approach also depends on the availability of structured testimony data (e.g., via platforms like Districtr) and requires careful selection of privacy parameters and clustering methods.

In conclusion, the paper posits that while IRCs are a promising tool, they require mathematical safeguards against manipulation. The proposed DP-MEW framework provides a quantifiable bound on the influence of adversarial inputs, allowing for the creation of redistricting plans that are both informed by community interests and resilient to subversion.

Technical Summary: Redistricting from the Bottom Up with Differential Privacy

More like this