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