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.''的设置，调查员已经为每个人提供了开创性的工作和深厚的贡献。在先知环境中，需求来自可能在秘书环境中提前已知的不同分布，需求按随机顺序出现。在先知秘书的环境中，需求来自不同的分布（在不同时间），这些分布是随机排列但事先知道的。最后，在I.I.D.设置是所有先前设置的特殊情况，要求一直来自相同的分布。在这些环境中，我们考虑了基本问题以及机理设计，网络设计和运动计划中的应用。该项目的目的是将工具组合起来，从停止理论，在线算法，机器学习，机制设计和操作研究等领域，通过新技术来解决该领域的重要研究挑战，并在这些领域之间建立更深入的联系。我们将对我们算法的实际应用和简单性以及对现实世界设置的基本原则进行特殊考虑。我们还将将我们的发现纳入有关近似算法，机器学习基础和算法游戏理论的现有和新课程中，并与统计学家和经济学家讨论了进一步的合并。该奖项反映了NSF的法定任务，并被认为是通过基金会的智力功能和广泛影响的评估来审查CRITERIA的评估。

项目成果

期刊论文数量（8）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Generalized Stochastic Matching

广义随机匹配

DOI：
10.1609/aaai.v36i9.21239
发表时间：
2022
期刊：
Proceedings of the AAAI Conference on Artificial Intelligence
影响因子：
0
作者：
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
期刊：
Artif. Intell.
影响因子：
0
作者：
M. Ghodsi;M. Hajiaghayi;Masoud Seddighin;Saeed Seddighin;Hadi Yami
通讯作者：
M. Ghodsi;M. Hajiaghayi;Masoud Seddighin;Saeed Seddighin;Hadi Yami

Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce

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

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

Fair Allocation of Indivisible Goods: Improvement