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.