A preference profile is single-peaked on a tree if the candidate set can be equipped with a tree structure so that the preferences of each voter are decreasing from their top candidate along all paths in the tree. This notion was introduced by Demange (1982), and subsequently Trick (1989) described an efficient algorithm for deciding if a given profile is single-peaked on a tree. We study the complexity of multiwinner elections under several variants of the Chamberlin-Courant rule for preferences single-peaked on trees. We show that the egalitarian version of this problem admits a polynomial-time algorithm. For the utilitarian version, we prove that winner determination remains NP-hard, even for the Borda scoring function; however, a winning committee can be found in polynomial time if either the number of leaves or the number of internal vertices of the underlying tree is bounded by a constant. To benefit from these positive results, we need a procedure that can determine whether a given profile is single-peaked on a tree that has additional desirable properties (such as, e.g., a small number of leaves). To address this challenge, we develop a structural approach that enables us to compactly represent all trees with respect to which a given profile is single-peaked. We show how to use this representation to efficiently find the best tree for a given profile for use with our winner determination algorithms: Given a profile, we can efficiently find a tree with the minimum number of leaves, or a tree with the minimum number of internal vertices among trees on which the profile is single-peaked. We also consider several other optimization criteria for trees: for some we obtain polynomial-time algorithms, while for others we show NP-hardness results.

翻译：如果候选人组可以配备树状结构,让每个选民的偏好从树上的所有路径上从最高级候选人处下降,那么树上的偏好就会单加一个偏好。 Demange(1982年)引入了这个概念, Trick(1989年)随后描述了一种有效的算法,用于确定某个特定剖面是否在树上单加一个注。我们根据Capallin-Courant规则的若干变式研究多赢者选举的复杂性,以图在树上单加注。我们显示,这一问题的平等版本包含一个多树状,从而让每个选民的偏好在树上从树顶端下降。对于实用性版本来说,我们证明获胜者的身份仍然是最起码的,甚至对于博尔达的评分功能;然而,如果树的叶子数量或树底的内脊椎数量被一个常数捆绑在一起,那么在树上就会找到一个高效的图案。我们需要一个程序,在树上找到一个具有更多理想属性的树状(比如,比如,比如说,直观树底的树底的树状,让我们看到一个最起码的标定的树状,我们如何展示这个图状来显示这个图状。