You Can Have Your Cake and Redistrict It Too

References

• Agarwal PK, Ko S, Munagala K, Taylor E (2022) Locally fair partitioning. Proc. 36th AAAI Conf. Artificial Intelligence (AAAI Press, Washington, DC), 4752–4759.Google Scholar
• Akitaya HA, Gonczi A, Souvaine DL, Tóth CD, Weighill T (2023) Reconfiguration of polygonal subdivisions via recombination. Gørtz IL, Farach-Colton M, Puglisi SJ, Herman G, eds. 31st Annual Eur. Sympos. Algorithms (ESA 2023), Leibniz International Proceedings in Informatics (LIPIcs), vol. 274 (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 6:1–6:16.Google Scholar
• Allen D (2023) Opinion: Our democracy is menaced by two dragons. Here’s how to slay them. Washington Post (July 20), https://www.washingtonpost.com/opinions/2023/07/20/gerrymandering-electoral-college-solution-democracy/.Google Scholar
• Arunachaleswaran ER, Barman S, Rathi N (2019) Fully polynomial-time approximation schemes for fair rent division. SODA’19: Proc. 30th ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1994–2013.Google Scholar
• Austin AK (1982) Sharing a cake. Math. Gazette 66(437):212–215.Crossref, Google Scholar
• Aziz H, Mackenzie S (2016) A discrete and bounded envy-free cake cutting protocol for any number of agents. Proc. 57th IEEE Sympos. Foundations Comput. Sci. (FOCS) (IEEE, Piscataway, NJ), 416–427.Google Scholar
• Bertsimas D, Farias VF, Trichakis N (2011) The price of fairness. Oper. Res. 59(1):17–31.Link, Google Scholar
• Borodin A, Lev O, Shah N, Strangway T (2022) Little house (seat) on the prairie: Compactness, gerrymandering, and population distribution. AAMAS’22: Proc 21st Internat. Conf. Autonomous Agents Multiagent Systems (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 154–162.Google Scholar
• Bouie J (2023) A breathtaking contempt for the people of Wisconsin. New York Times (September 8), https://www.nytimes.com/2023/09/08/opinion/wisconsin-judge-impeachment-democracy.html.Google Scholar
• Brams SJ (2020) Making partisan gerrymandering fair: One old and two new methods. Soc. Sci. Quart. 101(1):68–72.Crossref, Google Scholar
• Brams SJ, Taylor AD (1996) Fair Division: From Cake-Cutting to Dispute Resolution (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Buchanan A, Ezazipour S, Shahmizad M (2025) A widespread belief about county splits in political districting plans is wrong. Election Law J.: Rules Politics Policy 24(4):303–321. Google Scholar
• Butler DE (1952) The British General Election of 1951 (Macmillan, New York).Google Scholar
• Bycoffe A, Koeze E, Wasserman D, Wolfe J (2018) The atlas of redistricting. Accessed April 15, 2026, https://web.archive.org/web/20180131230333/https://projects.fivethirtyeight.com/redistricting-maps/.Google Scholar
• Cannon S, Duchin M, Randall D, Rule P (2022) Spanning tree methods for sampling graph partitions. Preprint, submitted October 4, https://arxiv.org/abs/2210.01401.Google Scholar
• Caragiannis I, Kaklamanis C, Kanellopoulos P, Kyropoulou M (2009) The efficiency of fair division. Leonardi S, ed. Internet Network Econom. WINE 2009, Lecture Notes in Computer Science, vol. 5929 (Springer, Berlin, Heidelberg), 475–482.Google Scholar
• Charikar M, Liu P, Liu T, Vuong TD (2022) On the complexity of sampling redistricting plans. Preprint, submitted June 10, https://arxiv.org/abs/2206.04883.Google Scholar
• De Silva J, Gales B, Kagy B, Offner D (2018) An analysis of a fair division protocol for drawing legislative districts. Preprint, submitted November 14, https://arxiv.org/abs/1811.05705.Google Scholar
• DeFord D, Duchin M, Solomon J (2021) Recombination: A family of Markov chains for redistricting. Harvard Data Sci. Rev. 3(1):1–67.Google Scholar
• Dehghani S, Farhadi A, Hajiaghayi M, Yami H (2018) Envy-free chore division for an arbitrary number of agents. SODA’18: Proc. 29th ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 2564–2583.Google Scholar
• Donnay C, Kahle M (2025) Asymptotics of redistricting the n×n grid. Amer. Math. Monthly 132(9):856–866.Crossref, Google Scholar
• Duchin M (2018) Geometry v. gerrymandering. Sci. Amer. 319(5):48–53.Crossref, Google Scholar
• Duchin M, Gladkova T, Henninger-Voss E, Klingensmith B, Newman H, Wheelen H (2019) Locating the representational baseline: Republicans in Massachusetts. Election Law J.: Rules Politics Policy 18(4):388–401.Crossref, Google Scholar
• DvB (1986) Davis v. Bandemer 478 U.S. 109. https://supreme.justia.com/cases/federal/us/478/109/.Google Scholar
• Edmonds J, Pruhs K (2006) Cake cutting really is not a piece of cake. SODA’06: Proc. 17th ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 271–278.Google Scholar
• Frieze A, Pegden W (2023) Subexponential mixing for partition chains on grid-like graphs. Proc. 2023 Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (Society for Industrial and Applied Mathematics, Philadelphia), 3317–3329.Google Scholar
• Gal Y, Mash M, Procaccia AD, Zick Y (2017) Which is the fairest (rent division) of them all? J. ACM 64(6), 1–22.Crossref, Google Scholar
• Garfinkel RS, Nemhauser GL (1970) Optimal political districting by implicit enumeration techniques. Management Sci. 16(8):495–508.Link, Google Scholar
• Gelman A, King G (1994) A unified method of evaluating electoral systems and redistricting plans. Amer. J. Political Sci. 38(2):514–554.Crossref, Google Scholar
• Gomberg A, Pancs R, Sharma T (2023) Electoral maldistricting. Internat. Econom. Rev. 64(3):1223–1263.Crossref, Google Scholar
• Gomberg A, Pancs R, Sharma T (2024) Padding and pruning: Gerrymandering under turnout heterogeneity. Soc. Choice Welfare 63:401–415.Google Scholar
• Grofman B, King G (2007) The future of partisan symmetry as a judicial test for partisan gerrymandering after Lulac v. Oerry. Election Law J. 6(1):2–35.Crossref, Google Scholar
• Gurnee W, Shmoys DB (2021) Fairmandering: A column generation heuristic for fairness-optimized political districting. SIAM Conf. Appl. Comput. Discrete Algorithms (ACDA21) (Society for Industrial and Applied Mathematics, Philadelphia), 88–99.Google Scholar
• Hess SW, Weaver JB, Siegfeldt HJ, Whelan JN, Zitlau PA (1965) Nonpartisan political redistricting by computer. Oper. Res. 13(6):998–1006.Link, Google Scholar
• Jackman S (1994) Measuring electoral bias: Australia, 1949–93. British J. Political Sci. 24(3):319–357.Crossref, Google Scholar
• King G (1989) Representation through legislative redistricting: A stochastic model. Amer. J. Political Sci. 33(4):787–824.Crossref, Google Scholar
• Landau Z, Su FE (2014) Fair division and redistricting. Krisman J-D, Jones MA, eds. The Mathematics of Decisions, Elections, and Games, Contemporary Mathematics, vol. 624 (American Mathematical Society, Providence, RI), 17–36.Crossref, Google Scholar
• Landau Z, Reid O, Yershov I (2009) A fair division solution to the problem of redistricting. Soc. Choice Welfare 32(3):479–492.Crossref, Google Scholar
• LMV (2018) League of women voters of PA v. com. of PA. 181 A.3d 1083. https://law.justia.com/cases/pennsylvania/supreme-court/2018/159-mm-2017-2.html.Google Scholar
• Mehrotra A, Johnson EL, Nemhauser GL (1998) An optimization based heuristic for political districting. Management Sci. 44(8):1100–1114.Link, Google Scholar
• Metric Geometry and Gerrymandering Group (2018) Comparison of districting plans for the Virginia House of Delegates. Technical report, Metric Geometry and Gerrymandering Group, Tufts University, Medford, MA.Google Scholar
• Metric Geometry and Gerrymandering Group (2020) MGGG-States: Open collection of precincts shapefiles for U.S. states. https://github.com/mggg-states.Google Scholar
• Moulin H (2003) Fair Division and Collective Welfare (MIT Press, Cambridge, MA).Crossref, Google Scholar
• Nagle JF (2017) How competitive should a fair single member districting plan be? Election Law J. 16(1):196–207.Crossref, Google Scholar
• Niemi RD, Deegan J (1978) A theory of political districting. Amer. Political Sci. Rev. 72(4):1304–1323.Crossref, Google Scholar
• Oehrlein J, Haunert J (2017) A cutting-plane method for contiguity-constrained spatial aggregation. J. Spatial Inform. Sci. 2017(15):89–120.Google Scholar
• Pancs R, Sharma T (2025) One man one vote. Amer. Econom. J.: Macroeconom. 17(1):171–205.Crossref, Google Scholar
• Pegden W, Procaccia AD, Yu D (2017) A partisan districting protocol with provably nonpartisan outcomes. Preprint, submitted October 24, https://arxiv.org/abs/1710.08781.Google Scholar
• Polsby D, Popper R (1991) The third criterion: Compactness as a procedural safeguard against partisan gerrymandering. Yale Law Policy Rev. 9(2):301–353.Google Scholar
• Procaccia AD (2013) Cake cutting: Not just child’s play. Comm. ACM 56(7):78–87.Crossref, Google Scholar
• Procaccia AD (2019) Axioms should explain solutions. Laslier JF, Moulin H, Sanver R, Zwicker WS, eds. The Future of Economic Design (Springer, Cham, Switzerland), 78–87.Crossref, Google Scholar
• Procaccia AD, Tucker-Foltz J (2022) Compact redistricting plans have many spanning trees. Proc. 2022 ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 3754–3771.Google Scholar
• Robertson JM, Webb WA (1998) Cake Cutting Algorithms: Be Fair If You Can (CRC Press, Boca Raton, FL).Crossref, Google Scholar
• Schutzman Z (2020) Trade-offs in fair redistricting. AIES’20: Proc. AAAI/ACM Conf. AI Ethics Soc. (AIES) (Association for Computing Machinery, New York), 159–165.Google Scholar
• Shirabe T (2005) A model of contiguity for spatial unit allocation. Geographical Anal. 37(1):2–16.Crossref, Google Scholar
• Shirabe T (2009) Districting modeling with exact contiguity constraints. Environment Planning B: Planning Design 36(6):1053–1066.Crossref, Google Scholar
• Stephanopoulos NO, McGhee EM (2015) Partisan gerrymandering and the efficiency gap. Univ. Chicago Law Rev. 82:831.Google Scholar
• Swamy R, King DM, Jacobson SH (2023) Multiobjective optimization for politically fair districting: A scalable multilevel approach. Oper. Res. 71(2):536–562.Link, Google Scholar
• Tapp K (2021) Spanning tree bounds for grid graphs. Preprint, submitted September 13, https://arxiv.org/abs/2109.05987.Google Scholar
• Tucker-Foltz J (2018) A cut-and-choose mechanism to prevent gerrymandering. Preprint, submitted February 22, https://arxiv.org/abs/1802.08351.Google Scholar
• Tucker-Foltz J (2023) Locked polyomino tilings. Preprint, submitted July 29, https://arxiv.org/abs/2307.15996.Google Scholar
• Validi H, Buchanan A, Lykhovyd E (2022) Imposing contiguity constraints in political districting models. Oper. Res. 70(2):867–892.Link, Google Scholar
• Voting Rights Data Institute (2018) GerryChain. https://github.com/mggg/GerryChain.Google Scholar