Arkadii Slinko

AIJ Journal 2025 Journal Article

Drawing a map of elections

• Stanisław Szufa
• Niclas Boehmer
• Robert Bredereck
• Piotr Faliszewski
• Rolf Niedermeier
• Piotr Skowron
• Arkadii Slinko
• Nimrod Talmon

Our main contribution is the introduction of the map of elections framework. A map of elections consists of three main elements: (1) a dataset of elections (i. e. , collections of ordinal votes over given sets of candidates), (2) a way of measuring similarities between these elections, and (3) a representation of the elections in the 2D Euclidean space as points, so that the more similar two elections are, the closer are their points. In our maps, we mostly focus on datasets of synthetic elections, but we also show an example of a map over real-life ones. To measure similarities, we would have preferred to use, e. g. , the isomorphic swap distance, but this is infeasible due to its high computational complexity. Hence, we propose polynomial-time computable positionwise distance and use it instead. Regarding the representations in 2D Euclidean space, we mostly use the Kamada-Kawai algorithm, but we also show two alternatives. We develop the necessary theoretical results to form our maps and argue experimentally that they are accurate and credible. Further, we show how coloring the elections in a map according to various criteria helps in analyzing results of a number of experiments. In particular, we show colorings according to the scores of winning candidates or committees, running times of ILP-based winner determination algorithms, and approximation ratios achieved by particular algorithms.

IJCAI Conference 2022 Conference Paper

How to Sample Approval Elections?

• Stanisław Szufa
• Piotr Faliszewski
• Łukasz Janeczko
• Martin Lackner
• Arkadii Slinko
• Krzysztof Sornat
• Nimrod Talmon

We extend the map-of-elections framework to the case of approval elections. While doing so, we study a number of statistical cultures, including some new ones, and we analyze their properties. We find that approval elections can be understood in terms of the average number of approvals in the votes, and the extent to which the votes are chaotic.

AAAI Conference 2019 Conference Paper

How Similar Are Two Elections?

• Piotr Faliszewski
• Piotr Skowron
• Arkadii Slinko
• Stanisław Szufa
• Nimrod Talmon

We introduce the ELECTION ISOMORPHISM problem and a family of its approximate variants, which we refer to as d- ISOMORPHISM DISTANCE (d-ID) problems (where d is a metric between preference orders). We show that ELECTION ISOMORPHISM is polynomial-time solvable, and that the d- ISOMORPHISM DISTANCE problems generalize various classic rank-aggregation methods (e. g. , those of Kemeny and Litvak). We establish the complexity of our problems (including their inapproximability) and provide initial experiments regarding the ability to solve them in practice.

IJCAI Conference 2018 Conference Paper

Egalitarian Committee Scoring Rules

• Haris Aziz
• Piotr Faliszewski
• Bernard Grofman
• Arkadii Slinko
• Nimrod Talmon

We introduce and study the class of egalitarian variants of committee scoring rules, where instead of summing up the scores that voters assign to committees---as is done in the utilitarian variants---the score of a committee is taken to be the lowest score assigned to it by any voter. We focus on five rules, which are egalitarian analogues of SNTV, the k-Borda rule, the Chamberlin--Courant rule, the Bloc rule, and the Pessimist rule. We establish their computational complexity, provide their initial axiomatic study, and perform experiments to represent the action of these rules graphically.

AAMAS Conference 2017 Conference Paper

Beyond Electing and Ranking: Collective Dominating Chains, Dominating Subsets and Dichotomies

• Jé rô me Lang
• Jé rô me Monnot
• Arkadii Slinko
• William S. Zwicker

IJCAI Conference 2017 Conference Paper

Multiwinner Rules on Paths From k-Borda to Chamberlin–Courant

• Piotr Faliszewski
• Piotr Skowron
• Arkadii Slinko
• Nimrod Talmon

The classical multiwinner rules are designed for particular purposes. For example, variants of k-Borda are used to find k best competitors in judging contests while the Chamberlin-Courant rule is used to select a diverse set of k products. These rules represent two extremes of the multiwinner world. At times, however, one might need to find an appropriate trade-off between these two extremes. We explore continuous transitions from k-Borda to Chamberlin-Courant and study intermediate rules.

AAAI Conference 2017 Conference Paper

What Do Multiwinner Voting Rules Do? An Experiment Over the Two-Dimensional Euclidean Domain

• Edith Elkind
• Piotr Faliszewski
• Jean-Francois Laslier
• Piotr Skowron
• Arkadii Slinko
• Nimrod Talmon

We visualize aggregate outputs of popular multiwinner voting rules—SNTV, STV, Bloc, k-Borda, Monroe, Chamberlin– Courant, and PAV—for elections generated according to the two-dimensional Euclidean model. We consider three applications of multiwinner voting, namely, parliamentary elections, portfolio/movie selection, and shortlisting, and use our results to understand which of our rules seem to be best suited for each application. In particular, we show that STV (one of the few nontrivial rules used in real high-stake elections) exhibits excellent performance, whereas the Bloc rule (also often used in practice) performs poorly.

AAMAS Conference 2016 Conference Paper

