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

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

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.