Logo Zephyrnet

Toán học đã thay đổi hình dạng của Gerrymandering như thế nào | Tạp chí lượng tử

Ngày:

Giới thiệu

Cho đến gần đây, các quận được chỉ định vui vẻ có xu hướng nhô ra ngoài, có thể nhận dạng được bằng các tua xoắn của chúng. Đây không còn là trường hợp. “Với công nghệ hiện đại, bạn có thể tạo hình khá hiệu quả mà không làm cho hình dạng của bạn trở nên quá kỳ quặc,” nói Beth Malmskog, một nhà toán học tại Đại học Colorado. Điều này khiến cho việc xác định liệu một bản đồ có bị thao túng một cách không công bằng hay không trở nên khó khăn hơn nhiều.

Không có dấu hiệu nhận biết về một quận rõ ràng bị biến dạng đi qua, các nhà toán học đã và đang phát triển các phương pháp thống kê ngày càng mạnh mẽ để tìm kiếm những người thợ săn. Chúng hoạt động bằng cách so sánh một bản đồ với một tập hợp gồm hàng nghìn hoặc hàng triệu bản đồ có thể. Nếu bản đồ dẫn đến số ghế dành cho Đảng viên Đảng Dân chủ hoặc Đảng Cộng hòa nhiều hơn đáng kể so với dự kiến ​​từ một bản đồ trung bình, thì đây là dấu hiệu cho thấy điều gì đó đáng ngờ có thể đã xảy ra.

Nhưng việc tạo ra những tổ hợp như vậy phức tạp hơn người ta tưởng, bởi vì không thể xem xét tất cả các bản đồ khả thi — đơn giản là có quá nhiều tổ hợp mà bất kỳ siêu máy tính nào cũng có thể đếm được. Một số tiến bộ toán học gần đây đề xuất các cách để điều hướng không gian mô phỏng khả thi rộng lớn không tưởng này, mang lại cho các nhà toán học một cách đáng tin cậy để phân biệt công bằng với không công bằng.

Giống như rất nhiều điều liên quan đến tái phân chia khu vực, công việc của họ sẽ kết thúc tại tòa án. Trong năm năm qua, các mô phỏng đã được chấp nhận làm bằng chứng trong các vụ kiện tại tòa án tái phân chia khu vực ở Missouri, North Carolina, Ohio và Michigan. Và họ là những đối tượng tranh luận trung tâm trong Allen kiện Milligan, một trường hợp quan trọng đang chờ xử lý trước Tòa án tối cao trong đó các cử tri Da đen cáo buộc bang Alabama đã vẽ bản đồ khu vực bầu cử của Quốc hội để gây bất lợi cho họ. Trong trường hợp này, cũng như trong nhiều trường hợp khác, các mô phỏng đang được cả nguyên đơn và bị đơn tranh thủ để bào chữa cho trường hợp của họ. Tòa án là dự kiến ​​ban hành quyết định vào tháng sáu hoặc tháng bảy.

Tuy nhiên, như một trong những luật sư của nguyên đơn đã nói với Thẩm phán Samuel Alito trong các cuộc tranh luận bằng miệng vào tháng XNUMX, “các mô phỏng thực sự tạo ra nhiều câu hỏi hơn là chúng trả lời.”

vụ nổ tổ hợp

Để hiểu khó khăn toán học trong việc tạo ra một tập hợp, hãy bắt đầu bằng cách nghĩ về các bản đồ đơn giản phi thực tế. Ví dụ, hãy tưởng tượng một lưới 4 nhân 4. Có 117 cách khác nhau để chia 16 ô vuông này thành bốn quận liền kề với bốn ô vuông mỗi quận. Từ đó, các khả năng phát triển rất nhanh trong cái gọi là bùng nổ tổ hợp. Một lưới 6 x 6 với sáu quận liền kề có sáu ô vuông, mỗi quận có 451,206 khả năng. Một lưới 9 x 9 với chín quận, mỗi quận có chín ô vuông? Hơn 700 nghìn tỷ tùy chọn. Đối với lưới 10 x 10, với 100 ô vuông, không ai biết có bao nhiêu cấu hình 10 quận có thể có.

