Fakultät II - Mathematik und Naturwissenschaften

Institut für Mathematik, Secr. MA 5-2

Technische Universität Berlin

Straße des 17. Juni 136

10623 Berlin

Office: TEL 505

Telephone: +49 30 314 23598

Email: (lastname)@math.tu-berlin.de

**Optimal Impartial Mechanisms**

DFG - Project number 431465007. Project head: Max Klimm

- Impartial Selection with Additive Guarantees via Iterated Deletion ( )

Games and Economic Behavior, 144:203–224, 2024.

@article{CembranoFischerHannon+2024,

author = {Javier Cembrano and Felix Fischer and David Hannon and Max Klimm},

title = {Impartial Selection with Additive Guarantees via Iterated Deletion},

journal = {Games and Economic Behavior},

year = {2024},

doi = {10.1016/j.geb.2024.01.008},

volume = {144},

pages = {203--224},

}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. For this problem, we give a deterministic mechanism with an additive performance guarantee of $O(n^{(1+\kappa)/2})$ in a setting with $n$ individuals where each individual casts $O(n^{\kappa})$ nominations, where $\kappa\in[0,1]$. For $\kappa=0$, ie when each individual casts at most a constant number of nominations, this bound is $O(\sqrt{n})$. This matches the best-known guarantee for randomized mechanisms and a single nomination. For $\kappa=1$ the bound is $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.

- Improved Bounds for Single-Nomination Impartial Selection ( )

EC 2023 – Proc. 24th ACM Conference on Economics and Computation, pp. 449.

@inproceedings{CembranoFischerKlimm2023,

author = {Javier Cembrano and Felix Fischer and Max Klimm},

title = {Improved Bounds for Single-Nomination Impartial Selection},

booktitle = {EC 2023 – Proc. 24th ACM Conference on Economics and Computation},

year = {2023},

doi = {10.1145/3580507.3597693},

pages = {449},

arxiv = {2305.09998},

}We give new bounds for the single-nomination model of impartial selection, a problem proposed by Holzman and Moulin (Econometrica, 2013). A selection mechanism, which may be randomized, selects one individual from a group of $n$ based on nominations among members of the group; a mechanism is impartial if the selection of an individual is independent of nominations cast by that individual, and $\alpha$-optimal if under any circumstance the expected number of nominations received by the selected individual is at least $\alpha$ times that received by any individual. In a many-nominations model, where individuals may cast an arbitrary number of nominations, the so-called permutation mechanism is $1/2$-optimal, and this is best possible. In the single-nomination model, where each individual casts exactly one nomination, the permutation mechanism does better and prior to this work was known to be $67/108$-optimal but no better than $2/3$-optimal. We show that it is in fact $2/3$-optimal for all $n$. This result is obtained via tight bounds on the performance of the mechanism for graphs with maximum degree $\Delta$, for any $\Delta$, which we prove using an adversarial argument. We then show that the permutation mechanism is not best possible; indeed, by combining the permutation mechanism, another mechanism called plurality with runner-up, and some new ideas, $2105/3147$-optimality can be achieved for all $n$. We finally give new upper bounds on $\alpha$ for any $\alpha$-optimal impartial mechanism. They improve on the existing upper bounds for all $n \geq 7$ and imply that no impartial mechanism can be better than $76/105$-optimal for all $n$; they do not preclude the existence of a (3/4−\varepsilon)-optimal impartial mechanism for arbitrary $\varepsilon > 0$ if $n$ is large. - Deterministic Impartial Selection with Weights ( )

WINE 2023 – Proc. 19th Conference on Web and Internet Economics, Springer Nature Switzerland, pp. 151–168.

