最近まで、ゲリマンダー地区は突き出ている傾向があり、その曲がりくねった蔓によって識別されていました。 これはもう当てはまりません。 「現代のテクノロジーを使えば、形をあまり奇妙にすることなく、かなり効果的にゲリマンダーを行うことができます」と彼は言いました。 ベス・マルムスコグ、コロラド大学の数学者。 このため、地図が不当に操作されているかどうかを把握することがさらに困難になります。

明らかに異常な形をした地区の兆候が見られないまま、数学者たちはゲリマンダーを見つけるためのますます強力な統計的手法を開発してきました。 これらは、マップを数千または数百万の可能なマップの集合と比較することによって機能します。 この地図で、平均的な地図から予想されるよりも明らかに多くの民主党または共和党の議席が得られた場合、これは何か怪しいことが起こった可能性があることを示しています。

しかし、このようなアンサンブルを作成するのは、思っているよりも難しいのです。考えられるすべてのマップを考慮するのは現実的ではありません。スーパーコンピューターでは数えきれないほどの組み合わせが存在します。 最近の数学的進歩の多くは、この不可能なほど広大なシミュレーション可能空間をナビゲートする方法を示唆しており、数学者に公平か不公平かを判断する信頼できる方法を提供しています。

区画整理に関連する多くの事柄と同様、彼らの仕事も最終的には法廷で争われることになる。 過去XNUMX年間、ミズーリ州、ノースカロライナ州、オハイオ州、ミシガン州の選挙区再編の訴訟でシミュレーションが証拠として認められてきた。 そして、それらは議論の中心的な対象です。 アレン対ミリガン、重大なケース 最高裁判所で係属中 その中で黒人有権者は、アラバマ州が自分たちに不利になるように下院選挙区地図を描いたと非難している。 この事件でも、他の多くの事件と同様に、原告と被告の両方がシミュレーションに協力して弁護を行っている。 裁判所は、 決定を下すことが期待されている XNUMX月かXNUMX月に。

しかし、原告側弁護士の一人がXNUMX月の口頭弁論でサミュエル・アリト判事に語ったように、「シミュレーションは実際、答えよりも多くの疑問を生み出している」。

組み合わせ爆発

アンサンブルを生成する際の数学的な難しさを理解するには、非現実的な単純なマップを考えることから始めます。 たとえば、4 行 4 列のグリッドを想像してください。 これらの 117 の正方形を、地区ごとに 16 つの正方形を持つ 6 つの連続する地区に分割する方法は 6 通りあります。 そこから、いわゆる組み合わせ爆発として可能性が急速に拡大します。 それぞれ 451,206 つの正方形からなる 9 つの連続する地区からなる 9 行 700 列のグリッドには、10 通りの可能性があります。 それぞれ 10 つの正方形からなる 100 つの地区を持つ 10 行 XNUMX 列のグリッドですか? XNUMX兆を超えるオプション。 XNUMX 個の正方形がある XNUMX × XNUMX のグリッドの場合、XNUMX 地区の構成がいくつ存在するかは誰も知りません。

もちろん、典型的な州には 100 を超えるさまざまな管轄区域があり、それらを地区にグループ化することができます。 アナリストは多くの場合、投票区から候補地区を構築します。 たとえば、ノースカロライナ州には 2,500 以上の管区があるのに対し、ペンシルベニア州には 9,159 の管区があります。 公式の地区計画は通常、さらに詳細な国勢調査ブロックに基づいており、アラバマ州にはそのようなブロックが 185,976 あります。

各州には地区を描くための異なるルールがありますが、一般に、地区は連続していて「コンパクト」でなければならず、伝統的な地理的および政治的境界を維持し、人口がほぼ均等に近く、いわゆる利益共同体がバラバラにならないようにする必要があります。 投票権法はまた、すべての人種グループの有権者が「自分の選んだ代表者を選出する」平等な機会を確実に得られるような方法で選挙区を決めることも求めている。 これらすべての要件を調和させることは数学的に困難です。 再地区化に関する要件が増えれば増えるほど、「数学的問題はより複雑になる」とマルムスコグ氏は述べた。

過去 20 年間、多数の可能性のあるマップを生成するための主要な手法は、「ランダム シード アンド グロー」と呼ばれる手法でした。 これは見た目どおりに機能します。 数千の個々の投票区を、たとえば 10 の下院選挙区に統合したいとします。各選挙区には約 760,000 人が含まれなければなりません。 まず、特定の地区を「シード」する地区をランダムに選択します。 次に、地区内の人口が 760,000 人に近づくまで、隣接する学区をこのシードに追加します。 次に、残りの地区が見つかるまで、別の学区から始めて別の地区にシードを追加するというプロセスを繰り返します。

