Ankit Sharma

Resource Allocation under Incentive, Information, and Complexity Constraints Degree Type: Ph.D. in Computer Science
Advisor(s): Avrim Blum, Anupam Gupta
Graduated: August 2014

Abstract:

This thesis studies the problem of resource allocation from multiple perspectives under a variety of constraints and objectives. Resource allocation is a central theme in many economic settings (markets, auctions etc.) and, more broadly, is prevalent in almost everything we do (for instance, everyday, we make decisions about allocating our money and time). The problem of resource allocation is usually driven by the fact that the resource under consideration is limited, and less than the number of claimants demanding it. And hence, we need to decide who to allocate the resource to and in what proportion. What makes resource allocation an extremely active area of research is that there is no single good allocation mechanism for the myriad constraints and objectives under which we encounter this problem. In this thesis, we make advances by designing new allocation mechanisms, studying the properties of existing ones, and understanding the complexity of how we value resources.

Specifically, our main contributions are: (a) we introduce a more general and realistic model of limitation of resources and under this limitation model, design allocation mechanisms that allocate resources to an online stream of self-interested buyers with combinatorial valuations through item pricing while approximately optimizing the objectives of social welfare and profit, (b) we design adaptive and non-adaptive allocation mechanisms for resource allocation under uncertain valuations, where the values can be determined only through expensive queries, (c) we analyze the performance of some of the popular auction formats in the presence of 'spiteful' bidders whose utility is negatively affected by other bidders' positive outcome, and (d) we understand the complexity of submodular valuation functions, a class of valuations characterized by decreasing marginal utilities, vis-á-vis some of its well-studied sub-classes such as budget additive, coverage and cut functions.

Thesis Committee:
Avrim Blum (Co-Chair)
Anupam Gupta (Co-Chair)
Ariel Procaccia
Jan Vondrák (IBM Almaden)

Frank Pfenning, Head, Computer Science Department
Andrew Moore, Dean, School of Computer Science

Keywords:
Resource allocation, Mechanism design, Approximation algorithms