---
title: "Complexity of Efficient and Envy-Free Resource Allocation: Few Agents, Resources, or Utility Levels"
authors:
  - "Bernhard Bliem"
  - "Robert Bredereck"
  - "Rolf Niedermeier"
doi: ""
url: "https://ijcai.org/proceedings/2016/22"
pdf: "https://ijcai.org/proceedings/2016/0022.pdf"
venue: "Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence"
year: 2016
pages: "102-107"
track: ""
keywords:
---

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

Bernhard Bliem, Robert Bredereck, Rolf Niedermeier

*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.