Efficient Algorithms for Monroe and CC Rules in Multi-Winner Elections with (Nearly) Structured Preferences

07/31/2023
by   Jiehua Chen, et al.
0

We investigate winner determination for two popular proportional representation systems: the Monroe and Chamberlin-Courant (abbrv. CC) systems. Our study focuses on (nearly) single-peaked resp. single-crossing preferences. We show that for single-crossing approval preferences, winner determination of the Monroe rule is polynomial, and for both rules, winner determination mostly admits FPT algorithms with respect to the number of voters to delete to obtain single-peaked or single-crossing preferences. Our results answer some complexity questions from the literature [18, 28, 21].

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset