TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 02.06.2016

isti-logo

Page Content

to Navigation

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

 

Date
Speaker
Location
Language
02.06.2016
16:15
Robert Bredereck
TEL 512
English

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe