Multiwinner Elections Under Preferences That Are Single-Peaked on a Tree
Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 425-430.
Abstract
We study the complexity of electing a committee under several variants of the Chamberlin–Courant rule when the voters' preferences are single-peaked on a tree. We first show that this problem is easy for the egalitarian, or minimax version of this problem, for arbitrary trees and misrepresentation functions. For the standard (utilitarian) version of this problem we provide an algorithm for an arbitrary misrepresentation function whose running time is polynomial in the input size as long as the number of leaves of the underlying tree is bounded by a constant. On the other hand, we prove that our problem remains computationally hard on trees that have bounded degree, diameter or path width. Finally, we show how to modify Trick's [1989] algorithm to check whether an election is single-peaked on a tree whose number of leaves does not exceed a given parameter.
@inproceedings{ijcai2013p70,
title = {Multiwinner Elections Under Preferences That Are Single-Peaked on a Tree},
author = {Yu, Lan and Chan, Hau and Elkind, Edith},
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 = {425--430},
year = {2013},
month = {8},
url = {https://ijcai.org/proceedings/2013/70},
}
TY - CPAPER TI - Multiwinner Elections Under Preferences That Are Single-Peaked on a Tree AU - Yu, Lan AU - Chan, Hau AU - Elkind, Edith 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 - 425 EP - 430 UR - https://ijcai.org/proceedings/2013/70 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
