Welfare and Profit Maximization with Procurement Costs

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).