Agentmandering: A Game-Theoretic Framework for Fair Redistricting via Large Language Model Agents

AI summary

Overview

Research area: Computational redistricting, game theory, and large language model (LLM) agents applied to political fairness.

Technical level: Advanced. The paper combines graph partitioning, Markov Chain Monte Carlo (MCMC) sampling algorithms, the game-theoretic Choose-and-Freeze protocol, and prompt-driven LLM agents.

Scope: The paper introduces Agentmandering, a framework that turns the theoretical Choose-and-Freeze negotiation protocol into a working redistricting method by having two partisan LLM agents alternately choose and freeze districts from small sets of ReCom-generated candidate maps, then evaluates it on post-2020 U.S. Census data across all states.

What This Paper Is About

Existing computational redistricting tools mainly generate large ensembles of legally valid maps, but they say nothing about how a map gets selected — leaving room for partisan actors to cherry-pick technically compliant maps that happen to favor them. The authors argue that satisfying formal constraints is not the same as being fair when the selection process itself can be gamed, and they show that four common fairness metrics can score two plans almost identically while producing very different electoral outcomes. Their goal is to build a procedure that is not only compliant but also robust against strategic selection, by implementing the game-theoretic Choose-and-Freeze protocol (Pegden et al. 2017) with LLM agents.

Key Contributions

1. A new paradigm for implementing game-theoretic protocols with LLM agents. The authors position this as bringing abstract fairness principles out of theory and into practical computational redistricting tools.

2. The Agentmandering framework itself. It combines the Choose-and-Freeze protocol with LLM agents so that redistricting becomes a turn-based strategic negotiation between a Republican agent and a Democratic agent, constraining partisan manipulation.

3. Empirical demonstration of fairness and stability. On post-2020 U.S. Census data across all states, Agentmandering reports 2 to 3 orders of magnitude lower variance than existing methods, along with reduced partisan bias and unfairness, with the strongest robustness in swing-state scenarios.

4. Robustness analyses. Ablations cover candidate-set size, agent ordering, choice of candidate generator, choice of LLM, and the number of repeated runs, alongside timing measurements for every state.

Main Findings

• Much lower variance than standard baselines. The abstract and results report variance 2 to 3 orders of magnitude lower than other methods, which the authors describe as reduced metric fluctuation and less room for strategic manipulation.

• Best or near-best on Partisan Bias and Unfairness. Across the seven swing states in Table 1 (Arizona, Georgia, Michigan, North Carolina, Nevada, Pennsylvania, Wisconsin), Agentmandering performs best or near-best on these two metrics.

• Lowest Population Deviation, slightly weaker compactness. All computational methods beat the enacted CD-2020 plans on Population Deviation (PD) and Polsby-Popper Score (PPS), revealing population imbalance and geometric distortion in real-world plans. Agentmandering achieves the lowest PD but slightly underperforms on PPS because of its irregular boundaries.

• Only method to recover the correct partisan direction in Wisconsin. In Table 1, Wisconsin's Bias findings for Agentmandering are marked in italics to indicate they match the sign of the real situation; the paper states Agentmandering is the only method to recover the correct partisan direction there.

• LLM agents beat rule-based decision rules. Compared to rule-based variants that maximize partisan bias, minimize population deviation, or maximize compactness during the choose and freeze steps, Agentmandering achieves a lower Unfairness score than all rule-based variants.

• Stability comes from the protocol, not just the agents. The rule-based variants also show standard deviations 2 to 3 orders of magnitude lower than traditional baselines, which the authors take as evidence that the overall stability of Agentmandering primarily stems from the Choose-and-Freeze protocol.

• Results are consistent across many different LLMs. Gemini 2.5 Pro, GPT-4o-mini, GPT-o3-mini, Deepseek-R1, Deepseek-V3, Claude-3.7, LLaMA-3-70B, Mixtral-3.1, and Qwen all achieve similar Unfairness scores across states, including models from the United States, Europe, and China. The authors read this as robustness to differences in model origin, training data, or political orientation.

• Larger candidate pools help, with diminishing returns. Increasing the candidate set size across 10, 50, 100, 200, and 500 improves population deviation, partisan bias, and compactness, but returns diminish beyond 100, so 100 became the default.

• Agent ordering makes little difference. Running with the Republican agent first versus the Democratic agent first produces only marginal variation in fairness metrics, with no systematic advantage, which the authors attribute to the alternating structure of the protocol.

• Candidate generator choice matters little. ReCom and Flip perform similarly on Partisan Bias, Unfairness, and Polsby-Popper Score, though Flip performs slightly better on Population Deviation.

• Stable across repeated runs on Pennsylvania. Running 10, 50, 100, 200, and 500 independent runs keeps both means and standard deviations remarkably stable across metrics.

• Practical runtime. With Gemini 2.5 Pro and ReCom using 100 candidate maps, most full runs complete in under 30 seconds. Larger states take longer — California 124.43 s, Texas 81.88 s, Florida 43.14 s, New York 41.59 s — and single-district states (AK, DE, ND, SD, VT, WY) are excluded because no redistricting is required.

Methodology in Plain English

