Redistricting from the Bottom Up: Sampling Communities of Interest with Differential Privacy

Resumen Técnico: Redistribución de abajo hacia arriba con Privacidad Diferencial

Planteamiento del Problema
Las Comisiones Independientes de Redistribución (IRC, por sus siglas en inglés) se utilizan cada vez más para facilitar una redistribución de abajo hacia arriba, con el objetivo de aislar el proceso de la manipulación partidista. Sin embargo, los procesos de testimonios públicos utilizados para recopilar datos de "Comunidades de Interés" (COI) son vulnerables a ataques adversarios. Ejemplos históricos de California y Florida demuestran que los operativos políticos pueden coordinar grupos para presentar testimonios guionizados o por delegación para manipular los límites de los distritos. Si bien los métodos de ensamble (Monte Carlo por Cadenas de Markov) son efectivos para detectar el gerrymandering de arriba hacia abajo, carecen de un mecanismo para incorporar el testimonio de las COI de una manera que sea robusta ante tales entradas adversarias. El desafío central es diseñar un algoritmo de redistribución que incorpore los datos de testimonios públicos sin permitir que un solo testimonio o un grupo coordinado dicte desproporcionadamente el resultado.

Metodología
Los autores proponen un marco que combina la Privacidad Diferencial (DP) con el muestreo de ensamble para generar planes de redistribución que respeten los testimonios de las COI, al tiempo que limitan la influencia de los datos individuales.

1. Representación de Datos:

   • El estado se modela como un grafo $G=(V, E)$ donde los vértices son grupos de bloques censales y las aristas conectan unidades adyacentes.
   • Los testimonios se codifican como vectores binarios que indican qué grupos de bloques desea mantener unidos una comunidad.
   • Los testimonios se agregan en clústeres geográficos basados en la proximidad.

2. Funciones de Puntuación:
   Los autores introducen dos funciones de puntuación distintas para medir la preservación de las COI:

   • Puntuación de Testimonio ($s_t$): Mide la proporción de testimonios individuales que permanecen enteramente dentro de un solo distrito. Es una métrica binaria de "todo o nada".
   • Puntuación de Clúster ($s_c$): Mide la fracción del peso total del clúster preservada en el "mejor" distrito para cada clúster. Esto permite una preservación parcial y es más granular.

3. Mecanismo de Muestreo:

   • Los autores utilizan el Mecanismo Exponencial para muestrear planes de redistribución de una distribución objetivo proporcional a $\exp(-\frac{\epsilon}{2\Delta(s)} s(t, \xi))$, donde $s$ es la función de puntuación elegida y $\Delta(s)$ es su sensibilidad.
   • Para muestrear de esta distribución, emplean el Caminata de Aristas Marcadas (MEW), un algoritmo de Monte Carlo por Cadenas de Markov (MCMC) elevado. El MEW opera sobre tuplas de árboles de expansión y aristas marcadas, lo que le permite recorrer el espacio de estados de manera más eficiente que las caminatas de giro local y converger a distribuciones independientes de las estructuras de los árboles de expansión.
   • La distribución objetivo también incluye un término de compacidad (Gaussiano sobre las aristas cortadas) centrado en el valor del plan promulgado para asegurar la validez geométrica.

4. Marco de Privacidad:

   • El sistema está definido como $(\epsilon, \delta)$-diferencialmente privado. La inclusión o exclusión de un solo testimonio (o un conjunto de datos vecino que difiere por un testimonio) resulta en un cambio acotado en la probabilidad de cualquier plan de salida.
   • La sensibilidad $\Delta(s)$ se calcula para ambas funciones de puntuación. La puntuación de testimonio tiene una sensibilidad de $1/T$ (donde $T$ es el número de testimonios), mientras que la puntuación de clúster tiene una sensibilidad más alta debido a la agregación de pesos.

Resultados Clave
El método se aplicó a la redistribución de ciclo medio de Missouri utilizando 808 testimonios de COI.

