Three New Complexity Results for Resource Allocation Problems

Details Three New Complexity Results for Resource Allocation Problems Three New Complexity Results for Resource Allocation Problems

2008-10-02

arxiv.org/abs/0810.0532v2

Computer Science

Multiagent Systems

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Three New Complexity Results for Resource Allocation Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Three New Complexity Results for Resource Allocation Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Three New Complexity Results for Resource Allocation Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-408956