AF: Small: Online Decision-Making under Uncertainty: Prophets and Secretaries

在算法的理论研究中，我们经常假设最坏情况分析。这通常意味着我们在将一个实例交给算法之前对它有完全的不确定性，这太悲观了。然而，在实践中，通常这种假设并不完全正确，并且来自不同应用领域的优化问题的实例通常具有重要的结构。在这个项目中，我们利用统计数据和分布信息的在线决策算法的输入放松悲观的看法。由于在电力市场、广告拍卖、动态机制设计、（强化）学习、投资程序、股票市场甚至联邦机构检查程序中的广泛应用，这种在线决策算法最近有相当大的发展势头。我们的算法将建立和开发新的通用框架，用于解决上述现实生活场景中的算法问题。该项目将涉及博士。学生和博士后，本科生，甚至高中生（特别是少数民族，女性，LGBT和残疾人的学生），其中许多人将继续在其他学术机构和研究中心进行研究，进一步扩大了该项目的影响。经典的在线设置要求我们在输入慢慢显示的过程中随着时间的推移做出决定，而不（完全）了解未来。在这个项目中，我们研究随机不确定性的输入需求，这被认为是非常现实的，并已在过去被广泛研究。在这个项目中感兴趣的在线设置是“先知”设置，“秘书”设置，“先知秘书”设置，以及“i.i.d.”。''对于他们每一个人来说，研究者都已经有了开创性的工作和深刻的贡献。在预言者设定中，需求来自事先已知的可能不同的分布，而在秘书设定中，需求以随机顺序出现。在先知秘书设置中，需求来自不同的分布（在不同的时间），这些分布是随机排列的，但事先知道。最后，在i.i.d.设置是所有先前设置的特殊情况，需求始终来自同一分布。 在这些设置中，我们考虑的基本问题，以及在机制设计，网络设计和运动规划中的应用。该项目的目标是将停止理论、在线算法、机器学习、机制设计和运筹学等领域的联合收割机工具结合起来，通过新技术解决该领域的重要研究挑战，并在这些领域之间建立更深层次的联系。我们将有特殊的考虑，为实际应用和简单的算法和基本原则，以现实世界的设置。我们还将把我们的发现融入到现有的和新的关于近似算法、机器学习基础和算法博弈论的课程中，并与统计学家和经济学家讨论进一步的融合。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

We often assume worst-case analysis in theoretical studies of algorithms. This often means we have complete uncertainty about an instance before it is handed to an algorithm, which is too pessimistic. In practice, however, often this assumption is not quite right and instances of optimization problems arising from different application domains often have significant structure. In this project we exploit statistical data and distribution information on inputs of online decision-making algorithms to relax the pessimistic view. Such online decision-making algorithms had considerable momentum lately due to profound applications in the electricity market, advertisement auctions, dynamic mechanism designs, (reinforcement) learning, investment procedures, stock market, and even federal agency inspection programs. Our algorithms will build on and develop new general frameworks for solving algorithmic problems in the above real-life scenarios. The project will involve Ph.D. students and postdocs, undergraduate students, and even high-school students (especially students among minorities, women, LGBT, and persons with disabilities), many of whom will continue their research at other academic institutions and research centers, further broadening the impact of this project.The classic online setting requires us to make decisions over time as the input is slowly revealed, without (complete) knowledge of the future. In this project we study stochastic uncertainty about input demands which are considered very realistic and has been widely studied in the past. Online settings of interest in this project are the ``prophet'' setting, the ``secretary'' setting, the ``prophet secretary'' setting, as well as the ``i.i.d.'' setting that for each of them, the investigator has already had pioneering work and deep contributions. In the prophet setting, demands are coming from possibly different distributions known in advance while in the secretary setting, demands are coming in a random order. In the prophet secretary setting, demands are coming from different distributions (at different times) which are randomly permuted but known in advance. Finally, in the i.i.d. setting, a special case of all previous settings, demands are coming from the same distribution all the time. In these settings, we consider fundamental problems as well as applications in mechanism design, network design, and motion planning. The goal of this project is to combine tools, from areas such as stopping theory, online algorithms, machine learning, mechanism design, and operations research to resolve important research challenges in the field via novel techniques and to forge deeper connections among these areas. We will have special considerations for practical applications and simplicity of our algorithms and underlying principles to real-world settings. We will also incorporate our discoveries into existing and new courses about approximation algorithms, foundations of machine learning, and algorithmic game theory, and discuss further incorporation with statisticians and economists.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.