Bonsai: A class of effective methods for independent sampling of graph partitions
This addresses the need for efficient and unbiased sampling in redistricting applications, offering a novel approach that could improve fairness and transparency in political map-making.
The paper tackled the problem of constructing ensembles of district plans by developing methods for independent sampling from a probability distribution over graph partitions, and it showed that these algorithms outperform standard Markov Chain-based methods on grid graphs and state maps, with explicit distribution descriptions for perfectly balanced populations.
We develop effective methods for constructing an ensemble of district plans via independent sampling from a reasonable probability distribution on the space of graph partitions. We compare the performance of our algorithms to that of standard Markov Chain based algorithms in the context of grid graphs and state congressional and legislative maps. For the case of perfect population balance between districts, we provide an explicit description of the distribution from which our method samples.