Multidimensional Political Apportionment (Javier Cembrano, Jose Correa and Victor Verdugo)
Proceedings of the National Academy of Sciences, 119(15):e2109305119, 2022.
@article{CembranoCorreaVerdugo2022,
author = {Javier Cembrano and Jose Correa and Victor Verdugo},
doi = {10.1073/pnas.2109305119},
journal = {Proceedings of the National Academy of Sciences},
number = {15},
pages = {e2109305119},
title = {Multidimensional Political Apportionment},
volume = {119},
year = {2022},
}
Deciding how to allocate the seats of a deliberative assembly is one of the most fundamental problems in the political organization of societies and has been widely studied over two centuries already. 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 their existence is a computationally hard problem ($\mathsf{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 finally evaluate our approach by using the data from the recent 2021 Chilean Constitutional Convention election.
Impartial Selection with Additive Guarantees via Iterated Deletion (Javier Cembrano, Felix A. Fischer, David Hannon and Max Klimm)
EC 2022 – Proc. 23rd ACM Conference on Economics and Computation, pp. 1104–1105.
@inproceedings{CembranoFischerHannon+2022,
author = {Javier Cembrano and Felix A. Fischer and David Hannon and Max Klimm},
booktitle = {EC 2022 – Proc. 23rd ACM Conference on Economics and Computation},
doi = {10.1145/3490486.3538294},
pages = {1104--1105},
title = {Impartial Selection with Additive Guarantees via Iterated Deletion},
year = {2022},
}
Impartial selection is the selection of an individual from a group based on nominations by other members of the group, in such a way that individuals cannot influence their own chance of selection. We give a deterministic mechanism with an additive performance guarantee of $\mathcal{O}(n^{(1+\kappa)/2})$ in a setting with $n$ individuals where each individual casts $\mathcal{O}(n^\kappa)$ nominations, where $\kappa \in [0,1]$. For $\kappa =0$, i.e. when each individual casts at most a constant number of nominations, this bound is $\mathcal{O}(\sqrt{n})$. This matches the best-known guarantee for randomized mechanisms and a single nomination. For $\kappa=1$ the bound is $\mathcal{O}(n)$. This is trivial, as even a mechanism that never selects provides an additive guarantee of $n-1$. We show, however, that it is also best possible: for every deterministic impartial mechanism there exists a situation in which some individual is nominated by every other individual and the mechanism either does not select or selects an individual not nominated by anyone.
Optimal Impartial Correspondences (Javier Cembrano, Felix A. Fischer and Max Klimm)
WINE 2022 – Proc. 18th Conference on Web and Internet Economics, pp. 187–203.
@inproceedings{CembranoFischerKlimm2022,
author = {Javier Cembrano and Felix A. Fischer and Max Klimm},
booktitle = {WINE 2022 – Proc. 18th Conference on Web and Internet Economics},
title = {Optimal Impartial Correspondences},
year = {2022},
accepted = {07.09.2022},
doi = {10.1007/978-3-031-22832-2_11},
pages = {187--203},
}
We study mechanisms that select a subset of the vertex set of a directed graph in order to maximize the minimum indegree of any selected vertex, subject to an impartiality constraint that the selection of a particular vertex is independent of the outgoing edges of that vertex. For graphs with maximum outdegree $d$, we give a mechanism that selects at most $d+1$ vertices and only selects vertices whose indegree is at least the maximum indegree in the graph minus one. We then show that this is best possible in the sense that no impartial mechanism can only select vertices with maximum degree, even without any restriction on the number of selected vertices. We finally obtain the following trade-off between the maximum number of vertices selected and the minimum indegree of any selected vertex: when selecting at most $k$ of vertices out of $n$, it is possible to only select vertices whose indegree is at least the maximum indegree minus $\lfloor(n-2)/(k-1)\rfloor+1$.
