4 papers
Algorithms for Candidate Control in Greedy Participatory Budgeting Rules
Šimon Schierreich, Krzysztof Sornat
We study the problem of candidate control in participatory budgeting elections. Our focus is on two prominent sequential welfare-based rules---GreedyAV and GreedyCost---which are w…
Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences
Pasin Manurangsi, Krzysztof Sornat
We present a polynomial-time algorithm for computing an optimal committee of size under any given Thiele voting rule for elections on the Voter Interval domain (i.e., when vote…
Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules
Krzysztof Sornat, Virginia Vassilevska Williams, Yinzhan Xu
We present an almost optimal algorithm for the classic Chamberlin-Courant multiwinner voting rule (CC) on single-peaked preference profiles. Given voters and candidates, it…
Fine-Grained Complexity and Algorithms for the Schulze Voting Method
Krzysztof Sornat, Virginia Vassilevska Williams, Yinzhan Xu
We study computational aspects of a well-known single-winner voting rule called the Schulze method [Schulze, 2003] which is used broadly in practice. In this method the voters give…