Three New Complexity Results for Resource Allocation Problems

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We prove the following results for task allocation of indivisible resources: - The problem of finding a leximin-maximal resource allocation is in P if the agents have max-utility functions and atomic demands. - Deciding whether a resource allocation is Pareto-optimal is coNP-complete for agents with (1-)additive utility functions. - Deciding whether there exists a Pareto-optimal and envy-free resource allocation is Sigma_2^p-complete for agents with (1-)additive utility functions.

Keywords

Multiagent Systems, Artificial Intelligence, Computational Complexity, Computer Science and Game Theory

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/171632

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0810.0532
 http://arxiv.org/abs/0810.0532

Collections

arXiv