David John Abraham

Matching Markets: Design and Analysis Degree Type: Ph.D. in Computer Science
Advisor(s): R. Ravi
Graduated: December 2009

Abstract:

A market consists of buyers and sellers of some commodity, say a DVD movie. In this thesis, we assume the role of market operator. Our goal is to ensure that the market has certain desirable properties, including truthfulness, fairness and stability. We explore how to achieve these properties by designing rules for how the participants (buyers and sellers) can interact. We also explore how to efficiently compute the outcome of large numbers of participants interacting at once.

The main type of market we study is called a matching market. We study several particular matching markets, including keyword auction, kidney exchange and stable roommate mar- kets. In each of these cases, the aim is to match the participants to each other, somehow taking into account their preferences for one another. Our results focus on properties of the matching process and the design of efficient algorithms for finding various types of matchings. In particular, we present new polynomial time algorithms for finding matchings that have one of the following properties: popularity, rank-maximality and fairness. We also give an efficient algorithm for clearing large swap markets such as kidney exchanges. Finally, we present a new decomposition technique for designing keyword auctions.

Thesis Committee:
R. Ravi (Chair)
Alan Frieze
Luis von Ahn
David Manlove (University of Glasgow)

Peter Lee, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

Keywords:
Mechanism Design, Algorithms, Matching, Stable Marriage, Kidney Exchange