Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPreferences Single-Peaked on a Tree: Multiwinner Elections and Structural Results
65
0
0.0
(
0
)
Added by
Dominik Peters
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A preference profile is single-peaked on a tree if the candidate set can be equipped with a tree structure so that the preferences of each voter are decreasing from their top candidate along all paths in the tree. This notion was introduced by Demange (1982), and subsequently Trick (1989) described an efficient algorithm for deciding if a given profile is single-peaked on a tree. We study the complexity of multiwinner elections under several variants of the Chamberlin-Courant rule for preferences single-peaked on trees. We show that the egalitarian version of this problem admits a polynomial-time algorithm. For the utilitarian version, we prove that winner determination remains NP-hard, even for the Borda scoring function; however, a winning committee can be found in polynomial time if either the number of leaves or the number of internal vertices of the underlying tree is bounded by a constant. To benefit from these positive results, we need a procedure that can determine whether a given profile is single-peaked on a tree that has additional desirable properties (such as, e.g., a small number of leaves). To address this challenge, we develop a structural approach that enables us to compactly represent all trees with respect to which a given profile is single-peaked. We show how to use this representation to efficiently find the best tree for a given profile for use with our winner determination algorithms: Given a profile, we can efficiently find a tree with the minimum number of leaves, or a tree with the minimum number of internal vertices among trees on which the profile is single-peaked. We also consider several other optimization criteria for trees: for some we obtain polynomial-time algorithms, while for others we show NP-hardness results.
rate research
Read More
We consider the algorithmic question of choosing a subset of candidates of a given size $k$ from a set of $m$ candidates, with knowledge of voters ordinal rankings over all candidates. We consider the well-known and classic scoring rule for achieving diverse representation: the Chamberlin-Courant (CC) or $1$-Borda rule, where the score of a committee is the average over the voters, of the rank of the best candidate in the committee for that voter; and its generalization to the average of the top $s$ best candidates, called the $s$-Borda rule. Our first result is an improved analysis of the natural and well-studied greedy heuristic. We show that greedy achieves a $left(1 - frac{2}{k+1}right)$-approximation to the maximization (or satisfaction) version of CC rule, and a $left(1 - frac{2s}{k+1}right)$-approximation to the $s$-Borda score. Our result improves on the best known approximation algorithm for this problem. We show that these bounds are almost tight. For the dissatisfaction (or minimization) version of the problem, we show that the score of $frac{m+1}{k+1}$ can be viewed as an optimal benchmark for the CC rule, as it is essentially the best achievable score of any polynomial-time algorithm even when the optimal score is a polynomial factor smaller (under standard computational complexity assumptions). We show that another well-studied algorithm for this problem, called the Banzhaf rule, attains this benchmark. We finally show that for the $s$-Borda rule, when the optimal value is small, these algorithms can be improved by a factor of $tilde Omega(sqrt{s})$ via LP rounding. Our upper and lower bounds are a significant improvement over previous results, and taken together, not only enable us to perform a finer comparison of greedy algorithms for these problems, but also provide analytic justification for using such algorithms in practice.
We study two notions of stability in multiwinner elections that are based on the Condorcet criterion. The first notion was introduced by Gehrlein: A committee is stable if each committee member is preferred to each non-member by a (possibly weak) majority of voters. The second notion is called local stability (introduced in this paper): A size-$k$ committee is locally stable in an election with $n$ voters if there is no candidate $c$ and no group of more than $frac{n}{k+1}$ voters such that each voter in this group prefers $c$ to each committee member. We argue that Gehrlein-stable committees are appropriate for shortlisting tasks, and that locally stable committees are better suited for applications that require proportional representation. The goal of this paper is to analyze these notions in detail, explore their compatibility with notions of proportionality, and investigate the computational complexity of related algorithmic tasks.
We study the complexity of determining a winning committee under the Chamberlin--Courant voting rule when voters preferences are single-crossing on a line, or, more generally, on a median graph (this class of graphs includes, e.g., trees and grids). For the line, Skowron et al. (2015) describe an $O(n^2mk)$ algorithm (where $n$, $m$, $k$ are the number of voters, the number of candidates and the committee size, respectively); we show that a simple tweak improves the time complexity to $O(nmk)$. We then improve this bound for $k=Omega(log n)$ by reducing our problem to the $k$-link path problem for DAGs with concave Monge weights, obtaining a $nm2^{Oleft(sqrt{log kloglog n}right)}$ algorithm for the general case and a nearly linear algorithm for the Borda misrepresentation function. For trees, we point out an issue with the algorithm proposed by Clearwater, Puppe and Slinko (2015), and develop a $O(nmk)$ algorithm for this case as well. For grids, we formulate a conjecture about the structure of optimal solutions, and describe a polynomial-time algorithm that finds a winning committee if this conjecture is true; we also explain how to convert this algorithm into a bicriterial approximation algorithm whose correctness does not depend on the conjecture.
Elections involving a very large voter population often lead to outcomes that surprise many. This is particularly important for the elections in which results affect the economy of a sizable population. A better prediction of the true outcome helps reduce the surprise and keeps the voters prepared. This paper starts from the basic observation that individuals in the underlying population build estimates of the distribution of preferences of the whole population based on their local neighborhoods. The outcome of the election leads to a surprise if these local estimates contradict the outcome of the election for some fixed voting rule. To get a quantitative understanding, we propose a simple mathematical model of the setting where the individuals in the population and their connections (through geographical proximity, social networks etc.) are described by a random graph with connection probabilities that are biased based on the preferences of the individuals. Each individual also has some estimate of the bias in their connections. We show that the election outcome leads to a surprise if the discrepancy between the estimated bias and the true bias in the local connections exceeds a certain threshold, and confirm the phenomenon that surprising outcomes are associated only with {em closely contested elections}. We compare standard voting rules based on their performance on surprise and show that they have different behavior for different parts of the population. It also hints at an impossibility that a single voting rule will be less surprising for {em all} parts of a population. Finally, we experiment with the UK-EU referendum (a.k.a. Brexit) dataset that attest some of our theoretical predictions.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
