Los desafíos de D’Hondt y su aplicación a DecideChile (Parte 1)

Introducción

Para poder avanzar hacia el desarrollo del software de DecideChile, el equipo de Unholster tuvo que resolver una serie de desafíos técnicos que se fueron presentando. En esa línea, este artículo busca dar a conocer cómo se resolvieron y atacaron los diferentes problemas del proyecto.

Además de saber cómo programar, para poder comprender correctamente este artículo se recomienda estar familiarizado con los siguientes tópicos:

Método D’Hondt

Estructuras de datos:

Diccionario o Arreglo Asociativo Heap El código fuente presentado aquí se encuentra en el siguiente repositorio:

Diseño

Decisiones Básicas Se usarán las siguientes tecnologías en este proyecto: Python – Lenguaje de programación pytest – Librería para crear pruebas flake8 – Librería de análisis estático.

Lo anterior es parte del stack estándar de Unholster para el backend. Se construirá el proyecto como un paquete, que pueda ser importado en cualquier proyecto.

Entradas

De la definición misma del método D’Hondt, sabemos que lo mínimo que necesitamos son:

Candidatos con sus afiliaciones Escaños en disputa Si bien el backend de DecideChile tiene un modelo de datos definido para la información listada, creemos prudente desacoplarnos de ese modelo para lograr una herramienta que sea reusable.

Para candidatos proponemos usar un simple diccionario del siguiente estilo:

{ "id":1, "pacto":"FRENTE AMPLIO", "partido":"PARTIDO HUMANISTA", "candidato":"CAROLINA SALDIVIA SALAZAR", "votos":1022 } Con esto, aún estamos obligando a quien ejecuta la función a usar nombres específicos para los campos. Para abstraernos de eso, permitiremos al ejecutor que decida qué campos son relevantes en el algoritmo, usando una firma como la que se muestra a continuación:

dhondt(llaves_afiliaciones, llave_votos, escaños, registros ) Para el caso del diccionario mostrado anteriormente, la llamada podría ser algo como:

dhondt(["pacto","partido"], "votos", 3, registros ) Con registros siendo una lista de diccionarios como los definidos más arriba

Salidas

Como resultado queremos: Una lista con los candidatos que fueron electos Una lista con los candidatos que NO fueron electos En este caso bastará con retornar listas de los mismos diccionarios usados como entradas.

Pruebas

Para validar el funcionamiento de la librería construiremos un set de datos de prueba para el cual conocemos los resultados, estos sets serán ejecutados por la librería y se validarán de manera automática.

El código propuesto para la prueba es el siguiente:

def test_set(set, seats): data_set = load_data_set(set) results = load_results(set) dhondt = Dhondt( group_key_list=('pacto', 'partido'), votes_key='votos', seats=seats, records=data_set) if len(dhondt.winners) == 0 or len(dhondt.losers) == 0: assert(False) for winner in dhondt.winners: assert(winner['id'] in results['winners']) for loser in dhondt.losers: assert(loser['id'] in results['losers']) Los puntos claves: La prueba recibe un set de datos y la cantidad de escaños que se deben elegir. Para cada set de datos, carga además de los datos el resultado el cual usa para comparar. Se verifican dos cosas: Que los candidatos se clasifiquen correctamente en ganadores y perdedores Que ambas listas tengan al menos 1 resultado. (Dado que la forma en que construiremos el assert también haría el test pasar en caso de listas vacías) Ahora sólo queda construir los sets de datos, por suerte el Servel como parte de su proceso preparatorio a las elecciones entregó varios ejemplos de resultados de elecciones con los respectivos ganadores elegidos.

Se eligieron los resultados con los siguientes criterios:

Dos elecciones donde el resultado con D’Hondt de un nivel (pacto) da el resultado correcto (Distritos 1 y 28) Dos elecciones donde se requiere un D’Hondt de dos nivels (pacto, partido) para obtener el resultado correcto (Distritos 9 y 10) Esto nos permitirá construir un proceso D’Hondt de un nivel y validarlo, antes de avanzar al más complejo D’Hondt de dos niveles.

V1 – Un nivel

Resumen del Algoritmo El proceso se puede dividir en tres fases distintas:

  1. Agrupar Se agrupan los candidatos por pacto y se calcula el total de votos del grupo.
  1. Calcular Escaños

Para calcular los escaños a cada grupo debemos asignarle una serie de parámetros adicionales:

Escaños asignados: Inicialmente en 0. Cociente: Inicialmente al número de votos.

Usando una lista priorizada por cociente (usando un heap) procedemos a:

Extraer de la lista el pacto con el cociente más alto Aumentar en uno los escaños asignados a ese pacto Recalcular el cociente como (escaños_asignados)/(escaños_asignados+1) Reinsertar el pacto en la lista priorizada

Y repetimos el proceso hasta que se entreguen todos los escaños:

  1. Asignar escaños

Teniendo la cantidad de escaños asignados asociados a cada pacto, sólo nos queda ordenar por votación y agregar a la lista de ganadores los N primeros, y a la lista de perdedores el resto.

Código La función principal de ejecución, en base al proceso anteriormente descrito, queda como se muestra a continuación:

def _calculate(self, group_key, votes_key, seats):

# Agrupar
results_heap = self._generate_starting_heap(group_key, votes_key)
if results_heap:
    # Calcular Escaños
    results_heap = self._allocate_seats(
    group_key,
    votes_key,
    results_heap,
    seats)
 # Asignar Escaños
 self._assign_seats(results_heap, votes_key)

Ahora miremos en más detalle las implementaciones específicas:

Agrupar El código construido fue el siguiente:

