{"id":{"repo_id":"chile","oai_identifier":"oai:repositorio.uchile.cl:2250/181346"},"canonical_url":"https://search.dev.ndltd.org/etd/chile/oai:repositorio.uchile.cl:2250/181346","repository":{"repo_id":"chile","name":"Universidad de Chile","base_url":"https://repositorio.uchile.cl/oai/request"},"display":{"title":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Cembrano Lassarre, Javier Alberto"],"institution":"Universidad de Chile","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Correa Haeussler, José","Verdugo Silva, Víctor"],"committee_chairs":[],"committee_members":[],"year":2021,"date_issued":"2021","date_published":"2021","updated_at":"2026-07-27T19:09:47Z","subjects":["Elección social","Optimización matemática","Algoritmos"],"languages":["es"],"rights":["Attribution-NonCommercial-NoDerivs 3.0 Chile"],"rights_urls":["http://creativecommons.org/licenses/by-nc-nd/3.0/cl/"],"identifier_entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["10.58011/bz3d-v793"],"render_values":[{"text":"10.58011/bz3d-v793","href":"https://doi.org/10.58011/bz3d-v793","code":true}]}]},"links":{"outbound_url":"https://repositorio.uchile.cl/handle/2250/181346","outbound_label":"Repository record","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Correa Haeussler, José","Verdugo Silva, Víctor"]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Ordóñez Pizarro, Fernando"]},{"key":"dc:creator","label":"Author","values":["Cembrano Lassarre, Javier Alberto"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2021-08-19T22:09:29Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2021-08-19T22:09:29Z"]},{"key":"dc:date.issued","label":"Date","values":["2021"]},{"key":"dc:publisher","label":"Institution","values":["Universidad de Chile"]},{"key":"dc:type","label":"Dc Type","values":["Tesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Elección social","Optimización matemática","Algoritmos"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["es"]},{"key":"dc:rights","label":"Dc Rights","values":["Attribution-NonCommercial-NoDerivs 3.0 Chile"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://creativecommons.org/licenses/by-nc-nd/3.0/cl/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["10.58011/bz3d-v793"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://repositorio.uchile.cl/handle/2250/181346"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Tesis para optar al grado de Magíster en Gestión de Operaciones","Memoria para optar al título de Ingeniero Civil Industrial"]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["Multidimensional apportionment through discrepancy theory"]}]}],"canonical_facts":{"dc:contributor.advisor":["Correa Haeussler, José","Verdugo Silva, Víctor"],"dc:contributor.other":["Ordóñez Pizarro, Fernando"],"dc:creator":["Cembrano Lassarre, Javier Alberto"],"dc:date.accessioned":["2021-08-19T22:09:29Z"],"dc:date.available":["2021-08-19T22:09:29Z"],"dc:date.issued":["2021"],"dc:description":["Tesis para optar al grado de Magíster en Gestión de Operaciones","Memoria para optar al título de Ingeniero Civil Industrial"],"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."],"dc:identifier.other":["10.58011/bz3d-v793"],"dc:identifier.uri":["https://repositorio.uchile.cl/handle/2250/181346"],"dc:language.iso":["es"],"dc:publisher":["Universidad de Chile"],"dc:rights":["Attribution-NonCommercial-NoDerivs 3.0 Chile"],"dc:rights.uri":["http://creativecommons.org/licenses/by-nc-nd/3.0/cl/"],"dc:subject":["Elección social","Optimización matemática","Algoritmos"],"dc:title":["Multidimensional apportionment through discrepancy theory"],"dc:type":["Tesis"]},"updated_at":"2026-07-27T19:09:47Z"}