AF: Small: Algorithm and Incentive Design for Modern Resource Allocation Platforms

过去十年见证了大规模在线平台和市场的快速发展，它们可以有效地分配资源，无论是云计算系统，还是在竞争任务之间分配CPU、磁盘和网络带宽；共享经济的在线市场，将乘车、住宿和技能等服务的卖家与这些服务的买家匹配起来；或者大型广告平台，将广告商与内容发布者相匹配。该项目将解决这些平台在算法和激励设计方面的关键挑战，特别是来自三个基本来源的挑战。首先是与平台互动的参与者的特征的不确定性，无论是云计算系统中的工作持续时间，还是买方和卖方的估值，以及在线市场中对这些的不对称知识。其次是参与者的动态特性，云系统中的工作，以及在线市场中的买家和卖家，都是动态到达和离开的。第三是资源配置问题的多维性，即工作或购买者同时从几种类型的资源中获得效用。该项目将开发整体算法方法来解决这些挑战，同时确保所得公式在计算上保持可处理性。由此产生的算法技术将为获得这些平台性能的实际改进提供指导原则。该项目有一个综合的教育和推广计划，通过有效的教学和指导，下一代学生将具备相关的算法技能。该项目的成果也将通过主要会议和期刊的出版物广泛传播；通过组织研讨会，将不同背景的研究人员聚集在一起；最后，通过开发课程材料和教程。在技术层面上，该项目正在开发超越最坏情况的方法，通过新颖的不确定性和动态随机模型，绕过最坏情况模型的计算难度和存在不可能性结果。该项目首先开发了基于多臂强盗框架的数据中心调度的新随机模型，其中具有多维资源需求的工作动态到达并且它们之间具有依赖关系。然后，该项目正在为共享经济应用产生的双边市场的战略方面开发一种算法理论。这涉及到开发贝叶斯模型，说明平台如何利用市场的不对称信息来影响卖家运行机制的结果。它还涉及开发技术，以解决买家和卖家匹配和定价的动态方面，当双方根据随机过程随时间到达和离开时。该项目从最优控制理论、贝叶斯拍卖和说服、动态定价和随机匹配等主题中借用建模工具并贡献工具。该项目的关键新颖之处在于在研究充分的和经典学科的交叉领域开发技术，例如在随机优化、学习理论和调度理论的交叉领域；或者最优控制，近似算法，和计算经济学。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

The last decade has witnessed the rapid development of large-scale online platforms and marketplaces for effective allocation of resources, whether it be cloud-computing systems for allocating CPU, disk, and network bandwidth among competing jobs; online marketplaces for the sharing economy that match sellers of services such as rides, lodging, and skills with buyers of these services; or large-scale advertising platforms that match advertisers with publishers of content. This project will address the key challenges in algorithm and incentive design for these platforms, in particular those arising from three fundamental sources. The first is uncertainty in the characteristics of the set of participants interacting with the platform, whether it be job durations in a cloud-computing system, or buyer and seller valuations and the asymmetric knowledge of these in an online marketplace. The second is the dynamic nature of the set of participants, where jobs in a cloud system, as well as buyers and sellers in an online marketplace, dynamically arrive and depart. The third is multi-dimensionality of the resource-allocation problems, where jobs or buyers derive utility from several types of resources simultaneously. This project will develop holistic algorithmic approaches to address these challenges, while ensuring the resulting formulations remain computationally tractable. The resulting algorithmic techniques will provide guiding principles for obtaining practical improvements in the performance of these platforms. The project has an integrated education and outreach plan, whereby the next generation of students will be equipped with the relevant algorithmic skills via effective teaching and mentorship. Results from the project will also be broadly disseminated via publications in major conferences and journals; via organizing workshops that bring together researchers with diverse backgrounds; and finally, via developing course materials and tutorials.At a more technical level, the project is developing approaches that go beyond the worst-case via novel stochastic models of uncertainty and dynamics that will circumvent the computational hardness and existential impossibility results in worst-case models. The project is first developing new stochastic models for scheduling in data centers based on the multi-armed bandit framework, where jobs with multidimensional resource requirements dynamically arrive and have dependencies between them. The project is then developing an algorithmic theory for the strategic aspects of two-sided marketplaces arising from sharing economy applications. This involves developing Bayesian models for how the platform can use asymmetric information about the marketplace to influence the outcome of mechanisms run by sellers. It also involves developing techniques to address the dynamic aspect of matching and pricing buyers and sellers, when both sides arrive and depart over time according to stochastic processes. The project is borrowing modeling tools from and contributing tools to the topics of optimal control theory, Bayesian auctions and persuasion, dynamic pricing, and stochastic matchings. The key novelty of the project is in developing techniques at the intersection of well-studied and classic disciplines, such as at the intersection of stochastic optimization, learning theory, and scheduling theory; or optimal control, approximation algorithms, and computational economics.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.