direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

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

Robert Bredereck (TU Berlin)


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.

This is joint work with Bernhard Bliem and Rolf Niedermeier


Robert Bredereck
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras