Thanh Nguyen
Center for Applied Mathematics & Cornell University
Abstract:
In resource allocation problems, a provider designs mechanisms to “sell” his resources to a set of users. These problems have many applications in Computer Science from network bandwidth sharing, job assignment in data centers to sponsor search. Simple mechanisms for resource allocation problems are important and practical because they are user-friendly and providers can predict more precisely the behavior of users. At the same time, a provider designs mechanisms to compete with others to maximize his revenue. How bad is the efficiency of such systems? In this paper we investigate the performance of simple weighted proportional sharing mechanisms. This is a different and richer approach for sponsor search problems. We also show that the efficiency loss is bounded by a constant independent of the number of users and providers in such systems.
This is a joint work with Milan Vojnovic.