Multidimensional Apportionment Through Discrepancy Theory. & Determination of functions by the metric slope.

Speaker 1: Víctor Verdugo

Title: Multidimensional Apportionment Through Discrepancy Theory.

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 can 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 on 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 José Correa, Javier Cembrano and Gonzalo Diaz (PNAS 2022, EC 2021 and EAAMO 2021).

Speaker 2: David Salas

Title: Determination of functions by the metric slope.

Abstract: In the seminal work of Boulmezaoud, Cieutat and Daniilidis (SIAM J. Optim. 2018), we discover that smooth convex functions that are bounded from below can be determined uniquely by their slopes. This result was extended for lower semicontinuous convex functions bounded from below in Hilbert spaces by Pérez-Aros, Salas and Vilches (Math. Program., 2021) and to general Banach Spaces by Thibault and Zagrodny (Commun. Contemp. Math. 2022). In a recent work, a similar result was obtained by Daniilidis and Salas (Proc. Amer. Math. Soc. 2022) for continuous functions, not necessarily convex, over metric spaces with a coercivity condition.  In this presentation, we will discuss these different results, and the evolution of the techniques used to obtain them.

Date: Aug 24, 2022 at 10:00:00 h
Venue: Sala de Seminario John Von Neuman, CMM, Beauchef 851, Torre Norte, Piso 7.
Speaker: Víctor Verduro & David Salas
Affiliation: Universidad de O'Higgins
Coordinator: Emilio Vilches
More info at:
Event website

Posted on Aug 19, 2022 in Optimization and Equilibrium, Seminars