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

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

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.