Tất nhiên, một tiểu bang điển hình có hơn 100 khu vực pháp lý khác nhau có thể được nhóm lại thành các quận. Các nhà phân tích thường xây dựng các khu vực khả thi từ các khu vực bỏ phiếu. Chẳng hạn, Bắc Carolina có hơn 2,500 khu bầu cử, trong khi Pennsylvania có 9,159. Các kế hoạch phân khu chính thức thường dựa trên các khối điều tra dân số thậm chí còn chi tiết hơn: Alabama có 185,976 khối như vậy.

Mỗi tiểu bang có các quy tắc khác nhau để vẽ các quận, nhưng nhìn chung, chúng phải liền kề và “nhỏ gọn”, bảo tồn các ranh giới địa lý và chính trị truyền thống, có dân số gần bằng nhau và tránh phá vỡ cái gọi là cộng đồng cùng lợi ích. Đạo luật về Quyền Bầu cử cũng yêu cầu các khu bầu cử phải được vẽ theo cách đảm bảo rằng các cử tri thuộc mọi nhóm chủng tộc đều có cơ hội bình đẳng để “bầu các đại diện mà họ lựa chọn.” Điều hòa tất cả các yêu cầu này là một thách thức về mặt toán học. Malmskog cho biết càng có nhiều yêu cầu về việc tái phân chia khu vực, thì “vấn đề toán học càng trở nên phức tạp hơn.”

Trong 20 năm qua, kỹ thuật chủ đạo để tạo ra nhiều bản đồ có thể là một kỹ thuật gọi là “gieo hạt và phát triển ngẫu nhiên”. Điều này hoạt động nhiều theo cách nó âm thanh. Giả sử bạn muốn kết hợp hàng nghìn khu vực bỏ phiếu riêng lẻ thành 10 khu vực bầu cử, mỗi khu vực phải bao gồm khoảng 760,000 người. Bạn bắt đầu bằng cách chọn ngẫu nhiên một khu vực để “gieo hạt” cho một quận cụ thể. Sau đó, bạn thêm các khu vực lân cận vào hạt giống này cho đến khi bạn có gần 760,000 người trong huyện. Sau đó, bạn lặp lại quy trình - bắt đầu với một khu vực bầu cử khác để gieo hạt cho một quận khác - cho đến khi bạn tìm ra các quận còn lại của mình.

Với một số chỉnh sửa tương đối đơn giản để đảm bảo các quận nhỏ gọn, có thể sử dụng phương pháp này để tạo ra nhiều bản đồ trông hợp lý. Nhưng do sự bùng nổ tổ hợp về số lượng các bản đồ có thể, thậm chí hàng triệu bản đồ được tạo bởi kỹ thuật gieo hạt và phát triển ngẫu nhiên chỉ chiếm một phần rất nhỏ trong tất cả các bản đồ có thể. Và không có bằng chứng toán học nào cho thấy phân số này đại diện cho toàn bộ tập hợp các bản đồ hợp lệ, có nghĩa là sử dụng nó làm cơ sở so sánh có thể dẫn đến kết luận sai lệch.

Đó là lý do tại sao vào giữa thập kỷ qua, các nhà nghiên cứu bao gồm Kosuke Imai, một giáo sư về chính phủ và thống kê tại Đại học Harvard, và Jonathan Mattingly, một giáo sư toán học và thống kê tại Đại học Duke, bắt đầu áp dụng một kỹ thuật gọi là Chuỗi Markov Monte Carlo, hay MCMC, để tạo bản đồ.

