This project will focus on the problem of allocating a limited number of shared resources among competing agents, which is a fundamental problem in operations research and economics. Such problems arise in many settings: scheduling in computer and communication networks, deciding where to locate public facilities, matching colleges to prospective students, assigning housing to graduate students, allocating organs to patients on a waiting-list, dividing an estate between siblings, sharing the cost of a public good, etc. The central aim of this project is to design effective resource allocation mechanisms that (i) have a strong theoretical justification; (ii) are easy to compute; and (iii) are simple to implement in practice. The project can be broadly classified in two parts: the first part deals with a notion of equilibrium based on minimizing maximum regret, and will explore its implications for mechanism design. Initial results of this approach to bargaining problems with incomplete information appear promising. The second part of the project deals with matching and allocation problems. Here, nonstandard criteria such as fairness and incentives are incorporated into some well-studied optimization models. The project will seek to characterize conditions under which it is possible to design mechanisms that are both fair and incentive-compatible for a number of natural models. One of the aims will be to promote a greater interaction between economists and optimization researchers by illustrating how the research questions, ideas, and tools in one discipline can inform and enrich the other. If successful, the results of the project will lead to a better understanding of important phenomena such as collusion and coalition formation in matching and allocation problems.
The methods developed in this project, and the algorithms derived from them have the potential to improve the performance of several real-life systems. For example, the work on matching and allocation problems is inspired by applications to "school choice" problems. The results of this research will provide insight into how resource allocation decisions interact with the (often conflicting) goals of incentive-compatibility and fairness. The educational goals of the proposed project include the introduction of the exciting recent developments in the area of mechanism design in the undergraduate and graduate curriculum. These courses will serve to expose the undergraduate and graduate students to the large variety of public-decision making problems for which optimization methods and tools are applicable.
