论文标题
一棵树上单峰的偏好：多翼纳尔选举和结构性结果
Preferences Single-Peaked on a Tree: Multiwinner Elections and Structural Results
论文作者
论文摘要
如果候选人集可以配备树结构，则在树上单峰型配置文件，以便每个选民的偏好在树上的所有路径上都从其顶部候选人降低。该概念是由Demange（1982）引入的，随后Trick（1989）描述了一种有效的算法，以决定是否在树上单峰。我们研究了Chamberlin-Courant规则的几种变体中多翼纳选举的复杂性，以单峰在树上。我们表明，这个问题的平均值版本是多项式时间算法。对于功利主义版，我们证明赢家的决心仍然是NP-HARD，即使对于Borda评分功能也是如此。但是，如果叶子数量或基础树的内部顶点数量是由常数界定的，则可以在多项式时间内找到获胜委员会。为了使这些积极的结果受益，我们需要一个可以确定给定轮廓是否单峰的过程，该树在树上具有额外的理想特性（例如，例如少量叶子）。为了应对这一挑战，我们开发了一种结构性方法，使我们能够紧凑地代表所有树木，而给定的轮廓是单峰的。我们展示了如何使用此表示形式有效地找到适合给定配置文件的最佳树，以与我们的获奖者确定算法一起使用：给定的配置文件，我们可以有效地找到具有最小叶子数量的树，或者在树木中具有最小内部顶点的树，该树在该树木上，该树的轮廓为单张言论。我们还考虑了树木的其他几个优化标准：对于某些树木，我们获得了多项式时间算法，而对于其他人，我们显示了NP硬度结果。
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.
