Welfare and Profit Maximization with Production Costs
Oct 19, 2011
ABSTRACT:
Imagine a scenario where a limited resource has 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. The allocation should be such that it maximizes the output of the company. Since the manager is not aware of the needs of various projects, she requests each project team to submit their requirements. The manager faces two issues that might hinder her in achieving the objective. The first is that the resources are limited, hence she may not be able to satisfy the needs of all the projects. The second is that each project team is interested in furthering only its own project, and so each team might make a case for being allocated all the resources. How can the manager allocate the resources to maximize the welfare of the company?
While previous literature has modeled the limited nature of a resource by assuming a fixed number of copies of that resource, in several situations, the limitation of the resource arises not because of a fixed number of copies but due to the cost associated in procuring additional copies. In other words, additional copies of a resource might be procured but at a possibly high marginal cost. In a work with Avrim Blum, Anupam Gupta and Yishay Mansour, we initiate the study of resource allocation in the more realistic scenario where each resource has an increasing production cost and the resources need to be allocated such that they maximize social welfare. In this talk, I describe how a simple allocation scheme over the resources achieves a constant approximation to the optimal social welfare for nice production curves such as polynomial and logarithmic. Furthermore, for general increasing production curves, I describe a scheme that achieves a logarithmic approximation to optimal welfare. The results are part of a work which is to appear at Foundations of Computer Science (FOCS) 2011.
Joint work with Avrim Blum, Anupam Gupta and Yishay Mansour.
While previous literature has modeled the limited nature of a resource by assuming a fixed number of copies of that resource, in several situations, the limitation of the resource arises not because of a fixed number of copies but due to the cost associated in procuring additional copies. In other words, additional copies of a resource might be procured but at a possibly high marginal cost. In a work with Avrim Blum, Anupam Gupta and Yishay Mansour, we initiate the study of resource allocation in the more realistic scenario where each resource has an increasing production cost and the resources need to be allocated such that they maximize social welfare. In this talk, I describe how a simple allocation scheme over the resources achieves a constant approximation to the optimal social welfare for nice production curves such as polynomial and logarithmic. Furthermore, for general increasing production curves, I describe a scheme that achieves a logarithmic approximation to optimal welfare. The results are part of a work which is to appear at Foundations of Computer Science (FOCS) 2011.
Joint work with Avrim Blum, Anupam Gupta and Yishay Mansour.