13 accepted papers
An index is a function that measures the extent to which an election has a particular feature. We seek indices that capture agreement, diversity, and polarization among voters in approval elections, normalized with respect to saturation. The latter means that if two elections differ by the fraction
We study the computational complexity of winner determination problems in approval-based committee elections under Thiele voting rules. These form a class of rules parameterized by a fixed weight vector that specifies how a voter
In the k-Kemeny problem, we are given an ordinal election, i.e., a collection of votes ranking the candidates from best to worst, and we seek the smallest number of swaps of adjacent candidates that ensure that the election has at most k different rankings. We study this problem for a number of stru
We study the complexity of candidate control in participatory budgeting elections. The goal of constructive candidate control is to ensure that a given candidate wins by either adding or deleting candidates from the election (in the destructive setting, the goal is to prevent a given candidate from
We develop a general, formal model of social choice in which voters have continuous preferences over a one-dimensional space. Our model is parameterized by different restrictions that we introduce regarding the way voter preferences change in time as well as the optimization criteria (that correspon…
In this paper, we experimentally compare major approval based multiwinner voting rules. To this end, we define a measure of similarity between two equal sized committees subject to a given election. Using synthetic elections coming from several distributions, we analyze how similar are the committee…
We consider the notions of agreement, diversity, and polarization in ordinal elections (that is, in elections where voters rank the candidates). While (computational) social choice offers good measures of agreement between the voters, such measures for the other two notions are lacking. We attempt t…
We extend the map-of-elections framework to the case of approval elections. While doing so, we study a number of statistical cultures, including some new ones, and we analyze their properties. We find that approval elections can be understood in terms of the average number of approvals in the votes,…
We present an almost optimal algorithm for the classic Chamberlin-Courant multiwinner voting rule (CC) on single-peaked preference profiles. Given n voters and m candidates, it runs in almost linear time in the input size improving the previous best O(nm^2) time algorithm. We also study multiwinner…
We study extensions of the Election Isomorphism problem, focused on the existence of isomorphic subelections. Specifically, we propose the Subelection Isomorphism and the Maximum Common Subelection problems and study their computational complexity and approximability. Using our problems in experimen…
We study a generalization of the standard approval-based model of participatory budgeting (PB), in which voters are providing approval ballots over a set of predefined projects and---in addition to a global budget limit---there are several groupings of the projects, each group with its own budget li…
Participatory budgeting systems allow city residents to jointly decide on projects they wish to fund using public money, by letting residents vote on such projects. While participatory budgeting is gaining popularity, existing aggregation methods do not take into account the natural possibility of p…
In approval-based multiwinner elections, we are given a set of voters, a set of candidates, and, for each voter, a set of candidates approved by the voter. The goal is to find a committee of size k that maximizes the total utility of the voters. In this paper, we study approximability of Thiele rule…