Multidimensional apportionment through discrepancy theory

Abstract

Decidir cómo asignar los escaños de un órgano representativo es uno de los problemas más fundamentales en la organización política de las sociedades, y ha sido ampliamente estudiado desde hace ya dos siglos. La idea de proporcionalidad es la esencia de la mayoría de las formas de abordar este problema y es una noción capturada por los métodos de divisores, tales como el método de Jefferson/D'Hondt o el de Webster/Sainte-Laguë. En un trabajo seminal, Balinski y Demange extendieron la idea de los métodos de divisores en una dimensión al ambiente en que la asignación es determinada en dos dimensiones simultáneamente, proponiendo el denominado método de asignación biproporcional. Este método, actualmente utilizado en varios sistemas electorales, está limitado a dos dimensiones, y su extensión a más dimensiones es considerada un problema relevante, tanto teóricamente como en la práctica.

En este trabajo iniciamos el estudio de la asignación multidimensional. En primer lugar, formalizamos una noción de proporcionalidad multidimensional que extiende naturalmente la de Balinski y Demange. Luego, a través del análisis de un programa lineal entero apropiado demostramos que, a diferencia del caso bidimensional, la existencia de asignaciones proporcionales multidimensionales no está garantizada y decidir su existencia es NP-completo. De manera interesante, nuestro resultado principal establece que es posible encontrar asignaciones proporcionales aproximadas en el caso multidimensional, que se desvían de las marginales en una cantidad pequeña. La idea central de esta demostración viene de la teoría de discrepancia, principalmente inspirada en el celebrado Teorema de Beck-Fiala. Específicamente, diseñamos un algoritmo para un problema relacionado de discrepancia en hipergrafos que puede ser de interés por sí solo.