## Speaker:

## Time:

## Venue:

- AG-80

## Organisers:

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