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

AF：小：不确定性下的在线决策：先知和秘书

• 批准号: 2114269
• 负责人: Mohammad Hajiaghayi
• 金额: $ 50万
• 依托单位: University of Maryland, College Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-06-01 至 2025-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2114269&HistoricalAwards=false
• 关键词: AF; Small; Online; Decision; Making

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.

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

项目成果

Adaptive Massively Parallel Constant-Round Tree Contraction

自适应大规模并行常轮树收缩

• DOI: 10.4230/lipics.itcs.2022.83
• 发表时间: 2022-02
• 期刊: USA
• 作者: MohammadTaghi Hajiaghayi;Marina Knittel;Hamed Saleh;Hsin Hao Su
• 通讯作者: Hsin Hao Su

Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce

在真正的次二次时间中近似编辑距离：Quantum 和 MapReduce

• DOI: 10.1145/3456807
• 发表时间: 2021-05
• 期刊: Journal of the ACM
• 影响因子: 2.5
• 作者: Boroujeni, Mahdi;Ehsani, Soheil;Ghodsi, Mohammad;Hajiaghayi, Mohammadtaghi;Seddighin, Saeed
• 通讯作者: Seddighin, Saeed

Generalized Stochastic Matching

广义随机匹配

• DOI: 10.1609/aaai.v36i9.21239
• 发表时间: 2022-06
• 期刊: Proceedings of the AAAI Conference on Artificial Intelligence
• 作者: Farhadi, Alireza;Gilbert, Jacob;Hajiaghayi, MohammadTaghi
• 通讯作者: Hajiaghayi, MohammadTaghi

Fair allocation of indivisible goods: Beyond additive valuations

不可分割商品的公平分配：超越附加估值

• DOI: 10.1016/j.artint.2021.103633
• 发表时间: 2021-11-01
• 期刊: Artif. Intell.
• 作者: M. Ghodsi;M. Hajiaghayi;Masoud Seddighin;Saeed Seddighin;Hadi Yami
• 通讯作者: Hadi Yami

Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance

有界树编辑距离的 (n poly(k)) 时间算法

• DOI: 10.1109/focs54457.2022.00071
• 发表时间: 2022-10
• 期刊: FOCS
• 作者: Das, Debarati;Gilbert, Jacob;Hajiaghayi, MohammadTaghi;Kociumaka, Tomasz;Saha, Barna;Saleh, Hamed
• 通讯作者: Saleh, Hamed