Fully Proportional Representation as Resource Allocation: Approximability Results
Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 353-358.
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.
Piotr Krzysztof Skowron, Piotr Faliszewski, and Arkadii M. Slinko. 2013. Fully Proportional Representation as Resource Allocation: Approximability Results. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13. IJCAI, 353–358. https://ijcai.org/proceedings/2013/60
Skowron, P. K., Faliszewski, P., & Slinko, A. M. (2013). Fully Proportional Representation as Resource Allocation: Approximability Results. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13 (pp. 353–358). IJCAI. https://ijcai.org/proceedings/2013/60
@inproceedings{ijcai2013p60,
title = {Fully Proportional Representation as Resource Allocation: Approximability Results},
author = {Skowron, Piotr Krzysztof and Faliszewski, Piotr and Slinko, Arkadii M.},
booktitle = {Proceedings of the Twenty-Third International Joint Conference on
Artificial Intelligence, {IJCAI-13}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Francesca Rossi},
pages = {353--358},
year = {2013},
month = {8},
url = {https://ijcai.org/proceedings/2013/60},
}
TY - CPAPER TI - Fully Proportional Representation as Resource Allocation: Approximability Results AU - Skowron, Piotr Krzysztof AU - Faliszewski, Piotr AU - Slinko, Arkadii M. T2 - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2013 SP - 353 EP - 358 UR - https://ijcai.org/proceedings/2013/60 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
