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

在线和基于匹配的市场设计领域始于1962年盖尔和沙普利关于稳定匹配的开创性论文。几十年来，它带来了非常成功的应用，产生了经济和社会影响，包括将实习生与医院配对，将学生与学校配对，将肾移植接受者与相容的捐赠者配对。这种跨学科工作的重要性和影响导致了2012年诺贝尔经济学奖被授予阿尔文·罗斯和劳埃德·沙普利。在过去的二十年里，互联网和移动计算的革命为研究和新颖、开创性的应用开辟了全新的途径。这些应用包括搜索引擎公司的广告拍卖市场，它将用户的查询与广告商相匹配；拼车、司机与乘客的匹配；雇主与员工的匹配市场；人与人之间的匹配平台；等等。这一领域的“第二次生命”甚至比第一次更加跨学科，计算机科学家和经济学家一起发挥着重要作用。研究人员在1990年的一篇联合论文中给出了在线二部匹配问题的最优算法，称为排名，它已经成为第二生命中设定范式的算法思想，就像第一次生命中的稳定匹配一样。最近开发的一种简单的排名证明开辟了新的机会，导致了当前项目下提出研究的四个问题中的三个：(I)获得在线超图匹配的算法及其推广--这些算法应用于网络收入管理和拼车；(Ii)将排名扩展到小出价下的AdWords问题，从而得到一个将在自动竞价平台中有用的与预算无关的算法；(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.