@inproceedings{CembranoGriesbachStahlberg2023,

author = {Javier Cembrano and Svenja M. Griesbach and Maximilian J. Stahlberg},

title = {Deterministic Impartial Selection with Weights},

editor = {Jugal Garg and Max Klimm and Yuqing Kong},

booktitle = {WINE 2023 – Proc. 19th Conference on Web and Internet Economics},

series = {LNCS},

volume = {14413},

publisher = {Springer Nature Switzerland},

address = {Cham},

year = {2023},

pages = {151--168},

doi = {10.1007/978-3-031-48974-7\_9},

arxiv = {2310.14991},

}In the impartial selection problem, a subset of agents up to a fixed size $k$ among a group of $n$ is to be chosen based on votes cast by the agents themselves. A selection mechanism is impartial if no agent can influence its own chance of being selected by changing its vote. It is $\alpha$-optimal if, for every instance, the ratio between the votes received by the selected subset is at least a fraction of $\alpha$ of the votes received by the subset of size $k$ with the highest number of votes. We study deterministic impartial mechanisms in a more general setting with arbitrarily weighted votes and provide the first approximation guarantee, roughly $1/\lceil 2n/k\rceil$. When the number of agents to select is large enough compared to the total number of agents, this yields an improvement on the previously best known approximation ratio of $1/k$ for the unweighted setting. We further show that our mechanism can be adapted to the impartial assignment problem, in which multiple sets of up to $k$ agents are to be selected, with a loss in the approximation ratio of $1/2$. - Impartial Rank Aggregation ( )

Preprint, 2023.

@techreport{CembranoFischerKlimm+2023,

author = {Javier Cembrano and Felix Fischer and Max Klimm},

title = {Impartial Rank Aggregation},

year = {2023},

arxiv = {2310.13141},

}We study functions that produce a ranking of $n$ individuals from $n$ such rankings and are impartial in the sense that the position of an individual in the output ranking does not depend on the input ranking submitted by that individual. When $n \geq 4$, two properties concerning the quality of the output in relation to the input can be achieved in addition to impartiality: individual full rank, which requires that each individual can appear in any position of the output ranking; and monotonicity, which requires that an individual cannot move down in the output ranking if it moves up in an input ranking. When $n \geq 5$, monotonicity can be dropped to strengthen individual full rank to weak unanimity, requiring that a ranking submitted by every individual must be chosen as the output ranking. Mechanisms achieving these results can be implemented in polynomial time. Both results are best possible in terms of their dependence on $n$. The second result cannot be strengthened further to a notion of unanimity that requires agreement on pairwise comparisons to be preserved.

- Multidimensional Political Apportionment ( )

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 ( )

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 ( )

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},

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$.

- Multidimensional Apportionment through Discrepancy Theory ( )

EC 2021 – Proc. 22nd ACM Conference on Economics and Computation, pp. 287–288.

@inproceedings{CembranoCorreaVerdugo2021,

author = {Javier Cembrano and Jose Correa and Victor Verdugo},

booktitle = {EC 2021 -- Proc. 22nd ACM Conference on Economics and Computation},

doi = {10.1145/3465456.3467596},

pages = {287--288},

title = {Multidimensional Apportionment through Discrepancy Theory},

year = {2021},

} - Proportional Apportionment: A Case Study From the Chilean Constitutional Convention ( )

EAAMO 2021 - Proc. 1st ACM conference on Equity and Access in Algorithms, Mechanisms, and Optimization, pp. 1–9.

@inproceedings{CembranoCorreaDiaz+2021,

author = {Javier Cembrano and Jose Correa and Gonzalo Diaz and Victor Verdugo},

booktitle = {EAAMO 2021 - Proc. 1st ACM conference on Equity and Access in Algorithms, Mechanisms, and Optimization},

doi = {10.1145/3465416.3483295},

pages = {1--9},

title = {Proportional Apportionment: A Case Study From the Chilean Constitutional Convention},

year = {2021},

}How to elect the representatives in legislative bodies is a question that every modern democracy has to answer. This design task has to consider various elements so as to fulfill the citizens' expectations and contribute to maintaining a healthy democracy. In this work, we present five proposals of electoral methods based on proportional representation that extend the notion of proportionality to several dimensions: For instance, simultaneous proportionality in political, geographical, and gender representation. We also consider including two additional desirable properties for electoral methods: A minimum threshold to obtain political representation, and the incorporation of plurality voting, guaranteeing the election of the highest voted candidate in each district. We use the Chilean Constitutional Convention election (May 15–16, 2021) results as a testing ground, and compare the apportionment obtained under each method according to four criteria: Proportionality, representativeness, robustness, and voting power. We conclude that it is feasible to design and implement an electoral method satisfying all mentioned properties. Our findings may be useful in assessing electoral designs in other contexts as well.