Collaborative Research: AF: Medium: Modern Combinatorial Optimization: Incentives, Uncertainty, and Smoothed Analysis

优化理论是计算机科学的一个核心方面，从一开始就推动了理论基础的发展。经典范式认为决策者拥有所有可用的相关信息，算法主要根据产生的解决方案的质量和找到解决方案的速度进行评估。然而，在现代应用中，决策者不再事先掌握所有相关信息。也许他们必须激励战略代理来透露这些信息，即使这些代理在所产生的解决方案中有自己的利益。也许他们必须在网上零碎地学习相关信息，在只有部分信息的情况下做出不可撤销的决定。该项目的总体主题是在这些现代约束下发展新的优化理论。更详细地说，这个项目考虑了三个关键的角度。首先，它考虑了多物品拍卖之间的相互作用和通信复杂性。例如，它的目的是了解是否可以在没有考虑激励的情况下设计任何通信效率优化算法，以适应代理的激励而不（太多）损失性能。其次，它重新审视了受基数约束的次模最大化的经典问题（已知在最坏情况下输入是难以处理的），并引入了该问题的平滑分析的新变体。最后，提出了一种解决仍然开放的矩阵秘书问题的新方法：对最小生成树问题的推广，其中每次学习一条边，并且在看到其他边之前必须不可撤销地包含（或不包含）在生成树中。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Optimization theory is a central facet of computer science, and has driven the theoretical foundations since its inception. The classical paradigm considers a decision maker with all the relevant information available, and algorithms are evaluated primarily on the quality of the solution produced and the speed with which the solution is found. In modern applications, however, the decision maker no longer has all the relevant information in advance. Perhaps they must instead incentivize strategic agents to reveal this information, even when these agents have their own interests in the solution produced. Perhaps they must instead learn the relevant information in pieces online, making irrevocable decisions along the way with only partial information. The overarching theme of this project is the development of novel optimization theory subject to these modern constraints.In more detail, this project considers three key angles. First, it considers the interaction between multi-item auctions and communication complexity. For example, it aims to understand whether or not any communication-efficient optimization algorithm, designed without incentives in mind, can be made to also accommodate agents’ incentives without (much) loss in performance. Second, it revisits the classical problem of submodular maximization subject to a cardinality constraint (which is known to be intractable on worst case inputs), and introduces a novel variant of smoothed analysis for this problem. Finally, it proposes a new approach towards the still-open Matroid Secretary Problem: a generalization of the Minimum Spanning Tree problem where edges are learned one at a time and must be irrevocably included (or not) in the spanning tree before seeing other edges.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.