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

AF：小：现代匹配市场中出现的算法和博弈论问题

• 批准号: 1813135
• 负责人: Anna Karlin
• 金额: $ 39.95万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-10-01 至 2022-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1813135&HistoricalAwards=false
• 关键词: AF; SMALL; Algorithmic; Game; Theoretic

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.

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

项目成果

An improved approximation algorithm for TSP in the half integral case

• DOI: 10.1145/3357713.3384273
• 发表时间: 2019-08
• 期刊: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Anna R. Karlin;N. Klein;S. Gharan

Combinatorial Auctions with Interdependent Valuations: SOS to the Rescue

• DOI: 10.1145/3328526.3329759
• 发表时间: 2019-03
• 期刊: Proceedings of the 2019 ACM Conference on Economics and Computation
• 作者: Alon Eden;M. Feldman;A. Fiat;Kira Goldner;Anna R. Karlin

Energy Equilibria in Proof-of-Work Mining

工作量证明挖矿中的能量平衡

• 发表时间: 2019
• 期刊: ACM Conference on Economics and Computation
• 作者: Fiat, Amos;Karlin, Anna;Koutsoupias, Elias;Papadimitriou, Christos
• 通讯作者: Papadimitriou, Christos

Competition Alleviates Present Bias in Task Completion

竞争减轻了目前任务完成方面的偏差

• DOI: 10.1007/978-3-030-64946-3_19
• 发表时间: 2020
• 期刊: WINE 2020
• 作者: Saraf, Aditya;Karlin, Anna R.;Morgenstern, Jamie
• 通讯作者: Morgenstern, Jamie

A (slightly) improved approximation algorithm for metric TSP

• DOI: 10.1145/3406325.3451009
• 发表时间: 2020-07
• 期刊: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Anna R. Karlin;N. Klein;S. Gharan