Multiscale Parallel Tempering for Fast Sampling on Redistricting Plans
- URL: http://arxiv.org/abs/2401.17455v1
- Date: Tue, 30 Jan 2024 21:33:05 GMT
- Title: Multiscale Parallel Tempering for Fast Sampling on Redistricting Plans
- Authors: Gabriel Chuang, Gregory Herschlag, Jonathan C. Mattingly
- Abstract summary: 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.
- Score: 1.1233768932957773
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: When auditing a redistricting plan, a persuasive method is to compare the
plan with an ensemble of neutrally drawn redistricting plans. Ensembles are
generated via algorithms that sample distributions on balanced graph
partitions. To audit the partisan difference between the ensemble and a given
plan, one must ensure that the non-partisan criteria are matched so that we may
conclude that partisan differences come from bias rather than, for example,
levels of compactness or differences in community preservation. Certain
sampling algorithms allow one to explicitly state the policy-based probability
distribution on plans, however, these algorithms have shown poor mixing times
for large graphs (i.e. redistricting spaces) for all but a few specialized
measures. In this work, we generate a multiscale parallel tempering approach
that makes local moves at each scale. The local moves allow us to adopt a wide
variety of policy-based measures. We examine our method in the state of
Connecticut and succeed at achieving fast mixing on a policy-based distribution
that has never before been sampled at this scale. Our algorithm shows promise
to expand to a significantly wider class of measures that will (i) allow for
more principled and situation-based comparisons and (ii) probe for the typical
partisan impact that policy can have on redistricting.
Related papers
- Information Capacity Regret Bounds for Bandits with Mediator Feedback [55.269551124587224]
We introduce the policy set capacity as an information-theoretic measure for the complexity of the policy set.
Adopting the classical EXP4 algorithm, we provide new regret bounds depending on the policy set capacity.
For a selection of policy set families, we prove nearly-matching lower bounds, scaling similarly with the capacity.
arXiv Detail & Related papers (2024-02-15T19:18:47Z) - Off-Policy Evaluation for Large Action Spaces via Policy Convolution [60.6953713877886]
Policy Convolution family of estimators uses latent structure within actions to strategically convolve the logging and target policies.
Experiments on synthetic and benchmark datasets demonstrate remarkable mean squared error (MSE) improvements when using PC.
arXiv Detail & Related papers (2023-10-24T01:00:01Z) - Policy Dispersion in Non-Markovian Environment [53.05904889617441]
This paper tries to learn the diverse policies from the history of state-action pairs under a non-Markovian environment.
We first adopt a transformer-based method to learn policy embeddings.
Then, we stack the policy embeddings to construct a dispersion matrix to induce a set of diverse policies.
arXiv Detail & Related papers (2023-02-28T11:58:39Z) - 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) - Measuring Geometric Similarity Across Possible Plans for Automated
Redistricting [0.0]
This paper briefly introduces an interpretive measure of similarity, and a corresponding assignment matrix, that corresponds to the percentage of a state's area or population that stays in the same congressional district between two plans.
We then show how to calculate this measure in an intuitive time and briefly demonstrate some potential use-cases.
arXiv Detail & Related papers (2021-11-17T03:37:25Z) - Dealing with Non-Stationarity in Multi-Agent Reinforcement Learning via
Trust Region Decomposition [52.06086375833474]
Non-stationarity is one thorny issue in multi-agent reinforcement learning.
We introduce a $delta$-stationarity measurement to explicitly model the stationarity of a policy sequence.
We propose a trust region decomposition network based on message passing to estimate the joint policy divergence.
arXiv Detail & Related papers (2021-02-21T14:46:50Z) - Colorado in Context: Congressional Redistricting and Competing Fairness
Criteria in Colorado [0.0]
We generate a large random sample of reasonable redistricting plans and determine the partisan balance of each district using returns from state-wide elections in 2018.
We investigate the relationships between partisan outcomes, number of counties which are split, and number of competitive districts in a plan.
arXiv Detail & Related papers (2020-11-11T20:05:50Z) - Sequential Monte Carlo for Sampling Balanced and Compact Redistricting
Plans [0.0]
We present a new Sequential Monte Carlo (SMC) algorithm that generates a sample of redistricting plans converging to a realistic target distribution.
We validate the accuracy of the proposed algorithm by using a small map where all redistricting plans can be enumerated.
We then apply the SMC algorithm to evaluate the partisan implications of several maps submitted by relevant parties in a recent high-profile redistricting case in the state of Pennsylvania.
arXiv Detail & Related papers (2020-08-13T23:26:34Z) - Implicit Distributional Reinforcement Learning [61.166030238490634]
implicit distributional actor-critic (IDAC) built on two deep generator networks (DGNs)
Semi-implicit actor (SIA) powered by a flexible policy distribution.
We observe IDAC outperforms state-of-the-art algorithms on representative OpenAI Gym environments.
arXiv Detail & Related papers (2020-07-13T02:52:18Z) - The Essential Role of Empirical Validation in Legislative Redistricting
Simulation [0.0]
We apply a recently developed computational method that can efficiently enumerate all possible redistricting plans.
We show that this algorithm scales to a state with a couple of hundred geographical units.
arXiv Detail & Related papers (2020-06-17T20:51:43Z) - Variational Policy Propagation for Multi-agent Reinforcement Learning [68.26579560607597]
We propose a emphcollaborative multi-agent reinforcement learning algorithm named variational policy propagation (VPP) to learn a emphjoint policy through the interactions over agents.
We prove that the joint policy is a Markov Random Field under some mild conditions, which in turn reduces the policy space effectively.
We integrate the variational inference as special differentiable layers in policy such as the actions can be efficiently sampled from the Markov Random Field and the overall policy is differentiable.
arXiv Detail & Related papers (2020-04-19T15:42:55Z)
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.