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

Jiehua Chen, Christian Hatschka, Sofia Simola
7/31/2023
cs.MAcs.DScs.GT

No confident code implementation found for this paper.

Abstract

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].

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Stable Voting and the Splitting of Cycles

83% match1 repo2025

Optimal majority rules and quantitative Condorcet properties of setwise Kemeny voting schemes

82% match2023

Abductive and Contrastive Explanations for Scoring Rules in Voting

81% match2024

The Moderating Effect of Instant Runoff Voting

81% match2023

Space reduction techniques for the $3$-wise Kemeny problem

80% match2023

A General Theory of Proportionality with Additive Utilities

79% match2026

Cite this paper

@article{chen2023efficient,
  title  = {Efficient Algorithms for Monroe and CC Rules in Multi-Winner Elections with (Nearly) Structured Preferences},
  author = {Jiehua Chen and Christian Hatschka and Sofia Simola},
  year   = {2023},
  eprint = {2307.16864},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2307.16864v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2307.16864.svg)](https://codeofpaper.com/paper/2307.16864)

Discussion