Faliszewski, Piotr (AGH University) | Lackner, Martin ( TU Wien ) | Peters, Dominik (University of Oxford) | Talmon, Nimrod (Weizmann Institute of Science)

Committee scoring rules form an important class of multiwinner voting rules. As computing winning committees under such rules is generally intractable, in this paper we investigate efficient heuristics for this task. We design two novel heuristics for computing approximate results of multiwinner elections under arbitrary committee scoring rules; notably, one of these heuristics uses concepts from cooperative game theory. We then provide an experimental evaluation of our heuristics (and two others, known from the literature): we compare the scores of the committees output by our algorithms to the scores of the optimal committees, and also use the two-dimensional Euclidean domain to compare the visual representations of the outputs of our algorithms.

Bredereck, Robert (TU Berlin) | Faliszewski, Piotr (AGH University ) | Igarashi, Ayumi (University of Oxford) | Lackner, Martin (TU Wien ) | Skowron, Piotr (TU Berlin)

We develop a model of multiwinner elections that combines performance-based measures of the quality of the committee (such as, e.g., Borda scores of the committee members) with diversity constraints. Specifically, we assume that the candidates have certain attributes (such as being a male or a female, being junior or senior, etc.) and the goal is to elect a committee that, on the one hand, has as high a score regarding a given performance measure, but that, on the other hand, meets certain requirements (e.g., of the form "at least 30% of the committee members are junior candidates and at least 40% are females"). We analyze the computational complexity of computing winning committees in this model, obtaining polynomial-time algorithms (exact and approximate) and NP-hardness results. We focus on several natural classes of voting rules and diversity constraints.

Chen, Jiehua, Faliszewski, Piotr, Niedermeier, Rolf, Talmon, Nimrod

We study the computational complexity of candidate control in elections with few voters, that is, we consider the parameterized complexity of candidate control in elections with respect to the number of voters as a parameter. We consider both the standard scenario of adding and deleting candidates, where one asks whether a given candidate can become a winner (or, in the destructive case, can be precluded from winning) by adding or deleting few candidates, as well as a combinatorial scenario where adding/deleting a candidate automatically means adding or deleting a whole group of candidates. Considering several fundamental voting rules, our results show that the parameterized complexity of candidate control, with the number of voters as the parameter, is much more varied than in the setting with many voters.

Elkind, Edith (University of Oxford) | Faliszewski, Piotr (AGH Univesity of Science and Technology) | Laslier, Jean-Francois (Paris School of Economics) | Skowron, Piotr (University of Oxford) | Slinko, Arkadii (University of Auckland) | Talmon, Nimrod (Weizmann Institute of Science)

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.

Bredereck, Robert (Technische Universität Berlin) | Faliszewski, Piotr (AGH University of Science and Technology, Krakow) | Niedermeier, Rolf (Technische Universität Berlin) | Talmon, Nimrod (Technische Universität Berlin)

We study the (parameterized) complexity of Shift Bribery for multiwinner voting rules. We focus on the SNTV, Bloc, k-Borda, and Chamberlin-Courant rules, as well as on approximate variants of the Chamberlin-Courant rule, since the original rule is NP-hard to compute. We show that Shift Bribery tends to be significantly harder in the multiwinner setting than in the single-winner one by showing settings where Shift Bribery is easy in the single-winner cases, but is hard (and hard to approximate) in the multiwinner ones. We show that the non-monotonicity of those rules which are based on approximation algorithms for the Chamberlin--Courant rule sometimes affects the complexity of Shift Bribery.

Faliszewski, Piotr (AGH Univesity of Science and Technology) | Skowron, Piot (University of Oxford) | Slinko, Arkadii (University of Auckland) | Talmon, Nimrod (Technische Universitaet Berlin)

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.

Faliszewski, Piotr (AGH Univesity of Science and Technology) | Hemaspaandra, Edith (Rochester Institute of Technology) | Hemaspaandra, Lane A. (University of Rochester)

Many electoral control and manipulation problems — which we will refer to in general as manipulative actions problems — are NP-hard in the general case. Many of these problems fall into polynomial time if the electorate is single-peaked, i.e., is polarized along some axis/issue. However, real-world electorates are not truly single-peaked — for example, there may be some maverick voters — and to take this into account, we study the complexity of manipulative-action algorithms for the case of nearly single-peaked electorates.

Skowron, Piotr Krzysztof (University of Warsaw) | Faliszewski, Piotr (AGH University) | Lang, Jerome (Universite Paris-Dauphine)

We consider the following problem: There is a set of items (e.g., movies) and a group of agents (e.g., passengers on a plane); each agent has some intrinsic utility for each of the items. Our goal is to pick a set of K items that maximize the total derived utility of all the agents (i.e., in our example we are to pick K movies that we put on the plane's entertainment system). However, the actual utility that an agent derives from a given item is only a fraction of its intrinsic one, and this fraction depends on how the agent ranks the item among the chosen, available, ones. We provide a formal specification of the model and provide concrete examples and settings where it is applicable. We show that the problem is hard in general, but we show a number of tractability results for its natural special cases.

Chen, Jiehua (TU Berlin) | Faliszewski, Piotr (AGH University of Science and Technology) | Niedermeier, Rolf (TU Berlin) | Talmon, Nimrod (TU Berlin)

We study the computational complexity of candidate control in elections with few voters (that is, we take the number of voters as a parameter). We consider both the standard scenario of adding and deleting candidates, where one asks if a given candidate can become a winner (or, in the destructive case, can be precluded from winning) by adding/deleting some candidates, and a combinatorial scenario where adding/deleting a candidate automatically means adding/deleting a whole group of candidates. Our results show that the parameterized complexity of candidate control (with the number of voters as the parameter) is much more varied than in the setting with many voters.

Skowron, Piotr Krzysztof (University of Warsaw) | Faliszewski, Piotr (AGH University)

We consider the problem of winner determination under Chamberlin--Courant's multiwinner voting rule with approval utilities. This problem is equivalent to the well-known NP-complete MaxCover problem (i.e., a version of the SetCover problem where we aim to cover as many elements as possible) and, so, the best polynomial-time approximation algorithm for it has approximation ratio 1 - 1/e. We show exponential-time/FPT approximation algorithms that, on one hand, achieve arbitrarily good approximation ratios and, on the other hand, have running times much better than known exact algorithms. We focus on the cases where the voters have to approve of at most/at least a given number of candidates.