A computational approach to unbiased districting

Puppe, Clemens and Tasnádi, Attila (2008) A computational approach to unbiased districting. Mathematical and Computer Modelling, 48 (9-10). pp. 1455-1460. DOI 10.1016/j.mcm.2008.05.024

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL:


In the context of discrete districting problems with geographical constraints, we demonstrate that determining an (ex post) unbiased districting, which requires that the number of representatives of a party should be proportional to its share of votes, 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, that is, there is no guarantee for finding an unbiased districting (even if such exists). 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.

Item Type:Article
Series Number / Identification Number:10.1016/j.mcm.2008.05.024
Uncontrolled Keywords:redistricting, gerrymandering, NP-complete problems
Subjects:Mathematics, Econometrics
ID Code:276
Deposited By: Ádám Hoffmann
Deposited On:21 Feb 2011 15:51
Last Modified:18 Mar 2014 16:31

Repository Staff Only: item control page


Downloads per month over past year

View more statistics