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

该项目将为三个基本问题领域奠定新的基础。匹配、市场和匹配市场这三个问题领域都有深刻而丰富的算法理论。这三种方法都有很多应用；例如，匹配市场的应用从为医院分配实习生，到为搜索引擎公司数十亿美元的在线广告市场中的广告商分配查询关键字，无所不包。研究者在过去的三个问题领域都做出了基础性的贡献，并为这个项目确定了几个新的问题。与此同时，这位最近搬到加州大学欧文分校（University of California, Irvine）的研究人员肩负着帮助推动其理论小组更上一层楼的任务。为此，他将招收一名博士后和高素质的研究生，以提高研究活动的水平和质量，并将帮助改进研究生和本科生的理论课程。在匹配方面，研究者最近提出了一种快速并行（NC）算法，用于在平面图中寻找完美匹配，解决了一个三十多年的开放问题，并确定了一些重要的后续问题。在他为几个市场模型提供互补支点均衡算法的工作之后，他计划分析该算法的平滑复杂性。研究者最近在稳定匹配问题上的工作，得到了关于两个“附近”实例稳定匹配格之间关系的新的结构结果。这将有助于开发有效的算法，以找到对输入中引入的错误具有鲁棒性的解决方案。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.