Achieving Fully Proportional Representation by Clustering Voters

• Piotr Faliszewski
• Arkadii Slinko
• Kolja Stahl
• Nimrod Talmon

Both the Chamberlin–Courant and Monroe rules are voting rules solving the problem of so-called fully proportional representation: they select committees whose members represent the voters so that voters’ satisfaction with their assigned representatives is maximized. These rules suffer from a common disadvantage, being that it is computationally intractable to compute the winning committee exactly. As both of these rules, explicitly or implicitly, partition voters, they can be seen as clustering the voters so that the voters in each group share the same representative. This suggests studying approximation algorithms for these voting rules by means of cluster analysis, which is the subject of this paper. We develop several algorithms based on clustering the voters and analyze their performance experimentally. General Terms Algorithms, Experimentation

IJCAI Conference 2016 Conference Paper

Committee Scoring Rules: Axiomatic Classification and Hierarchy

• Piotr Faliszewski
• Piotr Skowron
• Arkadii Slinko
• Nimrod Talmon

We consider several natural classes of committee scoring rules, namely, weakly separable, representation-focused, top-k-counting, OWA-based, and decomposable rules. We study some of their axiomatic properties, especially properties of monotonicity, and concentrate on containment relations between them. We characterize SNTV, Bloc, and k-approval Chamberlin-Courant, as the only rules in certain intersections of these classes. We introduce decomposable rules, describe some of their applications, and show that the class of decomposable rules strictly contains the class of OWA-based rules.

AAAI Conference 2016 Conference Paper

Multiwinner Analogues of the Plurality Rule: Axiomatic and Algorithmic Perspectives

• Piotr Faliszewski
• Piot Skowron
• Arkadii Slinko
• Nimrod Talmon

We characterize the class of committee scoring rules that satisfy the fixed-majority criterion. In some sense, the committee scoring rules in this class are multiwinner analogues of the single-winner Plurality rule, which is uniquely characterized as the only single-winner scoring rule that satisfies the simple majority criterion. We find that, for most of the rules in our new class, the complexity of winner determination is high (i. e. , the problem of computing the winners is NP-hard), but we also show some examples of polynomial-time winner determination procedures, exact and approximate.

IJCAI Conference 2016 Conference Paper

Voting-Based Group Formation

• Piotr Faliszewski
• Arkadii Slinko
• Nimrod Talmon

We study a combinatorial problem formulated in terms of the following group-formation scenario. Given some agents, where each agent has preferences over the set of potential group leaders, the task is to partition the agents into groups and assign a group leader to each of them, so that the group leaders have as high support as possible from the groups they are assigned to lead. We model this scenario as a voting problem, where the goal is to partition a set of voters into a prescribed number of groups so that each group elects its leader, i. e. , their leader is a unique winner in the corresponding election. We study the computational complexity of this problem (and several of its variants) for Approval elections.

AIJ Journal 2015 Journal Article

Achieving fully proportional representation: Approximability results

• Piotr Skowron
• Piotr Faliszewski
• Arkadii Slinko

We study the complexity of (approximate) winner determination under the Monroe and Chamberlin–Courant multiwinner voting rules, which determine the set of representatives by optimizing the total satisfaction or dissatisfaction of the voters with their representatives. The total (dis)satisfaction is calculated either as the sum of individual (dis)satisfactions in the utilitarian case or as the (dis)satisfaction of the worst off voter in the egalitarian case. We provide good approximation algorithms for the satisfaction-based utilitarian versions of the Monroe and Chamberlin–Courant rules, and inapproximability results for the dissatisfaction-based utilitarian versions of these rules and also for all egalitarian cases. Our algorithms are applicable and particularly appealing when voters submit truncated ballots. We provide experimental evaluation of the algorithms both on real-life preference-aggregation data and on synthetic preference data. These experiments show that our simple and fast algorithms can, in many cases, find near-perfect solutions.

IJCAI Conference 2015 Conference Paper

Generalizing the Single-Crossing Property on Lines and Trees to Intermediate Preferences on Median Graphs

• Adam Clearwater
• Clemens Puppe
• Arkadii Slinko

Demange (2012) generalized the classical singlecrossing property to the intermediate property on median graphs and proved that the representative voter theorem still holds for this more general framework. We complement her result with proving that the linear orders of any profile which is intermediate on a median graph form a Condorcet domain. We prove that for any median graph there exists a profile that is intermediate with respect to that graph and that one may need at least as many alternatives as vertices to construct such a profile. We provide a polynomial-time algorithm to recognize whether or not a given profile is intermediate with respect to some median graph. Finally, we show that finding winners for the Chamberlin- Courant rule is polynomial-time solvable for profiles that are single-crossing on a tree.

IJCAI Conference 2015 Conference Paper

Gibbard-Satterthwaite Games

• Edith Elkind
• Umberto Grandi
• Francesca Rossi
• Arkadii Slinko

The Gibbard-Satterthwaite theorem implies the ubiquity of manipulators–voters who could change the election outcome in their favor by unilaterally modifying their vote. In this paper, we ask what happens if a given profile admits several such voters. We model strategic interactions among Gibbard–Satterthwaite manipulators as a normal-form game. We classify the 2-by-2 games that can arise in this setting for two simple voting rules, namely Plurality and Borda, and study the complexity of determining whether a given manipulative vote weakly dominates truth-telling, as well as existence of Nash equilibria.

