El Instituto de Ingeniería Matemática y Computacional (IMC) tiene el agrado de invitarlos al seminario que se dictará la próxima semana.
La charla tendrá un formato híbrido y se efectuará el miércoles 27 de octubre a las 13 horas, en el auditorio del edificio San Agustín del Campus San Joaquín. Concurrentemente se emitirá vía Zoom, cuyo enlace se puede pedir a través de nuestro email Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo..
El recinto tiene aforo y por ese motivo les pedimos a los estudiantes que deseen asistir presencialmente que confirmen vía email al correo antes mencionado.
Título: Multidimensional Apportionment Through Discrepancy Theory (Repartición multidimensional a través de la teoría de discrepancia).
Expositor: José Correa
Afiliación: Departamento de Ingeniería de Industrial, Universidad de Chile.
Fecha: Miércoles 27 de octubre de 2021, 1:00 PM - 2:00 PM.
Lugar: Auditorio San Agustín; Zoom.
Abstract:
Deciding how to allocate the seats of a house of representatives is one of the most fundamental problems in the political organization of societies, and has been widely studied over already two centuries. The idea of proportionality is at the core of most approaches to tackle this problem, and this notion is captured by the divisor methods, such as the Jefferson/D'Hondt method. In a seminal work, Balinski and Demange extended the single-dimensional idea of divisor methods to the setting in which the seat allocation is simultaneously determined by two dimensions, and proposed the so-called biproportional apportionment method. The method, currently used in several electoral systems, is however limited to two dimensions and the question of extending it is considered to be an important problem both theoretically and in practice. In this work we initiate the study of multidimensional proportional apportionment. We first formalize a notion of multidimensional proportionality that naturally extends that of Balinski and Demange. By means of analyzing an appropriate integer linear program we are able to prove that, in contrast to the two-dimensional case, the existence of multidimensional proportional apportionments is not guaranteed and deciding its existence is NP-complete. Interestingly, our main result asserts that it is possible to find approximate multidimensional proportional apportionments that deviate from the marginals by a small amount. The proof arises through the lens of discrepancy theory, mainly inspired by the celebrated Beck-Fiala Theorem.
We evaluate various methods based of 3-dimensional proportionality, using the data from the recent 2021 Chilean Constitutional Convention election. Besides the classical political and geographical dimensions, this election required the convention to be balanced in gender. The methods we consider are 3-dimensional in spirit but include further characteristics such as plurality constraints and/or minimum quotas for representation.
This is joint work with Javier Cembrano, Gonzalo Diaz, and Victor Verdugo. Preliminary versions appeared at EC 2021 and EAAMO 2021.
Bio:
José Correa is a full professor in the Department of Industrial Engineering at Universidad de Chile. Jose obtained a mathematical engineering degree from Universidad the Chile in 1999 and a PhD in Operations Research from MIT in 2004. His research, focusing in algorithmic game theory and mechanism design, has received numerous awards including an ACM SIGecom best paper award, an INFORMS Transportation Science and Logistics best paper awards, a Tucker prize finalist, and research awards from Amazon and Google. José has given keynote talks at several institutions and conferences and has been in the program committee of international computer science conferences. He also serves and has served in the editorial board of some of the leading journals of his field: Mathematical Programming B, Mathematics of Operations Research (as Game Theory Area Editor), and Operations Research.
