科罗拉多州成立了一个无党派重新划分委员会来绘制地图。然而，地区边界的无限可能性挑战了数学家决定什么是公平的能力。
Paul Chaikin/广达杂志
介绍
直到最近，被不公正划分的地区往往很突出，可以通过它们扭曲的卷须来识别。这已不再是这种情况。 “借助现代技术，你可以非常有效地进行 gerrymander，而不会使你的形状变得非常奇怪，”科罗拉多学院的数学家Beth Malmskog说。这使得弄清楚地图是否被不公平地操纵变得更加困难。
由于没有明显畸形地区的明显迹象，数学家们一直在开发越来越强大的统计方法来寻找不公正的选区。这些通过将地图与数千或数百万可能地图的集合进行比较来工作。如果地图为民主党人或共和党人提供的席位明显多于平均地图的预期席位，则表明可能发生了一些可疑的事情。
但是制作这样的集合比听起来更棘手，因为考虑所有可能的地图是不可行的——对于任何超级计算机来说，组合实在是太多了。最近的一些数学进步提出了在这个不可能的大可能模拟空间中导航的方法，为数学家提供了一种可靠的方法来判断公平与不公平。
就像许多与重新选区相关的事情一样，他们的工作最终要上法庭。在过去的五年中，模拟已被接受为密苏里州、北卡罗来纳州、俄亥俄州和密歇根州重新划分法院案件的证据。他们是艾伦诉米利根案中辩论的中心对象，这是一个等待最高法院审理的重要案件，黑人选民指责阿拉巴马州绘制国会选区地图，使他们处于不利地位。在这种情况下，与许多其他情况一样，原告和被告都在征集模拟来为他们的案件辩护。预计法院将在 6 月或 7 月作出裁决。
但是，正如原告的一名律师在 10 月份的口头辩论中告诉法官塞缪尔·阿利托的那样，“模拟实际上产生的问题多于他们回答的问题。”
组合爆炸
要理解生成集成的数学难度，请从考虑不切实际的简单地图开始。例如，想象一个 4×4 的网格。有 117 种不同的方法可以将这 16 个广场细分为四个相邻的区域，每个区域有四个广场。从那里开始，可能性在所谓的组合爆炸中迅速增长。一个 6×6 的网格有 6 个相邻的区域，每个区域有 6 个正方形，每个区域有 451,206 种可能性。一个 9×9 的网格，每个区域有 9 个区域，每个区域有 9 个正方形？超过 700 万亿种选择。对于具有 100 个正方形的 10×10 网格，没有人知道有多少种可能的 10 区配置。
当然，一个典型的州有 100 多个不同的管辖区，这些管辖区可以组合成地区。分析师经常在投票区之外建立可能的选区。例如，北卡罗来纳州有 2,500 多个辖区，而宾夕法尼亚州有 9,159 个。官方分区计划通常基于更精细的人口普查区块：阿拉巴马州有 185,976 个这样的区块。
每个州都有不同的划区规则，但总的来说，它们必须是连续的和“紧凑的”，保留传统的地理和政治边界，人口非常接近平等，并避免分裂所谓的利益共同体。 《投票权法》还要求以确保所有种族群体的选民都有平等机会“选举他们选择的代表”的方式划分选区。协调所有这些要求在数学上具有挑战性。 Malmskog 说，重新划分的要求越多，“数学问题就越复杂。”
“借助现代技术，你可以非常有效地进行 gerrymander，而不会使你的形状变得非常奇怪，”科罗拉多学院的数学家 Beth Malmskog 说。
在过去的 20 年里，生成大量可能地图的主要技术一直是一种称为“随机种子和生长”的技术。这听起来很有效。假设您想将数千个单独的选区合并为 10 个国会选区，每个选区必须包含大约 760,000 人。你首先随机选择一个区域来“播种”一个特定的区域。然后，您将相邻的辖区添加到该种子，直到该地区的人口接近 760,000。然后你重复这个过程——从另一个选区开始为另一个地区播种——直到你想出你的其他地区。
通过一些相对简单的调整来确保区域紧凑，可以使用此方法制作许多外观合理的地图。但是由于可能地图数量的组合爆炸式增长，即使通过随机种子和增长技术制作的数百万张地图也只占所有可能地图的一小部分。并且没有数学证据表明该分数代表整个有效地图集，这意味着将其用作比较基础可能会导致误导性结论。
这就是为什么在过去十年中，包括哈佛大学政府与统计学教授Kosuke Imai和杜克大学数学与统计学教授Jonathan Mattingly在内的研究人员开始应用一种称为马尔可夫链蒙特卡洛的技术，或 MCMC，制作地图。
MCMC 的工作原理是首先将现有的地区地图转换为图形——一种由节点或点组成的数学结构，由线或边连接。每个选区成为一个节点；如果区域在现实生活中共享边界，则它们在图中由一条边连接。早期的 MCMC 方法，如 Imai 及其同事在2014 年的一篇论文中描述的“基于翻转”的方法，通过以数学上特定的方式在边界地区之间交换选区来工作。
通过将他们的地图视为图表，研究人员可以使用图表理论中称为 Perron-Frobenius 定理的工具来证明，如果允许算法运行足够长的时间——数学家称之为混合时间的间隔——它将正确地运行从所有可能的有效地图的分布中抽样。这是一个改进，但通常仍然无法严格证明混合时间到底有多长。 Mattingly 表示，如何最好地“向所有人证明我们抽样工作做得很好”的问题仍未解决。因此，数学家们正在努力对 MCMC 进行调整，以更好地确定混合时间的界限——并更快地达到它。
2019 年 3 月，一名示威者在美国最高法院外抗议，当天法院正在审理两起不公正划分案件的辩论。
UPI/Alamy 图片
介绍
一项进展出现在 2019 年，当时一组研究人员正在研究一种更好的方法来为弗吉尼亚众议院绘制新的选区地图。前一年，联邦法院裁定弗吉尼亚地图上的 11 个选区违宪，因为它们集中了黑人居民，削弱了他们的投票权。此外，弗吉尼亚州在重新划分选区的过程中有一个异常严格的限制：选区的人口只能偏离 1%。鉴于有 100 个州议会选区，“这是一个非常严格的界限，”华盛顿州立大学的数学家Daryl DeFord说，他分析了弗吉尼亚地图的公平性。这意味着该小组无法在辖区级别开展工作。 “有些区域基本上太大了，无法制定有效的计划，”德福特说。将地图划分为更小的人口普查区块单元也没有用。在大约 1000 万步之后，标准的基于翻转的 MCMC 算法“离从整个空间中获得代表性样本还差得很远，”他说。
因此，DeFord 和他的同事想出了一种可以更快地在空间中移动的方法。为了快速从可能地图的整个空间中获取样本，他们需要以保持地区连续性的方式一次更改许多辖区的地区分配。这使得马尔可夫链中的每一步在计算上都更加昂贵，但这也意味着每一步都使它们更接近混合时间。
他们设计了一种称为 ReCom 的算法，该算法通过随机选择两个相邻的地区并将它们合并以创建一个单元来工作。本单元继承了各地区的图形结构。但是，ReCom 不是交换相邻的选区，而是随机创建一个称为生成树的新图，它以一种不包含任何循环但确保所有连接的方式将两个组合区（每个代表一个选区）中的节点相互连接节点已连接。因为没有回路，切割任何一条边都会将两个合并的区域分成两部分（就像锯掉树的任何分支都会将其恰好切割成两部分一样）。
通常很容易找到在每个结果组件中留下几乎相等数量节点的边——ReCom 随机选择这样的边。 （如果找不到，则重新绘制生成树。）由于生成树的统计，这也有产生紧凑区的自然趋势。由于 ReCom 在每一步都进行了数百次更改，因此其发明者相信它比一次更改较少区域的基于翻转的方法更快地达到混合时间。
现实世界的挑战
弗吉尼亚州严格的人口限制并不是这一过程中唯一可能出现的转折。科罗拉多州有一个不寻常的要求，超出了连续性和紧凑性的典型限制：科罗拉多州法律还要求选区具有“竞争力”。
法律对竞争力的定义非常模糊，因此负责绘制科罗拉多州立法选区地图的独立委员会决定使用历史数据来定义竞争选区。为了使一个假设的选区具有“竞争力”，在前三场选举中，民主党和共和党的选定种族的总票数必须在 46% 到 54% 之间。
该委员会随后求助于 DeFord、Malmskog 和科罗拉多大学博尔德分校的数学家Jeanne Clelland 。他们使用 ReCom 算法生成了数百万张符合州重新划分标准的地图的集合；然后，他们使用这些集合来计算出“您可能希望有多少地区落入该竞争范围的价值范围，”Clelland 说。然后，随着委员会制定新的计划，数学家们确定了它们在统计分析中的位置。 Clelland 说，最终，立法重新划分选区委员会选择了一张地图，该地图的选区比数学家在他们的集合中看到的平均选区更具竞争力。
Clelland 指出，虽然竞争选区听起来很公平，但实际上它们可能与比例原则相冲突，比例原则是任何一方的代表人数应与全州该党选民人数相匹配的目标。 “如果你有很多地区的结果真的接近 50%，那么选票份额的微小变化可能会导致席位份额的巨大变化。”
杜克大学的数学家乔纳森·马丁利 (Jonathan Mattingly) 是对选举地图公平性进行定量分析的先驱之一。
Duke Communications 的 Jared Lazarus
介绍
今井表示，他担心在某些情况下，从初始计划开始并对其进行调整的 MCMC 方法（例如 ReCom）“很难探索空间”。他说，由于可能的有效地图空间非常多模态（这意味着可能有多个彼此非常不同的好解决方案），这样的算法可能会过于接近其初始条件。这就是为什么 Imai 与他的研究生 Cory McCartan 一起在预印本中引入了一种称为“序贯蒙特卡罗”或 SMC 的新方法，该预印本已被《应用统计年鉴》接受发表。 SMC 还将地图转换为图形，并像 ReCom 一样创建这些图形的生成树。
SMC 创建一个单一的生成树，其中包含每个区域的节点。然后它试图从图中的其余部分中分离出一个区域。它根据 Imai 和 McCartan 指定的标准确定最有希望切割的边，然后它随机选择这些边之一。然后它在图表的剩余部分重复该过程，一次拆分一个新的地区，直到创建了所需数量的地区。通过重复这个过程数百万次，SMC 创建了数百万个可能的可行地图。
数学论证
计算重新划分有效地取代了相对简单的问题，即单个地图是否公平，而看似复杂得多的问题，即数百万张地图是否公平。这完全符合数学传统，即表明一个简单的问题等同于一个复杂得多的问题，然后解决更复杂的问题。
2022 年 11 月，今井的团队根据 2020 年人口普查数据发布了所有 50 个州的大量国会重新选区地图模拟集。由于有许多参数需要调整，具体取决于您要回答的问题，他们希望他们的工具能够让大众可以使用集成分析。
Imai 是最高法院未决案件原告的专家证人。原告使用他生成的合奏辩称，阿拉巴马州的选区剥夺了黑人选民的选举权，这违反了《投票权法》。但是被起诉的阿拉巴马州正在使用他的合奏来争辩说地图是公平绘制的。无论法院做出何种裁决，都表明在选举中，数学总是需要与政治相抗衡。
原文： https://www.quantamagazine.org/how-math-has-changed-the-shape-of-gerrymandering-20230601/