کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
436027 | 689964 | 2015 | 15 صفحه PDF | دانلود رایگان |
We study the complexity of winner determination in single-crossing elections under two classic fully proportional representation rules—Chamberlin–Courant's rule and Monroe's rule. Winner determination for these rules is known to be NP-hard for unrestricted preferences. We show that for single-crossing preferences this problem admits a polynomial-time algorithm for Chamberlin–Courant's rule, but remains NP-hard for Monroe's rule. Our algorithm for Chamberlin–Courant's rule can be modified to work for elections with bounded single-crossing width. We then consider elections that are both single-peaked and single-crossing, and develop an efficient algorithm for the egalitarian variant of Monroe's rule for such elections. While Betzler et al. [3] have recently presented a polynomial-time algorithm for this rule under single-peaked preferences, our algorithm has considerably better worst-case running time than that of Betzler et al.
Journal: Theoretical Computer Science - Volume 569, 2 March 2015, Pages 43–57