• Desempeño vs. Línea Base: El muestreo informado por COI superó consistentemente a una línea base no informada (muestreo basado únicamente en la compacidad) y al plan promulgado. El plan promulgado obtuvo 0.62 en la puntuación de testimonio y 0.71 en la puntuación de clúster, mientras que las distribuciones muestreadas con DP alcanzaron puntuaciones más altas a medida que aumentaba el presupuesto de privacidad ($\epsilon$).
• Compromiso entre Privacidad y Utilidad: A medida que $\epsilon$ aumentaba, los planes muestreados se desplazaban hacia puntuaciones más altas de preservación de COI. Sin embargo, con un $\epsilon$ muy alto, la cadena tuvo dificultades para mezclarse porque el mecanismo exponencial asignaba probabilidades ínfimas a las propuestas que disminuían la puntuación.
• Comparación de Funciones de Puntuación:
  • La Puntuación de Testimonio ofreció garantías de privacidad formal más fuertes (menor sensibilidad) pero exhibió un comportamiento de "sacrificio" contraintuitivo: a un $\epsilon$ alto, el muestreador dividiría algunos testimonios con mayor frecuencia para preservar otros, debido a la naturaleza discreta de la puntuación.
  • La Puntuación de Clúster proporcionó resultados más intuitivos y una mejor mezcla en presupuestos más altos, pero ofreció garantías de privacidad formal más débiles debido a su mayor sensibilidad.
• Robustez Adversaria: En un experimento donde un clúster de 9 testimonios fue reemplazado por datos adversarios que cubrían un área geográfica diferente:
  • Bajo la Puntuación de Clúster, el clúster adversario se preservó a tasas consistentes con la línea base a $\epsilon$ bajo, y se preservó cada vez más a medida que $\epsilon$ aumentaba.
  • Bajo la Puntuación de Testimonio, los testimonios adversarios eran cada vez más divididos a medida que $\epsilon$ aumentaba, efectivamente siendo sacrificados para preservar la integridad de los más de 800 testimonios restantes.
  • Los resultados sugieren que el método es robusto ante ataques coordinados de pequeña escala, funcionando mejor en la práctica de lo que los límites formales de privacidad de grupo (que se degradan linealmente con el número de atacantes) podrían implicar.
• Impacto Demográfico: Contrario a la intuición de que preservar las COI lleva a "empaquetar" a los votantes minoritarios o demócratas en distritos únicos, los resultados mostraron que una preservación de COI más fuerte en Missouri tendía a dispersar la representación minoritaria y demócrata de manera más uniforme a través de los tres principales distritos. Esto se atribuyó a la separación geográfica de los dos grandes centros urbanos de Missouri (St. Louis y Kansas City); mantener intactas las comunidades locales evitó la dilución de la representación en Kansas City, que fue dividida en el plan promulgado.

Significancia y Reivindicaciones
El artículo afirma ofrecer un marco novedoso para la redistribución "de abajo hacia arriba" que equilibra la incorporación de testimonios públicos con la robustez contra la manipulación adversaria.

• Robustez: La principal contribución es demostrar que la privacidad diferencial puede aplicarse a la distribución de salida de los planes de redistribución para limitar la influencia de un solo testimonio o un pequeño grupo coordinado, sin descartar los datos por completo.
• Aplicación Práctica: El estudio valida el enfoque utilizando datos del mundo real (testimonios de Missouri 2021) y un algoritmo MCMC específico (MEW) capaz de muestrear de distribuciones objetivo no estándar.
• Limitaciones: Los autores señalan modestamente que el método no resuelve el problema por completo; ataques coordinados suficientemente grandes aún podrían abrumar el mecanismo debido a la degradación lineal de la privacidad de grupo. El enfoque también depende de la disponibilidad de datos de testimonios estructurados (por ejemplo, a través de plataformas como Districtr) y requiere una selección cuidadosa de los parámetros de privacidad y los métodos de agrupación.

En conclusión, el artículo postula que, si bien las IRC son una herramienta prometedora, requieren salvaguardas matemáticas contra la manipulación. El marco DP-MEW propuesto proporciona un límite cuantificable de la influencia de las entradas adversarias, permitiendo la creación de planes de redistribución que están tanto informados por los intereses de la comunidad como resilientes a la subversión.