Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userJustifying Groups in Multiwinner Approval Voting
88
0
0.0
(
0
)
Added by
Warut Suksompong
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Justified representation (JR) is a standard notion of representation in multiwinner approval voting. Not only does a JR committee always exist, but previous work has also shown through experiments that the JR condition can typically be fulfilled by groups of fewer than $k$ candidates. In this paper, we study such groups -- known as $n/k$-justifying groups -- both theoretically and empirically. First, we show that under the impartial culture model, $n/k$-justifying groups of size less than $k/2$ are likely to exist, which implies that the number of JR committees is usually large. We then present efficient approximation algorithms that compute a small $n/k$-justifying group for any given instance, and a polynomial-time exact algorithm when the instance admits a tree representation. In addition, we demonstrate that small $n/k$-justifying groups can often be useful for obtaining a gender-balanced JR committee even though the problem is NP-hard.
rate research
Read More
We consider synchronized iterative voting in the Approval Voting system. We give examples with a Condorcet winner where voters apply simple, sincere, consistent strategies but where cycles appear that can prevent the election of the Condorcet winner, or that can even lead to the election of a consensual loser, rejected in all circumstances by a majority of voters. We conduct numerical experiments to determine how rare such cycles are. It turns out that when voters apply Lasliers Leader Rule they are quite uncommon, and we prove that they cannot happen when voters preferences are modeled by a one-dimensional culture. However a slight variation of the Leader Rule accounting for possible draws in voters preferences witnesses much more bad cycle, especially in a one-dimensional culture.Then we introduce a continuous-space model in which we show that these cycles are stable under perturbation. Last, we consider models of voters behavior featuring a competition between strategic behavior and reluctance to vote for candidates that are ranked low in their preferences. We show that in some cases, this leads to chaotic behavior, with fractal attractors and positive entropy.
Given a set of agents with approval preferences over each other, we study the task of finding $k$ matchings fairly representing everyones preferences. We model the problem as an approval-based multiwinner election where the set of candidates consists of all possible matchings and agents preferences over each other are lifted to preferences over matchings. Due to the exponential number of candidates in such elections, standard algorithms for classical sequential voting rules (such as those proposed by Thiele and Phragmen) are rendered inefficient. We show that the computational tractability of these rules can be regained by exploiting the structure of the approval preferences. Moreover, we establish algorithmic results and axiomatic guarantees that go beyond those obtainable in the general multiwinner setting. Assuming that approvals are symmetric, we show that proportional approval voting (PAV), a well-established but computationally intractable voting rule, becomes polynomial-time computable, and its sequential variant (seq-PAV), which does not provide any proportionality guarantees in general, fulfills a rather strong guarantee known as extended justified representation. Some of our positive computational results extend to other types of compactly representable elections with an exponential candidate space.
We study sincere-strategy preference-based approval voting (SP-AV), a system proposed by Brams and Sanver [Electoral Studies, 25(2):287-305, 2006], and here adjusted so as to coerce admissibility of the votes (rather than excluding inadmissible votes a priori), with respect to procedural control. In such control scenarios, an external agent seeks to change the outcome of an election via actions such as adding/deleting/partitioning either candidates or voters. SP-AV combines the voters preference rankings with their approvals of candidates, where in elections with at least two candidates the voters approval strategies are adjusted--if needed--to approve of their most-preferred candidate and to disapprove of their least-preferred candidate. This rule coerces admissibility of the votes even in the presence of control actions, and hybridizes, in effect, approval with pluralitiy voting. We prove that this system is computationally resistant (i.e., the corresponding control problems are NP-hard) to 19 out of 22 types of constructive and destructive control. Thus, SP-AV has more resistances to control than is currently known for any other natural voting system with a polynomial-time winner problem. In particular, SP-AV is (after Copeland voting, see Faliszewski et al. [AAIM-2008, Springer LNCS 5034, pp. 165-176, 2008]) the second natural voting system with an easy winner-determination procedure that is known to have full resistance to constructive control, and unlike Copeland voting it in addition displays broad resistance to destructive control.
Shortlisting is the task of reducing a long list of alternatives to a (smaller) set of best or most suitable alternatives from which a final winner will be chosen. Shortlisting is often used in the nomination process of awards or in recommender systems to display featured objects. In this paper, we analyze shortlisting methods that are based on approval data, a common type of preferences. Furthermore, we assume that the size of the shortlist, i.e., the number of best or most suitable alternatives, is not fixed but determined by the shortlisting method. We axiomatically analyze established and new shortlisting methods and complement this analysis with an experimental evaluation based on biased voters and noisy quality estimates. Our results lead to recommendations which shortlisting methods to use, depending on the desired properties.
To choose a suitable multiwinner voting rule is a hard and ambiguous task. Depending on the context, it varies widely what constitutes the choice of an ``optimal subset of alternatives. In this paper, we provide a quantitative analysis of multiwinner voting rules using methods from the theory of approximation algorithms---we estimate how well multiwinner rules approximate two extreme objectives: a representation criterion defined via the Approval Chamberlin--Courant rule and a utilitarian criterion defined via Multiwinner Approval Voting. With both theoretical and experimental methods, we classify multiwinner rules in terms of their quantitative alignment with these two opposing objectives. Our results provide fundamental information about the nature of multiwinner rules and, in particular, about the necessary tradeoffs when choosing such a rule.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
