Complexity of Efficient and Envy-Free Resource Allocation: Few Agents, Resources, or Utility Levels
Complexity of Efficient and Envy-Free Resource Allocation: Few Agents, Resources, or Utility Levels
复制标题
高效且无嫉妒的资源分配的复杂性：很少的代理、资源或效用级别
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
R. Niedermeier
中科院分区：
文献类型：
--
作者：
B. Bliem;Robert Bredereck;R. Niedermeier
我们研究的问题，找到一个帕累托有效的和嫉妒免费分配的一组不可分割的资源与单调的偏好，二分法或添加剂的一组代理。受Bouveret和Lang [JAIR 2008]结果的启发，我们通过研究三个自然参数的影响提供了一个精确的计算复杂度分析：代理的数量n，资源的数量m，以及代理基于效用的偏好中出现的不同数字的数量z。在消极的一面，我们表明，在大多数情况下，单独的n和z的小值不会显着降低计算复杂性。在积极的一面，设计固定参数的算法，我们表明，所有考虑的问题是易于处理的情况下，小m。此外，我们开发了一个固定参数的算法，表明添加剂偏好的问题变得计算上容易处理的情况下，小n和小z。
We study the problem of finding a Pareto-efficient and envy-free allocation of a set of indivisible resources to a set of agents with monotonic preferences, either dichotomous or additive. Motivated by results of Bouveret and Lang [JAIR 2008], we provide a refined computational complexity analysis by studying the influence of three natural parameters: the number n of agents, the number m of resources, and the number z of different numbers occurring in utility-based preferences of the agents. On the negative side, we show that small values for n and z alone do not significantly lower the computational complexity in most cases. On the positive side, devising fixed-parameter algorithms we show that all considered problems are tractable in case of small m. Furthermore, we develop a fixed-parameter algorithm indicating that the problem with additive preferences becomes computationally tractable in case of small n and small z.
如何应用 SAT 求解单调范式的等价检验
DOI：
10.1007/978-3-642-21581-0_10
发表时间：
2011
期刊：
影响因子：
--
作者：
Martin Mundhenk;Robert Zeranski
通讯作者：
Robert Zeranski