The Complexity of Proportionality Degree in Committee Elections

Over the last few years, researchers have put significant effort into understanding of the notion of proportional representation in committee election. In particular, recently they have proposed the notion of proportionality degree. We study the complexity of computing committees with a given propor...

Full description

Saved in:
Bibliographic Details
Main Authors: Janeczko, Łukasz, Faliszewski, Piotr
Format: Conference Proceeding
Language:English
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Over the last few years, researchers have put significant effort into understanding of the notion of proportional representation in committee election. In particular, recently they have proposed the notion of proportionality degree. We study the complexity of computing committees with a given proportionality degree and of testing if a given committee provides a particular one. This way, we complement recent studies that mostly focused on the notion of (extended) justified representation. We also study the problems of testing if a cohesive group of a given size exists and of counting such groups.
ISSN:2159-5399
2374-3468
DOI:10.1609/aaai.v36i5.20442