论文标题
通过选民行为中多种模式解释偏好
Explaining Preferences by Multiple Patterns in Voters' Behavior
论文作者
论文摘要
在某些偏好汇总方案中，选民的偏好是高度结构化的：例如，一组候选人可能具有一维结构（以便选民的偏好是单峰），或者由二进制决策树描述（以便选民的偏好是群体 - 分别为组成）。但是，有时单轴或决策树不足以捕捉选民的喜好。相反，有少数$ k $的轴或决策树，因此配置文件中的每个投票都与这些轴之一（分别为，树木）一致。在这项工作中，我们研究了决定选民偏好是否可以以这种方式解释的复杂性。对于$ k = 2 $，我们使用杨〜[2020]在单峰偏好的背景下开发的技术，以获得多个领域的多项式时间算法：价值限制的偏好，可分离的偏好和自然的群体偏好偏好的自然偏见，即，caterpillar-callar-Caltpillar群组组成的偏好。对于$ k \ ge 3 $，众所周知，这个问题对于单峰偏好很难；我们表明，对于限制价值和群体可分离的偏好也是这种情况。我们对$ k = 2 $的积极结果利用了相应域的禁止的次要特征；特别是，我们确定卡特彼勒群体分离的偏好的领域承认了禁忌的次要表征。
In some preference aggregation scenarios, voters' preferences are highly structured: e.g., the set of candidates may have one-dimensional structure (so that voters' preferences are single-peaked) or be described by a binary decision tree (so that voters' preferences are group-separable). However, sometimes a single axis or a decision tree is insufficient to capture the voters' preferences; rather, there is a small number $k$ of axes or decision trees such that each vote in the profile is consistent with one of these axes (resp., trees). In this work, we study the complexity of deciding whether voters' preferences can be explained in this manner. For $k=2$, we use the technique developed by Yang~[2020] in the context of single-peaked preferences to obtain a polynomial-time algorithm for several domains: value-restricted preferences, group-separable preferences, and a natural subdomain of group-separable preferences, namely, caterpillar group-separable preferences. For $k\ge 3$, the problem is known to be hard for single-peaked preferences; we show that this is also the case for value-restricted and group-separable preferences. Our positive results for $k=2$ make use of forbidden minor characterizations of the respective domains; in particular, we establish that the domain of caterpillar group-separable preferences admits a forbidden minor characterization.
