论文标题
在多个偏好下进行分配的参数化分析
Parameterized Analysis of Assignment Under Multiple Preferences
论文作者
论文摘要
任务问题是社会选择，计算经济学和离散分配的交集中的一个基本且研究的问题。在分配问题中，一组代理表达了比一组项目的偏好，而任务是找到对代理的帕累托最佳分配。我们介绍了此问题的广义版本，其中每个代理都配备了多个不完整的首选项列表：每个列表（称为一层）都是根据不同标准以可能不同方式的项目排名。我们介绍了全球最优性的概念，该概念将帕累托最优性的概念扩展到了多层设置，我们将重点放在决定是否存在全球最佳分配的问题上。我们从参数化复杂性的角度研究了这个问题：我们考虑了几个自然参数，例如层的数量，代理数量，项目数量以及偏好列表的最大长度。我们介绍了有关这些参数的参数化复杂性的全面图片。
The Assignment problem is a fundamental and well-studied problem in the intersection of Social Choice, Computational Economics and Discrete Allocation. In the Assignment problem, a group of agents expresses preferences over a set of items, and the task is to find a pareto optimal allocation of items to agents. We introduce a generalized version of this problem, where each agent is equipped with multiple incomplete preference lists: each list (called a layer) is a ranking of items in a possibly different way according to a different criterion. We introduce the concept of global optimality, which extends the notion of pareto optimality to the multi-layered setting, and we focus on the problem of deciding whether a globally optimal assignment exists. We study this problem from the perspective of Parameterized Complexity: we consider several natural parameters such as the number of layers, the number of agents, the number of items, and the maximum length of a preference list. We present a comprehensive picture of the parameterized complexity of the problem with respect to these parameters.
