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

AF：小：匹配、市场和匹配市场的算法

• 批准号: 1815901
• 负责人: Vijay Vazirani
• 金额: $ 50万
• 依托单位: University of California-Irvine
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-06-01 至 2021-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1815901&HistoricalAwards=false
• 关键词: AF; Small; Algorithms; Matching; Markets

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.

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