Multidimensional apportionment through discrepancy theory
Professor Advisor
dc.contributor.advisor
Correa Haeussler, José
Professor Advisor
dc.contributor.advisor
Verdugo Silva, Víctor
Author
dc.contributor.author
Cembrano Lassarre, Javier Alberto
Associate professor
dc.contributor.other
Ordóñez Pizarro, Fernando
Admission date
dc.date.accessioned
2021-08-19T22:09:29Z
Available date
dc.date.available
2021-08-19T22:09:29Z
Publication date
dc.date.issued
2021
Identifier
dc.identifier.uri
https://repositorio.uchile.cl/handle/2250/181346
General note
dc.description
Tesis para optar al grado de Magíster en Gestión de Operaciones
es_ES
General note
dc.description
Memoria para optar al título de Ingeniero Civil Industrial
Abstract
dc.description.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.