Improving prophet inequalities: going beyond worst case and impact of weaker benchmark
Improving prophet inequalities: going beyond worst case and impact of weaker benchmark
Date: November 3, 2025
Speaker:
ENSAE
Prophet inequalities is a standard stopping time question where a decision maker observes sequentially random variables and decides when to stop, in the hope of maximizing the value of the selected variable. There is an extensive literature on the subject, proving some "optimality" of different procedures in the worst-case scenario. We claim, and prove, that those results can be strikingly improved when considering non-pathological distributions. This is illustrated in two directions: by introducing a parameter that characterizes the complexity of an instance or by looking at some slightly weaker benchmarks that strongly impact the performances of the oracle that knows in advance all the realized values.
Vianney Perchet is a professor at the Centre de recherche en économie et statistique (CREST) at the ENSAE since october 2019. Mainly focusing on the interplay between machine learning and game theory, his research themes are at the intersection of mathematics, computer science, and economics. The spectrum of his interest ranges from pure theory (say, optimal rates of convergence of algorithms) to pure applications (modeling user behavior, optimisation of recommender systems, etc.) He is also part-time distinguished researcher in the Criteo AI Lab, in Paris, working on efficient exploration in recommender systems.
Date: October 20, 2025
Speaker:
University of Warwick
The talk introduces two new classes of ultra-sharp bounds in queueing systems. The first is specific to the G/G/1 queue, with possibly correlated inter-arrivals; the main result is an exact expression for the distribution of the delay in terms of a series, whose terms are subject to elementary integration. Remarkably, the first few terms are sufficient to render ultra-sharp bounds improving upon state-of-the-art bounds by orders of magnitude. The second new class of bounds is specific to a tandem queueing network with general (i.e., not necessarily Poisson) arrivals and light-tailed service times. Besides showing for the first time that the end-to-end delay distribution is subject to a polynomial-exponential structure, explicit bounds computed in some special cases are shown to improve upon state-of-the-art results by many orders of magnitude.
Florin Ciucu is a Professor in the CS Department at the University of Warwick. His research interests are in the stochastic analysis of communication networks and the non-asymptotic analysis of stochastic bandits. He co-chaired ACM Sigmetrics 2024 and served on the Technical Program Committees of several other top conferences; currently he is on the Editorial Boards of the Performance Evaluation Journal and IEEE Transactions on Networking. Florin is a recipient of the ACM Sigmetrics 2005 Best Student Paper Award and IFIP Performance 2014 Best Paper Award.
Date: September 29, 2025
Speaker:
Duke University
Motivated by mass emergencies such as pandemics and earthquakes that result in a large number of patients requiring critical services, we study a feature-based scheduling problem with N patients waiting to be served by a decision maker. The decision maker knows each patient's features and waiting cost, but does not know how the expected service time depends on the patient features. After a patient is served, the decision maker observes the realized service time and determines which patient to serve next. We prove that the decision maker's expected regret, i.e., the difference between the expected total waiting cost of the decision maker and that of a clairvoyant who knows the patients' expected service times, is at least of order N^{3/2}. We then design a learn-then-commit policy and an uncertainty ellipsoid policy to dynamically learn the expected service times, and prove that the expected regrets of these two policies are of order N^{5/3} log^{1/2} N and N^{3/2} log^{3/2} N, respectively. Finally, we conduct simulation experiments and a case study based on real-world data from Duke University Hospital to demonstrate the practical value of our policies relative to commonly used approaches. (Paper available at SSRN: https://ssrn.com/abstract=4852356)
Bora Keskin is an Associate Professor of Operations Management at Duke University’s Fuqua School of Business. His research focuses on data-driven decision making under uncertainty, with applications in dynamic pricing, revenue management, platform operations, and supply chain innovation. His recent work explores how emerging technologies—such as blockchain, IoT, and AI—are reshaping the future of operations. Bora received his Ph.D. from Stanford University. His work has been recognized with several awards, including the Lanchester Prize (2019) and the MSOM Young Scholar Prize (2024). Prior to joining Duke in 2015, he worked as a consultant at McKinsey & Company and served on the faculty of the University of Chicago Booth School of Business. At Fuqua, Bora teaches the MBA elective Value Chain Innovation in Business Processes, which emphasizes technological change and data-driven practices. He also teaches a Ph.D. course on revenue management and pricing. Outside Duke, he serves as an Associate Editor for Management Science and Operations Research, and as a Senior Editor for Production and Operations Management.