MCMC hoạt động bằng cách trước tiên chuyển đổi bản đồ quận hiện có thành biểu đồ — một cấu trúc toán học bao gồm các nút hoặc điểm, được kết nối bằng các đường hoặc cạnh. Mỗi khu vực trở thành một nút; nếu các khu bầu cử có chung đường viền trong đời thực, thì chúng được nối với nhau bằng một cạnh trong biểu đồ. Các phương pháp MCMC ban đầu, như phương pháp “dựa trên lật” được mô tả bởi Imai và các đồng nghiệp trong một tờ giấy 2014, hoạt động bằng cách hoán đổi các khu vực bầu cử giữa các quận giáp ranh theo một cách cụ thể về mặt toán học.

Bằng cách coi bản đồ của họ là một đồ thị, các nhà nghiên cứu có thể sử dụng một công cụ từ lý thuyết đồ thị gọi là định lý Perron-Frobenius để chỉ ra rằng, nếu thuật toán được phép chạy đủ lâu — một khoảng thời gian mà các nhà toán học gọi là thời gian trộn — thì nó sẽ hoạt động bình thường. mẫu từ phân phối của tất cả các bản đồ hợp lệ có thể. Đây là một cải tiến, nhưng thường vẫn không thể chứng minh chính xác thời gian trộn là bao lâu. Mattingly cho biết câu hỏi làm thế nào tốt nhất để “chứng minh với mọi người rằng chúng tôi đã làm tốt công việc lấy mẫu” vẫn chưa được giải quyết. Vì vậy, các nhà toán học đang nghiên cứu các điều chỉnh đối với MCMC để thiết lập tốt hơn các giới hạn về thời gian trộn — và đạt được giới hạn đó nhanh hơn.

Giới thiệu

Một bước tiến đã đến vào năm 2019, khi một nhóm các nhà nghiên cứu đang nghiên cứu một cách tốt hơn để vẽ một bản đồ quận mới cho Hạ viện Virginia. Năm trước, một tòa án liên bang đã phán quyết rằng 11 quận trên bản đồ của Virginia là vi hiến vì chúng tập trung cư dân Da đen theo cách làm giảm sức mạnh bỏ phiếu của họ. Hơn nữa, Virginia có một ràng buộc nghiêm ngặt khác thường trong quy trình tái phân chia khu vực: Các quận chỉ có thể sai lệch về dân số 1%. Cho rằng có 100 khu vực Hạ viện của bang, “đó là một giới hạn khá chặt chẽ,” nói Daryl DeFord, một nhà toán học tại Đại học Bang Washington, người đã phân tích tính công bằng của bản đồ Virginia. Điều đó có nghĩa là nhóm không thể hoạt động ở cấp độ khu vực bầu cử. DeFord nói: “Một số khu vực về cơ bản là quá lớn để lập một kế hoạch hợp lệ. Việc phân vùng bản đồ thành các đơn vị khối điều tra nhỏ hơn cũng không hoạt động. Sau khoảng 10 triệu bước, các thuật toán MCMC dựa trên lật tiêu chuẩn “không thể có được các mẫu đại diện từ toàn bộ không gian,” ông nói.

Vì vậy, DeFord và các đồng nghiệp của ông đã nghĩ ra một cách để di chuyển trong không gian nhanh hơn. Để nhanh chóng lấy được các mẫu từ toàn bộ không gian của các bản đồ có thể, họ cần thay đổi việc phân bổ quận cho nhiều khu vực bầu cử cùng một lúc theo cách duy trì sự tiếp giáp của các quận. Điều này làm cho mỗi bước trong chuỗi Markov trở nên tốn kém hơn về mặt tính toán, nhưng điều đó cũng có nghĩa là mỗi bước đưa chúng đến gần thời gian trộn hơn rất nhiều.

