ML Anthology

Fully Proportional Representation as Resource Allocation: Approximability Results

Piotr Krzysztof Skowron, Piotr Faliszewski, Arkadii M. Slinko
IJCAI 2013 pp. 353-359
/ijcai/2013/skowron2013ijcai-fully/

Abstract

We study the complexity of (approximate) winner determination under Monroe's and Chamberlin-Courant's multiwinner voting rules, where we focus on the total (dis)satisfaction of the voters (the utilitarian case) or the (dis)satisfaction of the worst-off voter (the egalitarian case). We show good approximation algorithms for the satisfaction-based utilitarian cases, and inapproximability results for the remaining settings.

PDF IJCAI Semantic Scholar

Cite

Text

Skowron et al. "Fully Proportional Representation as Resource Allocation: Approximability Results." International Joint Conference on Artificial Intelligence, 2013.

Markdown

[Skowron et al. "Fully Proportional Representation as Resource Allocation: Approximability Results." International Joint Conference on Artificial Intelligence, 2013.](https://mlanthology.org/ijcai/2013/skowron2013ijcai-fully/)

BibTeX

@inproceedings{skowron2013ijcai-fully,
  title     = {{Fully Proportional Representation as Resource Allocation: Approximability Results}},
  author    = {Skowron, Piotr Krzysztof and Faliszewski, Piotr and Slinko, Arkadii M.},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2013},
  pages     = {353-359},
  url       = {https://mlanthology.org/ijcai/2013/skowron2013ijcai-fully/}
}