AF: SMALL : Algorithmic and Game Theoretic Problems Arising in Modern Matching Markets

现代配对市场包括医疗保健市场、能源市场、在线市场、与共享/零工经济相关的市场、学校/大学与学生配对市场、云计算市场、在线广告市场等。该项目将包括设计和分析新的定价机制和匹配算法，目标是大幅提高此类市场的效力和效率。将开发大量在线资源，以展示计算研究协会妇女在计算领域的地位委员会多年来在其面对面研讨会上为不同劳动力提供的培训、建议和见解。这些资源将解决网络、沟通技能、在学术界和行业之间的选择、领导技能、谈判等问题。开发这些在线资源将确保这种指导将接触到更多的学生，特别是代表不足的群体的成员，从而增加他们在所有级别的计算研究和教育中的成功和参与。最大权重匹配是组合优化中的一个基石问题。它是一个展示算法瑰宝和美丽算法技术的窗口，最重要的是，它具有巨大的实际重要性，每天都有新的应用程序和重要的变体涌现。该项目的主要目标是解决由现代配对市场推动的算法和博弈论问题。在这些环境中出现的匹配问题需要处理战略代理，设计新的机制，做出定价决策，决定向参与代理传播什么和多少信息，解决在线问题，以及分析复杂的动态和排队。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Modern matching markets include healthcare markets, energy markets, online marketplaces, markets associated with the sharing/gig economy, markets for matching schools/universities with students, cloud computing markets, online advertising markets, etc. This project will consist of designing and analyzing new pricing mechanisms and matching algorithms with the objective of greatly increasing the effectiveness and efficiency of such marketplaces. Significant online resources will be developed to showcase training advice and insight for a diverse workforce that the Computing Research Association's Committee on the Status of Women in Computing has been providing for several years in its in-person workshops. These resources will address issues such as networking, communication skills, choosing between academia and industry, leadership skills, negotiating, etc. Developing these online resources will ensure that this mentoring will reach more students and especially members of underrepresented groups, thereby increasing their success and participation in computing research and education at all levels.Maximum weight matching is a cornerstone problem in combinatorial optimization. It is a showcase for algorithmic gems and beautiful algorithmic techniques, and, most importantly, is of immense practical importance, with new applications and important variants arising every day. The primary objective of the project is to solve algorithmic and game-theoretic problems motivated by modern matching markets. The matching problems that arise in these settings require handling strategic agents, designing new mechanisms, making pricing decisions, deciding what and how much information to disseminate to the participating agents, solving online problems, and analyzing complex dynamics and queueing.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.