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

合作研究：AF：中：现代组合优化：激励、不确定性和平滑分析

基本信息

批准号：
1954927
负责人：
Aviad Rubinstein
金额：
$ 59.79万
依托单位：
Stanford University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-07-01 至 2025-06-30
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1954927&HistoricalAwards=false
关键词：
Collaborative Research AF Medium Modern

项目摘要

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.

优化理论是计算机科学的一个核心方面，自诞生以来一直推动着理论基础的发展。经典范式认为决策者拥有所有可用的相关信息，算法主要根据生成的解决方案的质量和速度进行评估。然而，在现代应用中，决策者不再预先掌握所有相关信息，而是必须激励战略代理人披露这些信息，即使这些代理人对所产生的解决方案有自己的兴趣。也许他们必须学习该项目的首要主题是在这些现代约束下发展新颖的优化理论。更详细地说，该项目考虑了三个关键角度。例如，它考虑了多项目拍卖和通信复杂性之间的相互作用，旨在了解是否可以在不考虑激励的情况下设计任何有效的通信优化算法来适应代理的激励，而不会造成（太多）损失。其次，它回顾了性能。受基数约束的子模最大化的经典问题（众所周知，在最坏情况的输入上很难解决），并为此问题引入了一种新颖的平滑分析变体。最后，它提出了一种解决仍悬而未决的拟阵秘书问题的新方法。：最小生成树问题的概括，其中一次学习一个边，并且在看到其他边之前必须不可撤销地将其包含（或不包含）在生成树中。该奖项符合 NSF 的法定使命，并已被视为值得通过使用基金会的智力优点和更广泛的影响审查标准进行评估来支持。

项目成果

期刊论文数量（3）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

The randomized communication complexity of randomized auctions

随机拍卖的随机通信复杂性

DOI：
10.1145/3406325.3451111
发表时间：
2021-06
期刊：
STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
0
作者：
Rubinstein, Aviad;Zhao, Junyao
通讯作者：
Zhao, Junyao

Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics

达到最高点：最大化预期订单统计的子集选择