02/02/2021

Proportional Representation under Single-Crossing Preferences Revisited

Andrei Costin Constantinescu, Edith Elkind

Keywords:

Abstract Paper Similar Papers

Abstract: 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 tree. 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=Ω(log n) by reducing our problem to the k-link path problem for DAGs with concave Monge weights, obtaining a nm2^O(√(log k log log n)) 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.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38948928
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 20:37 
 0
 0
 0
 0
 14:19 
 0
 0
 0
 0
 12:31 
 0
 0
 0
 0
 14:22 
 0
 0
 0
 0
 16:11 
 0
 0
 0
 0
 5:12 
 0
 0
 0
 0
 22:30 
 0
 0
 0
 0
 3:24 
 0
 0
 0
 0
 5:16 
 0
 0
 0
 0
 9:37 
 0
 0
 0
 0
 3:23 
 0
 0
 0
 0
 12:43 
 0
 0
 0
 0
 29:37 
 0
 0
 0
 0
 25:10 
 0
 0
 0
 0
 24:50 
 0
 0
 0
 0
 14:50 
 0
 0
 0
 0
 14:16 
 0
 0
 0
 0
 24:22 
 0
 0
 0
 0
 19:35 
 0
 0
 0
 0
 15:53 
 0
 0
 0
 0
 23:23 
 0
 0
 0
 0
 13:14 
 0
 0
 0
 0
 25:12 
 0
 0
 0
 0
 9:36 
 0
 0
 0
 0
 3:03 
 0
 0
 0
 0
 18:58 
 0
 0
 0
 0
 16:52 
 0
 0
 0
 0
 13:48 
 0
 0
 0
 0
 18:07 
 0
 0
 0
 0
 3:25 
 0
 0
 0
 0
 22:50 
 0
 0
 0
 0
 15:28 
 0
 0
 0
 0
 5:16 
 0
 0
 0
 0
 7:26 
 0
 0
 0
 0
 5:40 
 0
 0
 0
 0
 14:53 
 0
 0
 0
 0
 23:51 
 0
 0
 0
 0
 9:02 
 0
 0
 0
 0
 23:42 
 0
 0
 0
 0
 3:23