Complexity of Efficient and Envy-Free Resource Allocation: Few Agents, Resources, or Utility Levels

Bliem, Bernhard; Bredereck, Robert; Niedermeier, Rolf

Complexity of Efficient and Envy-Free Resource Allocation: Few Agents, Resources, or Utility Levels

Bernhard Bliem, Robert Bredereck, Rolf Niedermeier

Download BibTeX Cite

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 102-107.

Abstract

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.

Bernhard Bliem, Robert Bredereck, and Rolf Niedermeier. 2016. Complexity of Efficient and Envy-Free Resource Allocation: Few Agents, Resources, or Utility Levels. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16. IJCAI, 102–107. https://ijcai.org/proceedings/2016/22

@inproceedings{ijcai2016p22,
  title     = {Complexity of Efficient and Envy-Free Resource Allocation: Few Agents, Resources, or Utility Levels},
  author    = {Bliem, Bernhard and Bredereck, Robert and Niedermeier, Rolf},
  booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-16}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Subbarao Kambhampati},
  pages     = {102--107},
  year      = {2016},
  month     = {7},
  url       = {https://ijcai.org/proceedings/2016/22},
}

TY  - CPAPER
TI  - Complexity of Efficient and Envy-Free Resource Allocation: Few Agents, Resources, or Utility Levels
AU  - Bliem, Bernhard
AU  - Bredereck, Robert
AU  - Niedermeier, Rolf
T2  - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2016
SP  - 102
EP  - 107
UR  - https://ijcai.org/proceedings/2016/22
ER  -