The state is modeled as an adjacency graph of population units, and the task is to cut it into contiguous districts that are balanced in population and satisfy legal constraints. Rather than drawing maps directly, Agentmandering stages a negotiation between two LLM agents, one representing Republicans and one representing Democrats, each given a state-specific political profile covering historical voting trends, demographic composition from Census data, and partisan geography.

The game follows the Choose-and-Freeze protocol over N rounds, where N is the number of districts in the state. At each round, a party-agnostic candidate generator produces a small set of c feasible maps over the still-unpartitioned region; in this work that generator is the ReCom algorithm. The choosing agent picks one map from that set, and the opposing agent then permanently freezes one district from the chosen map. The frozen district is removed from the unassigned region and the process recurses on the remainder. The choose and freeze roles switch each round, so neither side can unilaterally determine the final map.

Both the choose step and the freeze step are prompt-driven functions that ask the agent to reason about partisan composition and long-term party interest under legal constraints. Because a run covers t districts and draws c candidates per round, a single run uses roughly c × t samples — for example, about 700 samples for Alabama with t = 7 and c = 100, or 7000 across 10 repeats. Baselines are allowed to generate the same total number of plans, but they produce complete maps in one step rather than incrementally through interaction.

Evaluation uses four metrics: Population Deviation, Polsby-Popper Score (reported as average and minimum), Partisan Bias (positive favors Democrats, negative favors Republicans, zero is fair), and Local Unfairness, which measures the proportion of residents whose preferred party did not win in their district. The main experiments use Gemini 2.5 Pro (gemini-2.5-pro-preview-05-06) with temperature set to 0, ReCom as the candidate generator, and comparisons against ReCom, Merge-Split, FlipMCMC, and SMCredist as well as the enacted CD-2020 plans. District geography comes from data.census.gov and voting data from the Harvard Dataverse electionscience collection.

Why This Matters

Impact on research. The paper argues that generating legally valid maps is not enough when the selection step can be manipulated, and it supplies a concrete way to instantiate a proven fairness protocol that had previously been only a theoretical guide for human negotiation. It also extends LLM-agent research from games and economic settings into the high-stakes domain of political fairness.

Real-world applications:

• State and independent redistricting commissions could use the protocol as a structured, transparent procedure that does not require an external arbiter or special master to draw the map.
• Courts and analysts could use the low-variance outcome distribution as a stability reference when judging whether a challenged plan sits far from a procedurally fair baseline.
• Civic technology groups could build public-facing tools that let two opposing parties negotiate over a shared candidate pool.
• Researchers studying partisan bias could use the framework as a simulation testbed, since the vote data and candidate maps are drawn from public Census and election sources.

Industry relevance. Institutions that deploy LLMs can substitute or upgrade models without degrading performance, according to the cross-model experiment, and the reported per-state runtimes — mostly under 30 seconds — suggest the approach is practical for large-scale deployment across all U.S. states. The code is released at https://github.com/Lihaogx/AgentMandering.

Future Directions

• Extending the framework to multi-party systems, where fairness and strategy must be redefined to accommodate diverse party dynamics, coalition effects, and proportionality requirements — the authors name this explicitly as future work.
• Understanding why underlying LLM differences (origin, training data, political orientation) do not change outcomes, given that the paper attributes the consistency to structural guidance from the protocol rather than testing the mechanism directly.
• Determining how much the candidate generator matters in general, since the reported comparison between ReCom and Flip covers only two generators and leaves the tie-breaking role of the generator pool partly open.
• Testing whether the approach generalizes beyond the post-2020 U.S. Census setting and the 2020 presidential election voting data used here.

Target Audience

Readers who will benefit most are researchers in computational social choice, algorithmic fairness, and AI for social good; political scientists and legal scholars working on gerrymandering and redistricting reform; and LLM-agent researchers interested in how game-theoretic protocols shape agent behavior in high-stakes settings. Practitioners building redistricting or civic-engagement tools will find the protocol and runtime results directly useful, while readers looking for a beginner-level introduction to redistricting algorithms will need background in graph partitioning and Monte Carlo sampling to follow the baseline comparisons.

Authors’ abstract

Redistricting plays a central role in shaping how votes are translated into political power. While existing computational methods primarily aim to generate large ensembles of legally valid districting plans, they often neglect the strategic dynamics involved in the selection process. This oversight creates opportunities for partisan actors to cherry-pick maps that, while technically compliant, are politically advantageous. Simply satisfying formal constraints does not ensure fairness when the selection process itself can be manipulated. We propose \textbf{Agentmandering}, a framework that reimagines redistricting as a turn-based negotiation between two agents representing opposing political interests. Drawing inspiration from game-theoretic ideas, particularly the \textit{Choose-and-Freeze} protocol, our method embeds strategic interaction into the redistricting process via large language model (LLM) agents. Agents alternate between selecting and freezing districts from a small set of candidate maps, gradually partitioning the state through constrained and interpretable choices. Evaluation on post-2020 U.S. Census data across all states shows that Agentmandering significantly reduces partisan bias and unfairness, while achieving 2 to 3 orders of magnitude lower variance than standard baselines. These results demonstrate both fairness and stability, especially in swing-state scenarios. Our code is available at https://github.com/Lihaogx/AgentMandering.