Computer Science Thesis Oral

Thesis Orals
Ph.D. Student
Computer Science Department
Carnegie Mellon University
Resource Allocation under Incentive, Information, and Complexity Constraints
Thursday, July 24, 2014 - 2:00pm to 4:00pm
Reddy Conference Room 4405 
Gates&Hillman Centers
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)

Keywords:
For More Information, Please Contact:

deb [atsymbol] cs.cmu.edu