格点划分策略研究

Macal&North【2005年】），经历了时间步进化。在这种情况下，agent是一个在给定时间步关联到单个晶格站点的对象，walker函数是一组概率规则，用于确定agent的空间位置如何在时间步之间演化。代理代表人口中的一个个体，因此代理的概率进化导致人口分布中的随机波动。在这项工作中，我们将利用人口分布中的这些随机波动来实施蒙特卡罗方法。图2：例如，walkeralgorithm生成的人口分布。颜色强度表示人口密度。对于给定的区域S，可以通过walkerfunction构建一个总人口为Ps的人口模型，如下所述。我们取一个m×m格，考虑具有以下起始分布（在时间步长t=0）（1）Pi，jt=0=（PSfor（i，j）=（0,0）0，否则。因此，每个整数种群单位都与晶格上的一个代理相关联，在通过Walker函数进化之前，整个Territory种群都位于晶格中心位置。在每个时间步骤中，一个代理可以以固定的概率移动到其当前位置附近的任何晶格位置，概率相等，限制代理保持在m×m晶格内。每个代理分配固定数量的移动，所有代理的移动计数遵循正常分布，以从（0,0）到（m，m）所需的最小移动数为中心。一旦代理执行了规定的移动次数，它将保留在其终端单元中。在所有代理采取规定的移动后，walker函数输出每个晶格位置（i，j）的代理数量，这与领土单位Ti，j的人口Pi，jof一致。

walker函数为每个Ti，j提供Pi，j的值∈ 因此，Sand定义了一个人口模型（但不是选民模型，因为vi，jremain在现阶段尚未确定）。该算法得到的种群扩散近似于二维高斯分布；图2显示了一个示例。格点划分策略研究7B。在网格上模拟选举使用人口分布的工作网格模型，我们接下来介绍一个在人口中引入投票分布的自由度函数，该函数将导致投票和选举事件的发生。定义7：支持者（反对者）是指从选区划分中受益（损失）的一方。如果vi，j>0，则领土单位Ti，jis为支持者单位；如果vi，j<0，则为对手单位；如果vi，j=0，则为中立单位。在不丧失一般性的情况下，我们让提议方对应于正极端，即vi，j>0，并将其指定为“红色”方。我们把对方称为“蓝色”党。我们假设所有选民都投票，因此vi，j>0对应于领土单位Ti的平均投票数，j支持支持者。我们还假设GerryMander肯定知道值vi，j，尽管这可以放宽。定义8：领土S的净领土投票（或全民投票）是指苏门答腊岛：=∑i、 jvi，j.如果NS≈ 0.对于D区=∪（i，j）∈ITi，jin S，地区投票是ND=∑（i，j）∈Ivi，j.我们说，如果NS>0，红党将赢得S的普选；相反，如果NS<0，蓝色会赢得（红色）普选。然而，通常最重要的是地区整体投票，而不是全体选民的普选。

与普选类似，对于n个地区，我们说红色赢得了DK1区的地区投票≤ k≤ n如果NDk>0，并且如果NDk<0，我们说蓝色赢（红色输）地区投票。地区投票和普选之间的区别意味着一个政党可能会失去后者，同时确保大多数地区的安全。通常，最重要的结果是各方赢得的选区数量。因此，选区划分从根本上揭示了分布的局部和全局属性之间的差异。给定区域内n区的实际数量范围为2到O（10）；例如，夏威夷只有2个国会选区，而加州有53个。在后面的示例和统计研究中，我们通常取n=5。由于选举具有动态性和内在的不确定性，如果计划仅以一票之差赢得一个选区，那么选区划分者就有可能失败。引入投票门槛，确保老人党以最小优势赢得给定选区。如果NDk>w，我们称红色为严格的“安全”，对于固定的规定w∈ Z，称为votethreshold（相反，NDk<-w对于蓝色是安全的）。我们通常采用w~ 0.01×PS/n，适用于n个地区，因此安全地区至少有1%的裕度有利于支持者。C、 为选民偏好分布建模接下来，我们将介绍一种生成选民偏好平滑分布的新方法。我们根据党派偏见峰值的一些特定点实施选民偏好，“来源”，选民偏好下降到每个地区都可以确定工作区，因此根据地区的不同，要求会变弱或变强。8远离这些峰值的预印本中性。

