IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/vyid10.1007_s10878-020-00589-x.html
   My bibliography  Save this article

On theoretical and empirical algorithmic analysis of the efficiency gap measure in partisan gerrymandering

Author

Listed:
  • Tanima Chatterjee

    (University of Illinois at Chicago)

  • Bhaskar DasGupta

    (University of Illinois at Chicago)

  • Laura Palmieri

    (University of Illinois at Chicago)

  • Zainab Al-Qurashi

    (University of Illinois at Chicago)

  • Anastasios Sidiropoulos

    (University of Illinois at Chicago)

Abstract

Partisan gerrymandering is a major cause for voter disenfranchisement in United States. However, convincing US courts to adopt specific measures to quantify gerrymandering has been of limited success to date. Recently, Stephanopoulos and McGhee in several papers introduced a new measure of partisan gerrymandering via the so-called “efficiency gap” that computes the absolute difference of wasted votes between two political parties in a two-party system; from a legal point of view the measure was found legally convincing in a US appeals court in a case that claims that the legislative map of the state of Wisconsin was gerrymandered. The goal of this article is to formalize and provide theoretical and empirical algorithmic analyses of the computational problem of minimizing this measure. To this effect, we show the following: (a) On the theoretical side, we formalize the corresponding minimization problem and provide non-trivial mathematical and computational complexity properties of the problem of minimizing the efficiency gap measure. Specifically, we prove the following results for the formalized minimization problem: (i) We show that the efficiency gap measure attains only a finite discrete set of rational values. (observations of similar nature but using different arguments were also made independently by Cho and Wendy (Univ Pa Law Rev 166(1), Article 2, 2017). (ii) We show that, assuming P $$\ne \textsf {NP}$$≠NP, for general maps and arbitrary numeric electoral data the minimization problem does not admit any polynomial time algorithm with finite approximation ratio. Moreover, we show that the problem still remains $$\textsf {NP}$$NP-complete even if the numeric electoral data is linear in the number of districts, provided the map is provided in the form of a planar graph (or, equivalently, a polygonal subdivision of the two-dimensional Euclidean plane). (iii) Notwithstanding the previous hardness results, we show that efficient exact or efficient approximation algorithms can be designed if one assumes some reasonable restrictions on the map and electoral data. Items (ii) and (iii) mentioned above are the first non-trivial computational complexity and algorithmic analyses of this measure of gerrymandering. (b) On the empirical side, we provide a simple and fast algorithm that can “un-gerrymander” the district maps for the states of Texas, Virginia, Wisconsin and Pennsylvania (based on the efficiency gap measure) by bring their efficiency gaps to acceptable levels from the current unacceptable levels. To the best of our knowledge, ours is the first publicly available implementation and its corresponding evaluation on real data for any algorithm for the efficiency gap measure. Our work thus shows that, notwithstanding the general worst-case approximation hardness of the efficiency gap measure as shown by us, finding district maps with acceptable levels of efficiency gaps could be a computationally tractable problem from a practical point of view. Based on these empirical results, we also provide some interesting insights into three practical issues related the efficiency gap measure.

Suggested Citation

  • Tanima Chatterjee & Bhaskar DasGupta & Laura Palmieri & Zainab Al-Qurashi & Anastasios Sidiropoulos, 0. "On theoretical and empirical algorithmic analysis of the efficiency gap measure in partisan gerrymandering," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-35.
  • Handle: RePEc:spr:jcomop:v::y::i::d:10.1007_s10878-020-00589-x
    DOI: 10.1007/s10878-020-00589-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-020-00589-x
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s10878-020-00589-x?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Niemi, Richard G. & Deegan, John, 1978. "A Theory of Political Districting," American Political Science Review, Cambridge University Press, vol. 72(4), pages 1304-1323, December.
    2. Jackman, Simon, 1994. "Measuring Electoral Bias: Australia, 1949–93," British Journal of Political Science, Cambridge University Press, vol. 24(3), pages 319-357, July.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Tanima Chatterjee & Bhaskar DasGupta & Laura Palmieri & Zainab Al-Qurashi & Anastasios Sidiropoulos, 2020. "On theoretical and empirical algorithmic analysis of the efficiency gap measure in partisan gerrymandering," Journal of Combinatorial Optimization, Springer, vol. 40(2), pages 512-546, August.
    2. Barry Burden & Corwin Smidt, 2020. "Evaluating Legislative Districts Using Measures of Partisan Bias and Simulations," SAGE Open, , vol. 10(4), pages 21582440209, December.
    3. Christopher Warshaw & Eric McGhee & Michal Migurski, 2022. "Districts for a New Decade—Partisan Outcomes and Racial Representation in the 2021–22 Redistricting Cycle," Publius: The Journal of Federalism, CSF Associates Inc., vol. 52(3), pages 428-451.
    4. Justin Buchler, 2007. "The social sub-optimality of competitive elections," Public Choice, Springer, vol. 133(3), pages 439-456, December.
    5. Munzert, Simon, 2017. "Forecasting elections at the constituency level: A correction–combination procedure," International Journal of Forecasting, Elsevier, vol. 33(2), pages 467-481.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v::y::i::d:10.1007_s10878-020-00589-x. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.