Họ đã nghĩ ra một thuật toán gọi là ReCom hoạt động bằng cách chọn ngẫu nhiên hai quận liền kề và hợp nhất chúng để tạo thành một đơn vị duy nhất. Đơn vị này kế thừa cấu trúc biểu đồ mà mỗi quận đã có. Nhưng thay vì hoán đổi các khu vực lân cận, ReCom tạo ngẫu nhiên một biểu đồ mới gọi là cây bao trùm kết nối các nút trong hai khu vực kết hợp (mỗi nút đại diện cho một khu vực) với nhau theo cách không chứa bất kỳ vòng lặp nào nhưng đảm bảo rằng tất cả các nút được kết nối. Bởi vì không có vòng lặp, nên việc cắt bất kỳ một cạnh nào sau đó sẽ chia hai quận kết hợp lại thành hai phần (giống như việc cưa bất kỳ nhánh cây nào sẽ cắt nó thành đúng hai phần).

Thường dễ dàng tìm thấy các cạnh để lại số lượng nút gần như bằng nhau trong mỗi thành phần kết quả — ReCom chọn ngẫu nhiên một cạnh như vậy. (Nếu không thể tìm thấy, nó sẽ vẽ lại cây bao trùm.) Do thống kê về cây bao trùm, điều này cũng có xu hướng tự nhiên là tạo ra các quận nhỏ gọn. Bởi vì ReCom áp đặt hàng trăm thay đổi ở mỗi bước, các nhà phát minh của nó tin rằng nó đạt đến thời gian trộn nhanh hơn so với các phương pháp dựa trên lật thay đổi ít phân khu hơn tại một thời điểm.

Những thách thức trong thế giới thực

Hạn chế dân số chặt chẽ của Virginia không phải là bước ngoặt duy nhất có thể xảy ra trong quá trình này. Colorado có một yêu cầu bất thường vượt ra ngoài những hạn chế điển hình về tính liền kề và nhỏ gọn: Luật Colorado cũng yêu cầu các quận phải “cạnh tranh”.

Luật chỉ định nghĩa một cách mơ hồ về khả năng cạnh tranh, vì vậy ủy ban độc lập chịu trách nhiệm vẽ bản đồ khu vực lập pháp của bang Colorado đã quyết định xác định khu vực cạnh tranh bằng cách sử dụng dữ liệu lịch sử. Để một khu vực giả định trở nên “cạnh tranh”, tổng số phiếu bầu cho các chủng tộc được chọn trong ba cuộc bầu cử trước đó, cho cả Đảng Dân chủ và Đảng Cộng hòa, phải nằm trong khoảng từ 46% đến 54%.

Ủy ban sau đó chuyển sang DeFord, Malmskog và Jeanne Clland, một nhà toán học tại Đại học Colorado, Boulder, cùng với Flavia Sancier-Barbosa, một đồng nghiệp của Malmskog's tại Đại học Colorado. Bốn nhà nghiên cứu đã sử dụng thuật toán ReCom để tạo tập hợp hàng triệu bản đồ tuân theo các tiêu chí phân chia lại khu vực của tiểu bang; sau đó, họ sử dụng các tập hợp đó để tìm ra “phạm vi giá trị cho số lượng quận mà bạn có thể mong đợi sẽ rơi vào phạm vi cạnh tranh đó,” Clelland nói. Sau đó, khi ủy ban vạch ra các kế hoạch mới, các nhà toán học xác định xem họ rơi vào đâu trong phân tích thống kê. Cuối cùng, ủy ban tái phân chia khu vực lập pháp đã chọn một bản đồ có nhiều quận cạnh tranh hơn so với mức trung bình mà các nhà toán học nhìn thấy trong quần thể của họ, Clelland nói.

Clelland lưu ý rằng mặc dù các khu vực cạnh tranh nghe có vẻ công bằng, nhưng trên thực tế, chúng có thể mâu thuẫn với tỷ lệ, mục tiêu là số lượng đại diện của một trong hai đảng phải phù hợp với số lượng cử tri trong đảng đó trên toàn tiểu bang. “Nếu bạn có nhiều quận mà kết quả thực sự gần 50%, thì một thay đổi rất nhỏ trong tỷ lệ phiếu bầu có thể tạo ra thay đổi rất lớn trong tỷ lệ phiếu bầu.”

