AF: Small: Algorithms for Matching, Markets, and Matching-Markets

University Of California-Irvine, Irvine CA

Investigators

Abstract

This project will develop new foundations for three fundamental problem areas. All three problem areas, matching, markets, and matching markets have deep and rich algorithmic theories. All three have found numerous applications; for instance, applications of matching markets go all the way from assigning interns to hospitals, to assigning query keywords to advertisers in the multi-billion dollar online ads markets of search engine companies. The investigator has made foundational contributions to all three problem areas in the past, and has identified several new problems for this project. At the same time the investigator, who recently moved to the University of California, Irvine, has the mandate of helping propel its Theory Group to the next level. Towards this end, he will be recruiting a postdoc and high quality graduate students to increase the level and quality of research activity and will help revamp graduate and undergrad theory courses. On matching, the investigator recently solved a thirty-plus-year-old open problem by giving a fast parallel (NC) algorithm for finding a perfect matching in planar graphs, and has identified a number of important follow-up problems. Following up on his work giving complementary pivot equilibrium algorithms for several market models, he plans to analyze the smoothed complexity of this algorithm. Recent work of the investigator on the stable matching problem has yielded new structural results about relationships between the lattices of stable matchings of two "nearby" instances. This should help in developing efficient algorithms for finding solutions that are robust to errors introduced in the input. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.