A Computational Approach to Unbiased Districting

In the context of discrete districting problems with geographical constraints, we demonstrate that determining an unbiased districting turns out to be a computationally intractable (NP-complete) problem. This raises doubts as to whether an independent jury will be able to come up with a “fair” redistricting plan in case of a large population. We also show that, in the absence of geographical constraints, an unbiased districting can be implemented by a simple alternating-move game among the two parties