My PhD thesis is on algorithm and mechanism design for real-world matching markets.
Here is my thesis proposal.
The main markets I have looked at involve kidney exchanges, keyword auctions, and online DVD rental.
Kidney Exchanges: In these markets, patients with terminal kidney disease try to swap their incompatible donors with each other in order to get a compatible donor. My main contribution in this area is an algorithm for finding the best set of swaps.
This algorithm was recently selected by the UNOS for use in their upcoming nationwide kidney exchange, where it is expected to save thousands of lives and hundreds of millions of dollars a year in health care costs.
Keyword Auctions: Microsoft, Yahoo and Google use these auctions to sell the advertising space next to their search results. I came up with a new decomposition tool that leads to a simple technique for designing and analyzing keyword auction mechanisms. I used this tool to design a new mechanism that enables Microsoft to bid in its own auctions (e.g. when a user searches for xbox) without a conflict of interest. We have two patents pending on this work.
"Almost stable" matchings in the roomates problem, with Péter Biró and David F. Manlove.
In Proceedings of WAOA 2005: the 3rd Workshop on Approximation and Online Algorithms, volume 3879 of Lecture Notes in Computer Science, pages 1-14, Springer-Verlag, 2006.
Popular matchings, with Rob W. Irving, Kurt Mehlhorn and Kavitha Telikepalli.
In Proceedings of SODA 2005: the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 424-432, 2005.
In SIAM Journal on Computing vol. 37, pp. 1030-1045, 2007.
Pareto optimality in house allocation problems, with Katarína Cechlárová, David F. Manlove and Kurt Mehlhorn.
In Proceedings of ISAAC 2004: the 15th Annual International Symposium on Algorithms and Computation, volume 3341 of Lecture Notes in Computer Science, pages 3-15, Springer-Verlag, 2004.
The student-project allocation problem, with Rob W. Irving and David F. Manlove.
In Proceedings of ISAAC 2003: the 14th Annual International Symposium on Algorithms and Computation, volume 2906 of Lecture Notes in Computer Science, pages 474-484, Springer-Verlag, 2003.
XMLTutor: an Authoring Tool for Factual Domains, with Kalina Yacef.
In Proceedings of Workshop on Concepts and Ontologies in Web-based Educational Systems, held in conjunction with International Conference on Computers in Education (ICCE), CS-Report 02-15 Technische Universiteit Eindhoven, Auckland, New Zealand.
Adaptation in the Web-Based Logic-ITA, with Kalina Yacef.
In Proceedings of AH2002: the Second International Conference on Adaptive Hypermedia and Adaptive Web-Based Systems, volume 2347 of Lecture Notes in Computer Science, Springer-Verlag, 2002.
The Logic Tutor: A Multimedia Presentation, with Elisabeth Crawford, Leanna Lesta, Agathe Merceron and Kalina Yacef.
In Interactive Multimedia Electronic Journal on Computer Enhanced Learning, 3(2), 2001.
A tool to practice formal proofs, with Elisabeth Crawford, Leanna Lesta, Agathe Merceron and Kalina Yacef.
In the Proceedings EDMEDIA 2001: the World Conference on Educational Multimedia, Hypermedia and Telecommunications 2001(1), 7-8.
Layerable mechanisms for keyword auctions, with Arash Asadpour and Kamal Jain.
Online directed cycle cover, with R. Ravi and Viswanath Nagarajan.