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.

186 pages

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

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu