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

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.