Multiwinner elections under preferences that are single-peaked on a tree

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 pathwidth. 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 λ.