What is the problem?
A limited resource needs to be allocated amongst a set of self-interested
agents. For instance, a company manager wants to allocate resources such as
labour force or technical infrastructure to various projects of the company.
How should the manager allocate the resources to maximize the output of the
company? The manager faces two issues that might hinder her in achieving the
objective. The first is that the resources are limited, hence she needs to
choose whom to allocate and whom not to. The second is that the manager is
not aware of the needs of various projects and each project team is
self-interested, i.e., each project team is interested only in furthering
its own project and might lie about the value of the project or the
resources they need.
I like the problem. So, what is your contribution?
Allocating limited resources in a game-theoretic setting has been considered
previously in research literature. The main contribution of our work is
that we model limitation of resources in a more realistic manner. Previous
literature has modeled the limited nature of a resource by assuming a fixed
number of copies of that resource. However, in several situations, it is not
the case that the number of copies of a resource are fixed. Rather,
additional copies of a resource might be procured but at a possibly high
cost. The limitation of the resource is therefore, due to the cost
associated in procuring additional copies. Yet, additional copies can be
procured.
Highlight of the results.
In a work with Avrim Blum, Anupam Gupta and Yishay Mansour, we initiate the
study of resource allocation in the more realistic modeling of limitation
where each resource has an increasing procurement cost. The resources need
to be allocated amongst agents to maximizes welfare. In this talk, we
describe a simple allocation scheme that achieves a constant factor
approximation to the optimal social welfare for polynomial and logarithmic
procurement cost curves. Furthermore, for arbitrary procurement cost curves,
we describe a scheme that achieves a logarithmic approximation to optimal
welfare.
The results are part of a work that appeared at Foundations of Computer
Science (FOCS), 2011 (joint work with Avrim Blum, Anupam Gupta and Yishay
Mansour).
