AF: Small: Algorithmic Problems in Online and Matching-Based Market Design

AF：小：在线和基于匹配的市场设计中的算法问题

基本信息

批准号：
2230414
负责人：
Vijay Vazirani
金额：
$ 60万
依托单位：
University of California-Irvine
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2022
资助国家：
美国
起止时间：
2022-10-01 至 2025-09-30
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2230414&HistoricalAwards=false
关键词：
AF Small Algorithmic Problems Online

项目摘要

The area of online and matching-based market design started with the seminal 1962 paper of Gale and Shapley on stable matching. Over the decades, it led to highly successful applications, having economic as well as sociological impact, including matching medical interns to hospitals, matching students to schools, and matching kidney transplant recipients with compatible donors. The importance and impact of this interdisciplinary work led to the award of the 2012 Nobel Prize in Economics to Alvin Roth and Lloyd Shapley. Over the last two decades, the revolutions of the Internet and mobile computing opened up altogether new avenues of research and novel, path-breaking applications. These applications include the ad auction marketplace of search engine companies, which matches user queries to advertisers; ride-sharing, matching drivers to riders; markets matching employers to workers; platforms matching people to each other; and others. This "second life" of the field has been even more interdisciplinary than the first, with computer scientists playing a major role along with the economists. The optimal algorithm for the online bipartite matching problem, called RANKING, given in a 1990 joint paper of the investigator, has become the paradigm-setting algorithmic idea in the second life, much as stable matching was in the first. A recently developed simple proof of RANKING has opened up new opportunities, leading to three of the four problems proposed for study under the current project: (i) obtaining algorithms for online hypergraph matching and its generalizations -- these have applications to network revenue management and ride-sharing; (ii) extending RANKING to the adwords problem under small bids, so as to get a budget-oblivious algorithm which will be useful in autobidding platforms; (iii) obtaining high probability statements for online algorithms, which have thus far been analyzed in expectation only. The fourth problem addresses the paucity of general mechanisms for matching markets under cardinal utility functions; this paucity became apparent via recent work of the investigator, which led to proof of intractability of the classic Hylland-Zeckhauser mechanism (1979). The investigator has proposed Nash-bargaining-based mechanisms as a replacement and wishes to develop efficient implementations for them.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.

基于在线和匹配的市场设计领域始于 Gale 和 Shapley 1962 年关于稳定匹配的开创性论文。几十年来，它带来了非常成功的应用，产生了经济和社会影响，包括将医学实习生与医院相匹配，将学生与学校相匹配，以及将肾移植受者与相容的捐赠者相匹配。这项跨学科工作的重要性和影响力使得阿尔文·罗斯 (Alvin Roth) 和劳埃德·沙普利 (Lloyd Shapley) 荣获 2012 年诺贝尔经济学奖。在过去的二十年中，互联网和移动计算的革命开辟了全新的研究途径和新颖的、开创性的应用。这些应用程序包括搜索引擎公司的广告拍卖市场，它将用户查询与广告商相匹配；拼车，将司机与乘客匹配；将雇主与工人相匹配的市场；相互匹配人员的平台；和其他人。该领域的“第二次生命”比第一次更加跨学科，计算机科学家与经济学家一起发挥着重要作用。在线二分匹配问题的最优算法称为 RANKING，在研究者 1990 年的联合论文中给出，已成为第二次生命中的范式设定算法思想，就像第一次中的稳定匹配一样。最近开发的简单的 RANKING 证明开辟了新的机会，导致了当前项目提出的四个研究问题中的三个：（i）获得在线超图匹配算法及其泛化——这些可应用于网络收入管理和拼车； (ii)将RANKING扩展到小出价下的adwords问题，从而得到一种在自动出价平台中有用的预算忽略算法； (iii) 获得在线算法的高概率陈述，迄今为止仅在预期中进行分析。第四个问题解决了基数效用函数下缺乏匹配市场的通用机制；通过研究者最近的工作，这种缺乏变得明显，这证明了经典的 Hylland-Zeckhauser 机制（1979）的难处理性。研究人员提出了基于纳什讨价还价的机制作为替代方案，并希望为其开发有效的实施方案。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力优点和更广泛的影响审查标准进行评估，被认为值得支持。