地区をコンパクトにするためにいくつかの比較的簡単な調整を行うだけで、この方法を使用して見栄えの良いマップを多数作成できます。 しかし、可能なマップの数は組み合わせによって爆発的に増加しているため、ランダム シード アンド グロウ技術によって作成された何百万ものマップでさえ、すべての可能なマップのごく一部にすぎません。 また、この部分が有効なマップのセット全体を代表しているという数学的証拠はありません。つまり、これを比較の基礎として使用すると、誤解を招く結論につながる可能性があります。

だからこそ、過去 XNUMX 年半ばに、次のような研究者が 今井康介、ハーバード大学の政府と統計の教授、そして ジョナサン・マッティングリーデューク大学の数学と統計学の教授である彼は、マルコフ連鎖モンテカルロ (MCMC) と呼ばれる手法を地図の作成に適用し始めました。

MCMC は、まず既存の地区マップをグラフ (線またはエッジで接続されたノードまたは点で構成される数学的構造) に変換することによって機能します。 各区域がノードになります。 実際に境内が境界線を共有している場合、それらはグラフではエッジによって結合されます。 初期の MCMC 手法、今井らによって説明された「フリップベース」手法など 2014論文、数学的に特殊な方法で、隣接する地区間で校区を交換することで機能しました。

マップをグラフとして考えることで、研究者は、ペロン・フロベニウスの定理と呼ばれるグラフ理論のツールを使用して、アルゴリズムを十分な時間 (数学者が混合時間と呼ぶ間隔) 実行できれば、適切にアルゴリズムが実行されることを示すことができます。考えられるすべての有効なマップの分布からのサンプル。 これは改善ですが、混合時間の長さを正確に厳密に証明することは通常はまだ不可能です。 マッティングリー氏は、「サンプリングが適切に行われたことを皆に証明する」最善の方法の問題は未解決のままだと述べた。 そこで数学者たちは、混合時間の限界をより適切に確立し、より早く限界に到達するために、MCMC の微調整に取り組んでいます。

2019年に研究者のグループがバージニア州代議員院の新しい地区地図を描くためのより良い方法に取り組んでいたとき、11つの進歩があった。 前年、連邦裁判所はバージニア州地図上の1の地区が黒人住民の投票力を弱める形で集中させているとして違憲であるとの判決を下していた。 さらに、バージニア州の地区再編プロセスには異常に厳しい制約があります。地区間の人口の偏差は 100% までです。 州議会選挙区が XNUMX あることを考えると、「これはかなり厳しい制限です」と同氏は述べた。 ダリル・デフォード、ワシントン州立大学の数学者で、バージニア州の地図の公平性を分析しました。 それは、グループが校区レベルで活動できないことを意味しました。 「一部の地区は基本的に大きすぎて有効な計画を立てることができなかった」とデフォード氏は語った。 マップをより小さな国勢調査ブロック単位に分割することも機能しませんでした。 約10万ステップを経た後、標準的なフリップベースのMCMCアルゴリズムは「空間全体から代表的なサンプルを得るには程遠いものでした」と同氏は述べた。

そこでデフォード氏と彼の同僚は、空間をより迅速に移動する方法を考え出しました。 可能な地図の全領域からサンプルを迅速に取得するために、地区の連続性を維持する方法で、多くの校区の地区割り当てを一度に変更する必要がありました。 これにより、マルコフ連鎖の各ステップの計算コストが高くなりましたが、各ステップが混合時間に非常に近づくことも意味しました。

彼らは、隣接する XNUMX つの地区をランダムに選択し、それらを結合して XNUMX つのユニットを作成することで機能する ReCom と呼ばれるアルゴリズムを考案しました。 本機は各地区が持っていたグラフ構造を継承しています。 ただし、隣接する校区を交換する代わりに、ReCom はスパニング ツリーと呼ばれる新しいグラフをランダムに作成します。このグラフは、ループを含まず、すべてのノードがすべてノードは接続されています。 ループがないため、いずれかのエッジを切断すると、結合された XNUMX つの地区が再び XNUMX つの部分に分割されます (木の枝を鋸で切り落とすと正確に XNUMX つの部分に切断されるのと同じです)。

通常、結果として得られる各コンポーネントにほぼ同数のノードを残すエッジを見つけるのは簡単です。ReCom はそのようなエッジをランダムに選択します。 (見つからない場合は、スパニング ツリーが再描画されます。) スパニング ツリーの統計により、コンパクトな地区が生成される自然な傾向もあります。 ReCom は各ステップで何百もの変更を加えるため、その発明者らは、一度に変更するプレシンクトが少ないフリップベースの方法よりも早く混合時間に達すると考えています。

