Committee scoring voting rules are multiwinner analogues of positional scoring rules which constitute an important subclass of single-winner voting rules. We identify several natural subclasses of committee scoring rules, namely, weakly separable, representation-focused, top- @math -counting, OWA-based, and decomposable rules. We characterize SNTV, Bloc, and @math -Approval Chamberlin--Courant as the only nontrivial rules in pairwise intersections of these classes. We provide some axiomatic characterizations for these classes, where monotonicity properties appear to be especially useful. The class of decomposable rules is new to the literature. We show that it strictly contains the class of OWA-based rules and describe some of the applications of decomposable rules.
Proportional Approval Voting (PAV) received a bit less attention than the Chamberlin--Courant rule, but due to the work of @cite_10 on justified representation, it is now being studied with increasing interest (briefly put, @. have shown that PAV is remarkably good at providing committees that represent the voters proportionally, as also confirmed by @cite_3 ; see the work of @cite_4 for another rule with similar properties). The rule was shown to be @math -hard to compute @cite_16 @cite_44 , but the standard greedy @math -approximation algorithm works for it. Very recently, @cite_34 have shown a different, apparently much more powerful algorithm. The rule was also considered in the context of restricted domains @cite_77 . FPT approximation schemes for PAV and other OWA-based rules were provided by Skowron @cite_69 .
@cite_69 @cite_4 @cite_3 @cite_34 @cite_44 @cite_77 @cite_16 @cite_10
2293358884 2606550175 2110060186 1575960470 2951884201 2172146192 2124837549 1972375916
Given a set of voters V, a set of candidates C, and voters' preferences over the candidates, multiwinner voting rules output a fixed-size subset of candidates committee. Under the Chamberlin---Courant multiwinner voting rule, one fixes a scoring vector of length |C|, and each voter's 'utility' for a given committee is defined to be the score that she assigns to her most preferred candidate in that committee; the goal is then to find a committee that maximizes the joint utility of all voters. The joint utility is typically identified either with the sum of all voters' utilities or with the utility of the least satisfied voter, resulting in, respectively, the utilitarian and the egalitarian variant of the Chamberlin---Courant's rule. For both of these cases, the problem of computing an optimal committee is NP-hard for general preferences, but becomes polynomial-time solvable if voters' preferences are single-peaked or single-crossing. In this paper, we propose a family of multiwinner voting rules that are based on the concept of ordered weighted average OWA and smoothly interpolate between the egalitarian and the utilitarian variants of the Chamberlin---Courant rule. We show that under moderate constraints on the weight vector we can recover many of the algorithmic results known for the egalitarian and the utilitarian version of Chamberlin---Courant's rule in this more general setting. We study a generic framework that provides a unified view on two important classes of problems: (i) extensions of the k-median problem where clients are interested in having multiple facilities in their vicinity (e.g., due to the fact that, with some small probability, the closest facility might be malfunctioning and so might not be available for using), and (ii) finding winners according to some appealing multiwinner election rules, i.e., election system aimed for choosing representatives bodies, such as parliaments, based on preferences of a population of voters over individual candidates. Each problem in our framework is associated with a vector of weights: we show that the approximability of the problem depends on structural properties of these vectors. We specifically focus on the harmonic sequence of weights for which the objective function interpreted in a multiwinner election setup reflects to the well-known Proportional Approval Voting (PAV) rule. Our main result is that, due to the specific (harmonic) structure of weights, the problem allows constant factor approximation. This is surprising since the problem can be interpreted as a variant of the k-median problem where we do not assume that the connection costs satisfy the triangle inequality. The algorithm we propose is based on dependent rounding [Srinivasan, FOCS'01] applied to the solution of a natural LP-relaxation of the problem. The rounding process is well known to produce distributions over integral solutions satisfying Negative Correlation (NC), which is usually sufficient for the analysis of approximation guarantees offered by rounding procedures. In our analysis, however, we need to use the fact that the carefully implemented rounding process satisfies a stronger property, called Negative Association (NA), which allows us to apply standard concentration bounds for conditional random variables. We study the complexity of winner determination in single-crossing elections under two classic fully proportional representation rules-Chamberlin-Courant's rule and Monroe's rule. Winner determination for these rules is known to be NP-hard for unrestricted preferences. We show that for single-crossing preferences this problem admits a polynomial-time algorithm for Chamberlin-Courant's rule, but remains NP-hard for Monroe's rule. Our algorithm for Chamberlin-Courant's rule can be modified to work for elections with bounded single-crossing width. We then consider elections that are both single-peaked and single-crossing, and develop an efficient algorithm for the egalitarian variant of Monroe's rule for such elections. While [3] have recently presented a polynomial-time algorithm for this rule under single-peaked preferences, our algorithm has considerably better worst-case running time than that of We study computational aspects of three prominent voting rules that use approval ballots to select multiple winners. These rules are proportional approval voting, reweighted approval voting, and satisfaction approval voting. Each rule is designed with the intention to compute a representative winning set. We show that computing the winner for proportional approval voting is NP-hard, closing an open problem (Kilgour, 2010). As none of the rules we examine are strategy-proof, we study various strategic aspects of the rules. In particular, we examine the computational complexity of computing a best response for both a single agent and a group of agents. In many settings, we show that it is NP-hard for an agent or agents to compute how best to vote given a fixed set of approval ballots of the other agents. We study computational aspects of three prominent voting rules that use approval ballots to elect multiple winners. These rules are satisfaction approval voting, proportional approval voting, and reweighted approval voting. We first show that computing the winner for proportional approval voting is NP-hard, closing a long standing open problem. As none of the rules are strategyproof, even for dichotomous preferences, we study various strategic aspects of the rules. In particular, we examine the computational complexity of computing a best response for both a single agent and a group of agents. In many settings, we show that it is NP-hard for an agent or agents to compute how best to vote given a fixed set of approval ballots from the other agents. This paper examines the system of Qualified Majority Voting, used by the Council of the European Union, from the perspective of enlargement of the Union. It uses an approach based on power indices due to Penrose (1946), Banzhaf (1965) and Coleman (1971) to make two analyses: (1) the question of the voting power of member countries from the point of view of fairness, and (2) the question of how the threshold number of votes required for QMV should be determined. It studies two scenarios for change from 2005 onwards envisaged by the Nice Treaty: (1) no enlargement, the EU comprising 15 member countries, and (2) full enlargement to 27 members by the accession of all the present twelve candidates. The proposal is made that fair weights be determined algorithmically as a technical or routine matter as the membership changes. The analysis of how the threshold affects power shows the trade-offs that countries face between their blocking power and the power of the Council to act. The main findings are: (1) that the weights laid down in the Nice Treaty are close to being fair, the only significant discrepancies being the under-representation of Germany and Romania, and the over-representation of Spain and Poland; (2) the threshold required for a decision is set too high for the Council to be an effective decision making body. We investigate two systems of fully proportional representation suggested by Chamberlin & Courant and Monroe. Both systems assign a representative to each voter so that the "sum of misrepresentations" is minimized. The winner determination problem for both systems is known to be NP-hard, hence this work aims at investigating whether there are variants of the proposed rules and or specific electorates for which these problems can be solved efficiently. As a variation of these rules, instead of minimizing the sum of misrepresentations, we considered minimizing the maximal misrepresentation introducing effectively two new rules. In the general case these "minimax" versions of classical rules appeared to be still NP-hard. We investigated the parameterized complexity of winner determination of the two classical and two new rules with respect to several parameters. Here we have a mixture of positive and negative results: e.g., we proved fixed-parameter tractability for the parameter the number of candidates but fixed-parameter intractability for the number of winners. For single-peaked electorates our results are overwhelmingly positive: we provide polynomial-time algorithms for most of the considered problems. The only rule that remains NP-hard for single-peaked electorates is the classical Monroe rule. In multiagent settings where the agents have different preferences, preference aggregation is a central issue. Voting is a general method for preference aggregation, but seminal results have shown that all general voting protocols are manipulable. One could try to avoid manipulation by using protocols where determining a beneficial manipulation is hard. Especially among computational agents, it is reasonable to measure this hardness by computational complexity. Some earlier work has been done in this area, but it was assumed that the number of voters and candidates is unbounded. Such hardness results lose relevance when the number of candidates is small, because manipulation algorithms that are exponential only in the number of candidates (and only slightly so) might be available. We give such an algorithm for an individual agent to manipulate the Single Transferable Vote (STV) protocol, which has been shown hard to manipulate in the above sense. This motivates the core of this article, which derives hardness results for realistic elections where the number of candidates is a small constant (but the number of voters can be large). The main manipulation question we study is that of coalitional manipulation by weighted voters. (We show that for simpler manipulation problems, manipulation cannot be hard with few candidates.) We study both constructive manipulation (making a given candidate win) and destructive manipulation (making a given candidate not win). We characterize the exact number of candidates for which manipulation becomes hard for the plurality, Borda, STV, Copeland, maximin, veto, plurality with runoff, regular cup, and randomized cup protocols. We also show that hardness of manipulation in this setting implies hardness of manipulation by an individual in unweighted settings when there is uncertainty about the others' votes (but not vice-versa). To our knowledge, these are the first results on the hardness of manipulation when there is uncertainty about the others' votes.