通过与静电势理论和逆幂定律的类比，我们通过点电荷的特性确定了党派偏见的来源，如下所示。定义9：给定一个区域S，源点是一对Ei，j={（i，j），e}，以其位置（i，j）为特征∈ S和e级∈ 源的R。我们要求任何一组震源点都给出| vi，j |≤ 1.Ti，j∈ S、 为了与我们之前的（任意）赋值相匹配，即vi，j>0对应于红方，我们在e>0时称为Ei，ja红色源，在e<0时称为蓝色源。源点可以位于任意晶格位置，给定领土单位的选民偏好ti，jis是距离这些源点d的函数，遵循1/d幂律：定义10：投票贡献k、 l从一个源，由E={（i，j），E}到领土单位Tk，l的净投票，其中（i，j）和（k，l）由距离d隔开（Ti，j，Tk，l）为（2）k、 l=emax[1，d（Ti，j，Tk，l）]，其中距离函数（度量）取（3）d（Ti，j，Tk，l）：=q（k-i） +（l- j） 。给定1的α源点{Eα}≤ α ≤ m、 他们的职位是独立选择的，我们表示他们对vi，jas的贡献（α） i，jand（4）vi，j=∑m级（m） i，j.根据上述定义，给定来源的投票贡献与距离d呈线性下降。由于1/d幂律，源点通常代表选民偏好的局部最大值，符号（e）表示被支持方。