Giới thiệu

Imai cho biết anh ấy lo ngại rằng trong một số trường hợp nhất định, các phương pháp MCMC như ReCom bắt đầu từ một kế hoạch ban đầu và điều chỉnh nó “gặp khó khăn trong việc khám phá không gian.” Ông nói, vì không gian của các bản đồ hợp lệ có thể có là rất đa phương thức (có nghĩa là có thể có nhiều giải pháp tốt rất khác nhau), các thuật toán như vậy có thể gặp rủi ro ở quá gần với các điều kiện ban đầu của chúng. Đó là lý do tại sao, cùng với sinh viên tốt nghiệp của mình là Cory McCartan, Imai đã giới thiệu một phương pháp mới gọi là “Monte Carlo tuần tự,” hoặc SMC, trong một in sẵn đã được chấp nhận để xuất bản trong Biên niên sử thống kê ứng dụng. SMC cũng dịch các bản đồ thành đồ thị và giống như ReCom, tạo ra các cây bao trùm của các đồ thị này.

SMC tạo một cây bao trùm duy nhất bao gồm một nút cho mọi phân khu. Sau đó, nó cố gắng tách riêng một quận khỏi phần còn lại của biểu đồ. Nó xác định các cạnh hứa hẹn nhất để cắt dựa trên các tiêu chí mà Imai và McCartan chỉ định, sau đó nó chọn ngẫu nhiên một trong các cạnh này. Sau đó, nó lặp lại quy trình trên phần còn lại của biểu đồ, tách một quận mới tại một thời điểm cho đến khi số lượng quận cần thiết được tạo ra. Bằng cách lặp lại quy trình này hàng triệu lần, SMC tạo ra hàng triệu bản đồ khả thi.

Đối số toán học

Tái phân chia khu vực bằng máy tính thay thế một cách hiệu quả câu hỏi tương đối đơn giản về việc liệu một bản đồ đơn lẻ có công bằng hay không bằng câu hỏi có vẻ phức tạp hơn nhiều là liệu hàng triệu bản đồ có công bằng hay không. Điều này đặt nó thẳng vào truyền thống toán học chỉ ra rằng một vấn đề đơn giản tương đương với một vấn đề phức tạp hơn nhiều, và sau đó giải quyết vấn đề phức tạp hơn.

Vào tháng 2022 năm XNUMX, nhóm của Imai đã phát hành một bộ sưu tập lớn gồm mô phỏng bản đồ phân chia lại khu vực quốc hội cho tất cả 50 tiểu bang dựa trên dữ liệu từ cuộc điều tra dân số năm 2020. Vì có nhiều tham số để điều chỉnh, tùy thuộc vào câu hỏi mà bạn đang cố gắng trả lời, nên họ hy vọng rằng công cụ của họ sẽ cung cấp phân tích tập hợp cho đại chúng.

Imai là nhân chứng chuyên môn cho các nguyên đơn trong vụ án đang chờ xử lý của Tòa án Tối cao. Các nguyên đơn đang tranh luận, sử dụng các quần thể do anh ấy tạo ra, rằng các quận của Alabama vi phạm Đạo luật về Quyền Bầu cử bằng cách tước quyền bầu cử của cử tri Da đen. Nhưng bang Alabama, nơi đang bị kiện, đang sử dụng nhóm của mình để lập luận rằng bản đồ được vẽ khá công bằng. Bất kể quyết định của tòa án là gì, điều đó cho thấy rằng, khi nói đến các cuộc bầu cử, toán học sẽ luôn cần phải đấu tranh với chính trị.

tại chỗ_img

Mã xác nhận

Mã xác nhận

Tin tức mới nhất

tại chỗ_img