Group = namedtuple('Group', 'quotient seats_won candidates group records')

def _generate_starting_heap(self, group_key, votes_key): heap = [] srtd_records = sorted(self._records, key=lambda r: r[group_key]) # 1 for key, records in groupby(srtd_records, key=lambda r: r[group_key]): # 2 records = list(sorted(records, key=lambda r: r[votes_key])) heapq.heappush(heap, Group( quotient=-sum(int(r[votes_key]) for r in records), # 3 seats_won=0, # 3 candidates=len(records), group=key, records=records )) # 4 return heap Que a grandes rasgos hace esto:

  1. Ordena los candidatos por pacto (requisito para el paso siguiente)
  2. Se agrupan los candidatos
  3. Se calculan los cocientes, y se inicializan los escaños ganados en 0
  4. Cada grupo se inserta en un heap (usando la libreria heapq)

Calcular

El código construido fue el siguiente:

def _allocate_seats(self, group_key, votes_key, results_heap, seats): for seat in range(seats): group = heapq.heappop(results_heap) # 1 if group.quotient == 0: # 2 heapq.heappush(results_heap, group) break seats_won = group.seats_won + 1 # 3 if group.seats_won < group.candidates: # 4 quotient = group.quotient * seats_won / (seats_won + 1) else: quotient = 0 heapq.heappush( results_heap, Group( quotient=quotient, seats_won=seats_won, candidates=group.candidates, group=group.group, records=group.records)) # 5 return results_heap Primero que nada, llamó la atención que la variable votes_key es totalmente innecesaria, pero quedo ahí de nuestra exploración inicial del problema.

Los puntos claves del código, los cuales se realizan tantas veces como escaños hay por ganar:

  1. Obtener el grupo con cociente más alto
  2. Si algún grupo tiene cociente 0, estamos en un caso en que hay muy pocos votantes o muy pocos candidatos por lo que D’Hondt no es aplicable
  3. Para el grupo con el cociente más alto aumentamos el número de escaños ganados.
  4. Si el grupo en cuestión ha ganado menos puestos que la cantidad de candidatos que tiene se recalcula el cociente, en caso contrario se setea el cociente en 0.
  5. Se reinserta el grupo en el heap

Asignar

El código construido fue el siguiente:

def _assign_seats(self, results_heap, votes_key): for group in results_heap: srtd_records = sorted(group.records, key=lambda r: int(r[votes_key])) # 1 for seated in range(group.seats_won): self.winners.append(srtd_records.pop()) # 2 for notseated in range(len(srtd_records)): self.losers.append(srtd_records.pop()) # 3 Esta sección es bastante más directa que las otras, las tareas posteriores se hacen para cada grupo:

  1. Se ordenan los registros del grupo por orden de votación (en una segunda inspección al parecer es innecesario porque ya lo hicimos anteriormente, una mejora futura).
  2. Por cada escaño ganado se extrae el candidato con mayor votación y se agrega a la lista de ganadores 3. Se agrega el resto de los candidatos a la lista de perdedores.

Pruebas

Ejecutando las pruebas vía py.test, obtenemos el siguiente resultado:

Si bien tenemos dos test fallidos, es esperable pues son los sets de datos que solo pueden ser pasados usando un D’Hondt multinivel.

V2 – Múltiples niveles

Cambios al Algoritmo La principal diferencia en cuanto al uso de múltiples niveles, es que debemos ejecutar las fases Agrupar y Calcular múltiples veces, donde para cada grupo con escaños ganados se ejecutará un nuevo D’Hondt usando solo los candidatos y escaños a asignar de ese grupo:

Lo anterior es relativamente directo mediante llamadas recursivas, la condición de término de la recursión es que no queda más jerarquía organizacional que cruzar (En Chile serían solo 2 niveles, Pacto y Partido)

Código

Los principales cambios ocurren en la función calcular:

def _calculate(self, group_key_list, votes_key, seats, records): current_group = group_key_list[0] if len(group_key_list) > 1: remainder_group_list = group_key_list[1:] else: remainder_group_list = None heap = self._generate_heap(current_group, votes_key, records) if heap: heap = self._allocate_seats( current_group, votes_key, heap, seats) if remainder_group_list is not None: for group in heap: self._calculate( remainder_group_list, votes_key, group.seats_won, group.records) else: self._assign_seats(heap, votes_key)

Pruebas

Ejecutando las pruebas vía py.test, obtenemos el siguiente resultado:

¡Excelente! Ahora tenemos una librería que puede calcular D’Hondt, para una cantidad arbitraria de niveles.

Casos de Borde y otras mejoras

Lo antes mencionado no es suficiente para cumplir todos los requisitos del método D’Hondt, debido a que aún no hemos probado por los siguientes casos:

Un pacto/partido debe elegir más candidatos de los que tiene (una inspección del código diría que no nos afecta, pero hay que probarlo de todas maneras). Empates, ya sea dentro de un partido/pacto o entre partidos o pactos, lo cual es particularmente engorroso porque el comportamiento esperado debería variar según cuando escaños quedan disponibles. Escenarios de baja votación donde los resultados podrían no estar definidos (particularmente relevante para los primeros cómputos). Adicionalmente las siguientes mejoras serían deseables:

Poder recibir cualquier objeto como récord no solo un diccionario, lo cual requeriría que en vez de recibir llaves, deberíamos recibir funciones. Revisar otros métodos eleccionarios y verificar que los métodos de entrada y salida son suficientes para soportar todos los procesos. Sin embargo, se nos acabó el espacio en esta ocasión, así que veremos estos casos en el siguiente post.

Software a medida, EleccionesConstanza Herrera