在这个模型中，一个平衡的区域至少需要一个蓝色和一个红色来源，sowe通常对有两个或更多来源的场景感兴趣。此外，我们注意到，原则上，两个震源点可以位于同一地点，（5）E={（i，j），E}和E={（i，j），E}，在这种情况下，两个震源始终可以替换为一个震源：（6）{E，E}<-> E1+2={（i，j），（e+e）}。原则上，可以研究其他幂律，或者考虑每个具有不同d依赖性的源。格点划分策略研究9D。基准模型图3：例如，两个源点的选民分布。综上所述，给定一个区域S，我们使用第I.a节的walker函数来确定S的Pi、J值，并通过指定一组源点并参考公式（4）来确定vi、jvaluesof S，从而确定选民模型。例如，我们将原点（0,0）的左侧和右侧的晶格点指定为蓝色和红色源点{EB，ER}，其中（7）ER={(-1，0），1}和EB={（1，0），-1} .二维准高斯总体分布（如图2所示）和源{EB，ER}的组合产生图3所示的选民分布。颜色强度表示净选民偏好vi，Jan的大小，这些颜色区域的中心对应于两个源点的位置。在接下来的示例和统计分析中，我们将考虑一些具有准俄罗斯人口分布和特定源点分布的特定基准选民模型，如下表1所示：模型#Eberer1（（1,0），-1) - ((-1,0),1) 2 ((4,0),-1) - ((-4,0),1) 3 ((6,0),-1) ((0,6),-1) ((-6,0),1) ((0,-6),1)4 ((6,0),-1) ((-6,0),-1) ((0,6),1) ((0,-6） ，1）表1-：基于21×21平方格的区域有2或4个源点的模型。

破折号表示源点未包含在给定模型中。所有基准模型都有平衡的地区投票：NS≈0、#1模型的投票者分布如图3所示，#2-#4模型如图4所示。这些例子表明，上述方法可以实现多种选民分布。型号#2型号#3型号#4图4：表1.10预印前#2-#4模型选民分布的可视化。Friedman-Holden包装策略在算法的选区划分中有两种基本策略：包装和破解。首先，选区划分者可以通过将最集中的反对党投票亚群体划分为少数几个选区来稀释反对党的投票权。第二，可以将最集中的反对党人口分成几个选区，以便反对党最集中或极端的投票基础永远获得多数。弗里德曼和霍尔顿（Friedman&Holden）[2008]的研究方法以选民包装的战略应用为基础。作为一个例子，考虑一个支持红党的选区划分者，其目标是在最大选区数dk1中NDk>0≤ k≤n在给定区域内。Friedman&Holden[2008]考虑了伪正态选民极端分布，并通过简单地按极端划分人口的贝尔曲线来生成地区。第一个区是通过连接最极端的亚种群（即钟形曲线尾部）形成的，因此i）它们的组合种群约为平均区种群，ii）右尾部远远大于左尾部。后一个条件意味着极右翼政党选民有足够的能力推翻其选区内极左翼政党的投票。从本质上讲，上述过程将“浪费”对手在一个不太可能获胜的选区中最强大的投票群体。

这一过程在随后的地区重复，最终地区由剩余人口组成。因此，通过建设，后期地区主要由温和选民组成，对于平衡的地区，通常由反对党获胜。这种方法有许多优点，但缺乏空间考虑。弗里德曼·霍尔顿（Friedman Holden）方法等同于不受限制的“樱桃采摘”：gerrymanderer可以自由选择分散的人口块，以便将其放置在同一类别中，我们很快就会证明这一点。值得注意的是，如果连一个区都断开连接，那么分区计划通常是法律禁止的。失效的一个有用度量是每个区域的连接部件数量：定义11：连接部件C D区的D是D中的一组（非空）领土单位，因此给定一个领土单位Ti，j∈C、 另一个领土单位Tk，lalso位于C当且仅当Tk，l.A区可到达的Ti，jis可分解为其连接组件集Cian，我们将写=∪我≤rCi，其中r是连接组件的数量。如果任何领土单位D可以从D中的所有其他领土单位访问，那么r=1，我们说D是连通的。连接组件的数量对于分析所研究算法产生的空间分布非常重要。A、 将Friedman和Holden的算法应用于晶格领域Friedman和Holden【2008】概述了一种忽略选民分布空间数据的打包策略。为了证明这一策略如何导致高度脱节的地区，我们将重新制定Friedman&Holden[2008]的策略，将其应用于格点投票模型11的算法方法，我们将此算法称为“FH填充”。

然后，通过在重新划分过程中忽略空间数据，但跟踪分配给每个地区的领土单元的位置，我们可以评估通过FH布局构建的地区的连通性。首先，由于法律要求投票地区拥有可比人口，我们确定了目标人口PD±以确保所有地区的人口大致相等。目标人口使用人口阈值t（从定义6开始）、总人口PS和区数n来实现，如下（8）PD±：=（PS/n±t）。在执行算法之前计算PD±的值，每个地区应满足以下人口条件（9）PD-≤ PDk公司≤ PD+。此外，大多数地区应满足地区获胜条件（10）NDk>w。如果地域平衡，后期地区，尤其是最终地区，必须有对手偏见。只有当算法满足给定地区的组成时，它才会继续形成下一个地区，直到形成所有n个地区。为了在格子区域上实现FH布局策略，我们的算法迭代地将单个区域单元分配给一个区域，一次分配一个区域，这样最终的结果会让支持者满意。如果领土单位尚未分配给某个地区，我们称之为未分配单位，并表示未分配单位的集合U。当领土单位通过算法分配给地区时，它们将从U中删除。对于m×m格点上的领土S，最初在DK1的U和n（空）区中有指定的领土单位≤ k≤n

我们通过使用快速排序方法【Hoare，1961年】，首先按照净投票数vi，j的递减顺序对领土单位进行排序，并重新标记该有序集合的元素{T，T，························································。更准确地说，最强的未分配对手单位是Ti，j∈U如果vi，j≤ vk，l前油箱，l∈U、 或等效为^Tβ∈所有其他^Tγ的U if∈U一的β<γ。相反，U中最大指数β的^Tβ是最强的未分配支持单位。实施Friedman&Holden【2008】中所述策略的离散化版本，我们的算法通过迭代添加最强的未分配支持者单位，然后再添加最强的未分配对手单位，形成每个D区，直到PD>PD-. 然后，该算法计算地区投票NDk，并将其与votethreshold w进行比较。如果NDk>w且PD<PD+，则该地区已完成，并且该算法重复此过程以创建剩余的地区，但最后一个地区除外。可能是在形成一个给定的地区时，该地区满足PD>PD-分区投票的计算结果小于投票阈值。在这种情况下，算法会添加最强的剩余未分配支持单位，直到NDk>w，并且在每一步12预印本检查PD<PD+。一旦选区投票足够大，选区就完成了。当超过人口限制时，PD>PD+，我们的算法将删除最后一个unitadded，然后在排序列表中尝试下一个unitadded，直到它识别出一个不违反人口限制的添加到地区。对于较大的投票阈值w或较小的人口阈值t，此分区算法可能会失败（即没有同时满足的分区）。

（9） 和（10）），但对于百分比水平w和t来说，这很少是一个问题。最后，在第一个（n-1） 地区建设。如果领土平衡，正如我们所假设的那样，那么所有地区都不可能支持支持者，因此预计最终地区的NDn<0。此外，根据设计，最终选区主要由温和派选民组成。对最终地区的唯一要求是满足-≤ PDn公司≤ PD+，这通常是合理选择t的情况。对于较低的人口阈值，以及更严格的人口一致性要求，最终地区可能无法满足人口限制。在这种情况下，在构建最终地区后，算法将对地区组成进行多次修改，以使人口在阈值范围内。如果PDn>PD+，则最终地区外部有利于领土单位的权益将转移至相邻地区。如果PDn<PD-, 然后，支持其他地区和最终区附近的领土单位的对手将被转移到最终区。图5显示了执行示例，图6显示了说明此算法步骤的流程图。具体而言，我们展示了Friedman&Holden【2008】算法实现的输出，如上所述，将21×21晶格区域划分为5个区域，用于基准模型#1和#4（见表1）。颜色的强度表示某一特定地区的党派极端，黑线表示地区之间的分界线。最左边的图幅展示了整个地区，而右边的图幅则按建筑顺序显示了1至5个分区的组成。