In this dissertation, we study several aspects of matching-based market design, i.e. the problem of designing mechanisms that can match agents to goods (or to other agents) while satisfying certain desirable properties such as fairness or efficiency. Common applications include matching students to schools, doctors to hospitals, riders to drivers, search queries to online advertisements, etc.

Part I deals with cardinal-utility matching markets where agents report non-negative utilities for the goods they are interested in. The Hylland Zeckhauser mechanism satisfies many of the desirable properties that we are interested in, however it has been shown to be PPAD-complete. We design alternative, polynomial time mechanisms for several settings. In particular, this dissertation provides substantial support for Nash-bargaining-based mechanisms as a computationally tractable alternative to HZ.

Part II deals with online matching where some of the agents or goods arive online and must be matched immediately and irrevocably. We provide a novel analysis of the classic Ranking algorithm which shows that it achieves its competitive ratio of 1 − 1/? with high probability as opposed to just in expectation. In addition, we introduce the study of online matching on hypergraphs where we give asymptotically almost tight upper and lower bounds.