ﻻ يوجد ملخص باللغة العربية
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.
The goal of multi-winner elections is to choose a fixed-size committee based on voters preferences. An important concern in this setting is representation: large groups of voters with cohesive preferences should be adequately represented by the elect
We investigate two systems of fully proportional representation suggested by Chamberlin Courant and Monroe. Both systems assign a representative to each voter so that the sum of misrepresentations is minimized. The winner determination problem for bo
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 Demang
In this paper, we consider how to fairly allocate $m$ indivisible chores to a set of $n$ (asymmetric) agents. As exact fairness cannot be guaranteed, motivated by the extensive study of EF1, EFX and PROP1 allocations, we propose and study {em proport
Participatory budgeting is a democratic process for allocating funds to projects based on the votes of members of the community. However, most input methods of voters preferences prevent the voters from expressing complex relationships among projects