現実世界の課題

バージニア州の人口制約が厳しいことだけが、この過程で考えられるねじれの原因ではない。 コロラド州には、隣接性とコンパクトさという一般的な制約を超える珍しい要件があります。コロラド州の法律では、学区が「競争力がある」ことも求められています。

この法律は競争力を漠然としか定義していないため、コロラド州の州議会選挙区マップの作成を担当する独立委員会は、過去のデータを使用して競争力のある選挙区を定義することを決定しました。 仮想選挙区が「競争力がある」ためには、過去 46 回の選挙で選ばれた人種の得票合計が、民主党、共和党ともに 54% から XNUMX% の間になければなりませんでした。

その後、委員会はデフォード、マルムスコグ、そして ジャンヌ・クレランド、コロラド大学ボルダー校の数学者、コロラド大学のマルムスコグの同僚であるフラビア・サンシエ・バルボーサとともに。 XNUMX 人の研究者は ReCom アルゴリズムを使用して、州の区画整理基準に従った数百万枚の地図のアンサンブルを生成しました。 次に、彼らはそれらのアンサンブルを使用して、「その競争範囲に入ることが予想される地区の数の値の範囲」を計算したとクレランド氏は述べた。 その後、委員会が新しい計画を立てる際に、数学者たちはそれが統計分析のどの範囲に該当するかを判断しました。 最終的に、立法再選挙委員会は、数学者たちがアンサンブルで見た平均よりも競争力の高い選挙区を含む地図を選択した、とクレランド氏は語った。

クレランド氏は、競争区は公平に聞こえるかもしれないが、実際には比例と矛盾する可能性があり、どちらかの政党の代表者数が州全体のその政党の有権者の数と一致するという目標と矛盾する可能性があると指摘した。 「結果が実際に50%に近い選挙区が多数ある場合、得票率のごくわずかな変化が議席シェアの割合に非常に大きな変化をもたらす可能性があります。」

今井氏は、初期計画から開始して微調整する ReCom のような MCMC 手法では、場合によっては「領域を探索するのに苦労する」ことを懸念していると述べた。 同氏は、考えられる有効なマップの空間は非常に多峰性であるため（互いに大きく異なる複数の優れた解が存在する可能性があることを意味する）、そのようなアルゴリズムは初期条件に近すぎるリスクがある可能性があると述べた。 だからこそ、今井氏は大学院生のコーリー・マッカータン氏とともに、「逐次モンテカルロ」（SMC）と呼ばれる新しい手法を論文で導入した。 プレプリント での出版が受理されました 応用統計年報。 SMC はまた、マップをグラフに変換し、ReCom と同様に、これらのグラフのスパニング ツリーを作成します。

SMC は、すべてのプレシンクトのノードを含む単一のスパニング ツリーを作成します。 次に、グラフの残りの部分から XNUMX つの地区だけを分離しようとします。 Imai と McCartan が指定した基準に基づいて、カットする最も有望なエッジを特定し、これらのエッジの XNUMX つをランダムに選択します。 次に、グラフの残りの部分でこのプロセスを繰り返し、必要な数の地区が作成されるまで、一度に XNUMX つの新しい地区を分割します。 このプロセスを何百万回も繰り返すことにより、SMC は何百万もの実行可能なマップを作成します。

数学的引数

計算による再地区化は、単一のマップが公平かどうかという比較的単純な問題を、何百万ものマップが公平かどうかという一見はるかに複雑な問題に効果的に置き換えます。 これは、単純な問題がはるかに複雑な問題と同等であることを示し、その後、より複雑な問題を解決するという数学の伝統に真っ向から位置づけられます。

2022 年 XNUMX 月、今井氏のチームは大規模なコレクションをリリースしました。 議会の区画整理地図シミュレーション 50 年国勢調査のデータに基づく、全 2020 州を対象としています。 どのような質問に答えようとしているかに応じて、調整するパラメータが多数あるため、彼らの希望は、彼らのツールがアンサンブル分析を一般の人に利用できるようにすることです。

今井氏は係争中の最高裁判所訴訟の原告側の専門証人である。 原告らは、同氏が結成したアンサンブルを利用して、アラバマ州の選挙区が黒人有権者の権利を剥奪することで投票権法に違反していると主張している。 しかし、訴訟を起こされているアラバマ州は、同氏の支持者らを利用して、地図は公正に描かれていると主張している。 裁判所がどのような判決を下すにせよ、選挙に関しては数学が常に政治と争う必要があることを示している。