IJCAI Conference 2013 Conference Paper

Fully Proportional Representation as Resource Allocation: Approximability Results

• Piotr Skowron
• Piotr Faliszewski
• Arkadii Slinko

We study the complexity of (approximate) winner determination under Monroe’s and Chamberlin- Courant’s multiwinner voting rules, where we focus on the total (dis)satisfaction of the voters (the utilitarian case) or the (dis)satisfaction of the worstoff voter (the egalitarian case). We show good approximation algorithms for the satisfaction-based utilitarian cases, and inapproximability results for the remaining settings.

AAMAS Conference 2011 Conference Paper

Homogeneity and Monotonicity of Distance-Rationalizable Voting Rules

• Edith Elkind
• Piotr Faliszewski
• Arkadii Slinko

Distance rationalizability is a framework for classifying voting rules by interpreting them in terms of distances and consensus classes. It can also be used to design new voting rules with desired properties. A particularly natural and versatile class of distances that can be used for this purpose is that of votewise distances, which "lift" distances over individual votes to distances over entire elections using a suitable norm. In this paper, we continue the investigation of the properties of votewise distance-rationalizable rules initiated in Elkind et al. We describe a number of general conditions on distances and consensus classes that ensure that the resulting voting rule is homogeneous or monotone. This complements the results of Elkind et al. , where the authors focus on anonymity, neutrality and consistency. We also introduce a new class of voting rules, that can be viewed as "majority variants" of classic scoring rules, and have a natural interpretation in the context of distance rationalizability.

AAAI Conference 2010 Conference Paper

Cloning in Elections

• Edith Elkind
• Piotr Faliszewski
• Arkadii Slinko

We consider the problem of manipulating elections via cloning candidates. In our model, a manipulator can replace each candidate c by one or more clones, i. e. , new candidates that are so similar to c that each voter simply replaces c in his vote with the block of c’s clones. The outcome of the resulting election may then depend on how each voter orders the clones within the block. We formalize what it means for a cloning manipulation to be successful (which turns out to be a surprisingly delicate issue), and, for a number of prominent voting rules, characterize the preference profiles for which a successful cloning manipulation exists. We also consider the model where there is a cost associated with producing each clone, and study the complexity of finding a minimum-cost cloning manipulation. Finally, we compare cloning with the related problem of control via adding candidates.

AAAI Conference 2010 Conference Paper

Good Rationalizations of Voting Rules

• Edith Elkind
• Piotr Faliszewski
• Arkadii Slinko

We explore the relationship between two approaches to rationalizing voting rules: the maximum likelihood estimation (MLE) framework originally suggested by Condorcet and recently studied in (Conitzer and Sandholm 2005; Conitzer, Rognlie, and Xia 2009) and the distance rationalizability (DR) framework (Meskanen and Nurmi 2008; Elkind, Faliszewski, and Slinko 2009). The former views voting as an attempt to reconstruct the correct ordering of the candidates given noisy estimates (i. e. , votes), while the latter explains voting as search for the nearest consensus outcome. We provide conditions under which an MLE interpretation of a voting rule coincides with its DR interpretation, and classify a number of classic voting rules, such as Kemeny, Plurality, Borda and Single Transferable Vote (STV), according to how well they fit each of these frameworks. The classification we obtain is more precise than the ones that result from using MLE or DR alone: indeed, we show that the MLE approach can be used to guide our search for a more refined notion of distance rationalizability and vice versa.

AAMAS Conference 2010 Conference Paper

On the Role of Distances in Defining Voting Rules

• Edith Elkind
• Piotr Faliszewski
• Arkadii Slinko

A voting rule is an algorithm for determining the winner in an election, and there are several approaches that have been used to justify the proposed rules. One justification is to show that a rule satisfies a set of desirable axioms that uniquely identify it. Another is to show that the calculation that it performs is actually maximum likelihood estimation relative to a certain model of noise that affects voters (MLE approach). The third approach, which has been recently actively investigated, is the so-called {\em distance rationalizability} framework. In it, a voting rule is defined via a class of consensus elections (i. e. , a class of elections that have a clear winner) and a distance function. A candidate $c$ is a winner of an election $E$ if $c$ wins in one of the consensus elections that are closest to $E$ relative to the given distance. In this paper, we show that essentially any voting rule is distance-rationalizable if we do not restrict the two ingredients of the rule: the consensus class and the distance. Thus distance rationalizability of a rule does not by itself guarantee that the voting rule has any desirable properties. However, we demonstrate that the distance used to rationalize a given rule may provide useful information about this rule's behavior. Specifically, we identify a large class of distances, which we call {\em votewise} distances, and show that if a rule is rationalized via a distance from this class, many important properties of this rule can be easily expressed in terms of the underlying distance. This enables us to provide a new characterization of scoring rules and to establish a connection with the MLE framework. We alsogive bounds on the complexity of the winner determination problem for distance-rationalizable rules.