Spring 2023

Abstract

Matching decisions are important operational controls for online marketplaces, with applications including order fulfillment, ride-hailing, and service platforms. Existing stochastic models often rely on an assumption of "serial independence," which implies that demand is approximately Poisson-distributed and low-variance. By relaxing this assumption, we develop a nonparametric framework for online matching that can represent high-variance and correlated arrivals, which are prevalent in real-world demand predictions. Specifically, we propose models that combine a nonparametric distribution for the demand with standard assumptions on the arrival patterns –adversarial or random-order.  We demonstrate that fluid relaxations, which rely solely on expected demand information, have arbitrarily bad performance guarantees. Instead, we propose tighter linear programming relaxations that leverage distribution knowledge and use a novel rounding scheme to obtain matching algorithms that achieve optimal (worst-case) performance guarantees. 

Joint work with Will Ma (Columbia GSB), and ongoing work with Weizhong Zhang (Tepper, CMU)

Speaker's Bio

Ali Aouad is an Assistant Professor at London Business School. His research interests are in the interface of algorithm design under uncertainty and the operations of digital platforms, ranging from marketplaces to cultural institutions.Before joining LBS, he was an applied scientist at Uber Technology in 2018 and received a Ph.D. from the Operations Research Center at MIT in 2017. His work was recognized by the 2022 Second Prize of the INFORMS Junior Faculty Interest Group, the 2021 LBS Junior Faculty Research Award, featured as a 2021 Finalist in the 2021 Best OM paper in Operations Research, and selected for funding in the European Research Council’s 2022 Starting Grant.

Abstract

Among multivariate point processes, the class of Hawkes processes, or mutually exciting processes, provides a natural contender for modeling contagion phenomena. In this talk I'll discuss multivariate population processes in which general, not necessarily Markovian, multivariate Hawkes processes dictate the stochastic arrivals.

The first class of results concerns the identification of the time-dependent joint probability distribution, allowing for general intensity decay functions, general intensity jumps, and general sojourn times, in terms of a fixed-point representation.

The second class of results focuses on risk processes driven by multivariate Hawkes arrivals. The main results are (i) a large deviations principle for the cumulative claim process in the light-tailed regime, (ii) the identification of the decay rate of the ruin probability, and (iii) an importance sampling based efficient simulation procedure to estimate rare events.

Joint work with R.S. Karim and R.J.A. Laeven (both University of Amsterdam)

Speaker's Bio

Michel Mandjes received M.Sc. degrees in mathematics and econometrics from the Free University in Amsterdam, the Netherlands, in 1993, and a Ph.D. in operations research from the same university in 1996. After having been a member of the technical staff at KPN Research (Leidschendam, the Netherlands) and Bell Labs (Murray Hill, New Jersey), a full professor of stochastic operations research at the University of Twente, the Netherlands, and department head at CWI in Amsterdam, he is currently a full professor of applied probability at the University of Amsterdam. He is also affiliated as an advisor with EURANDOM, Eindhoven, the Netherlands, and as a guest professor at the Amsterdam Business School. He was visiting professor at Stanford University (2008-2009), New York University (2013-2014), the University of Melbourne (2005, 2017) and Columbia University (2011). His main research interests are in stochastic processes, queueing processes, efficient simulation techniques, and applications in transportation and communication networks. He is the author of three books (a single-authored book on Gaussian Queues, and coauthored books on Lévy Fluctuation Theory and on the Cramér-Lundberg model), and he has published more than 340 papers in journals and conference proceedings. He was program chair of several leading conferences (INFORMS Applied Probability, Stochastic Networks), he is the Editor-in-Chief of Queueing Systems, and serves on the editorial board of multiple other journals (Stochastic Models, Journal of Applied Probability.

Abstract

Almost all queueing models assume that a job runs on a single server. But this one-server-per-job model is not a good representation of today's compute jobs. A typical data center job today occupies multiple cores concurrently, often thousands of cores.  We refer to a job that concurrently occupies multiple cores as a multiserver job.  Unfortunately, very little is known about response time in multiserver job queueing models. We present the first results on response time for multiserver job queueing models. In particular, we propose a new scheduling policy for multiserver jobs, called ServerFilling, and bound its response time.

All results presented are very recent and are a testament to how little is understood about multiserver jobs. If you are looking for open problems to work on, this is a good talk for you!

Speaker's Bio

Mor Harchol-Balter is the Bruce J. Nelson Professor of Computer Science at Carnegie Mellon University. Mor is a Fellow of both ACM and IEEE. She is a recipient of the McCandless Junior Chair, the NSF CAREER award, and several teaching awards, including the Herbert A. Simon Award and Spira Teaching Award. She is a recipient of dozens of Industrial Faculty Awards including multiple awards from Google, Microsoft, IBM, EMC, Facebook, Intel, Yahoo!, and Seagate. Mor's work focuses on designing new resource allocation policies, including load balancing policies, power management policies, and scheduling policies. Mor is heavily involved in the SIGMETRICS / PERFORMANCE research community, where she has received many paper awards (INFORMS George Nicholson Prize 22, SIGMETRICS 21, SIGMETRICS 19, PERFORMANCE 18, INFORMS APS 18, EUROSYS 16, MASCOTS 16, MICRO 10, SIGMETRICS 03, ITC 03, SIGMETRICS 96). She is also the author of a popular textbook, Performance Analysis and Design of Computer Systems, published by Cambridge University Press, which bridges Operations Research and Computer Science.

Abstract

High dimensional distributions, especially those with heavy tails, are difficult for off-the-shelf MCMC samplers: the combination of unbounded state spaces, diminishing gradient information and local moves, results in empirically observed "stickiness" and poor theoretical mixing properties—eg lack of geometric ergodicity. This talk will introduce a new class of easy to implement MCMC samplers that map the original high dimensional problem in Euclidean space onto a sphere and remedy these notorious mixing problems. Such an approach can be used to construct a Random Walk Metropolis algorithm on the projective sphere. This exhibits very good scalable properties on a wide range of target distributions, except it can still fail the geometric ergodicity test in the heavy-tailed target case. A bouncy particle sampler analogue has even more robust convergence properties and also empirically exhibits rapid convergence. These methods are sensitive to tuning parameters. However, important properties of the algorithms are that in the worst case scenario, they behave just like their vanilla Euclidian cousins. This is joint work with Jun Yang (Oxford) and Krys Latuszynski (Warwick).

Speaker's Bio

Gareth Roberts has broad interests across Computational, Bayesian Statistics and Applied Probability, especially  theory methodology and applications for scalable Bayesian analysis. He completed a BSc in Mathematics at Oxford in 1985 after which he moved to Warwick to complete a PhD in Statistics in 1988. From there he took up the positions of lecturer in statistics at Nottingham 1988-1992, and at Cambridge, 1992-1998. He then became professor of Statistics at Lancaster in 1998 before returning to Warwick in 2007 as Director of the Centre for Research in Statistical Methodology (CRiSM) and Professor of Statistics..

Abstract

Learning in multi-agent systems often poses significant challenges due to interference between agents. In particular, unlike classical stochastic systems, the performance of an agent's action is not drawn i.i.d. from some distribution but is directly affected by the (unobserved) actions of the other agents. This is the reason why most collaborative multi-agent learning approaches aim to globally coordinate all agents' actions to evade this interference. In this talk, we focus on agents in a decentralized bipartite queueing system, where N agents request service from K servers. Prior decentralized approaches aim to decentrally identify a globally coordinated schedule, which leads to various shortcomings: they are restricted to symmetric systems, have performance that degrades exponentially in the number of servers, require communication through shared randomness, two-way message passing or unique identifiers, or are computationally demanding. In contrast, we provide a low-complexity algorithm that is run decentrally by each agent, avoids the shortcomings of "global coordination", and leads the queueing system to have efficient performance in asymmetric bipartite queuing systems while also having additional robustness properties.

Speaker's Bio

Daniel Freund is an Assistant Professor of Operations Management at the MIT Sloan School of Management. Before joining MIT, Daniel received his PhD in applied mathematics from Cornell & spent a year as a research fellow at Lyft Marketplace Labs. There, he worked on the development and design of new algorithms and market mechanisms for the ride-hailing industry. His current research, published in journals such as Operations Research, Mathematics of Operations Research, and the INFORMS Journal on Applied Analytics, applies market design, stochastic modeling, and optimization to problems in in transportation, online platforms, and revenue management among others. It has been recognized with the INFORMS Applied Probability Society Best Publication Award (2021), the George B. Dantzig Dissertation Award (2018), the Daniel H. Wagner Prize for Excellence in Operations Research and Analytics (2018), and a Best Paper award at the ACM SIGCAS COMPASS conference (2018), and has been featured as a finalist for the 2017 George Nicholson and the 2017 and 2022 APS Best Student Paper prizes.

Abstract

In customer support contact centers, every service interaction involves a messaging dialogue between a customer and an agent; together, they exchange information, solve problems, and collectively co-produce the service. Because the service progression is shaped by the history of conversation so far, we propose a bivariate marked Hawkes process cluster model of the customer-agent interaction. 

To evaluate our stochastic model of service, we apply it to an industry contact center dataset containing nearly 5 million messages. Through both a novel residual analysis comparison and several Monte Carlo goodness-of-fit tests, we show that the Hawkes cluster model indeed captures dynamics at the heart of the service and also surpasses classic models that do not incorporate the service history. 

Furthermore, in an entirely data-driven simulation, we demonstrate how this history dependence can be leveraged operationally, showing that widely-used and well-studied customer routing policies can be outperformed with simple modifications according to the Hawkes model. Through analysis of a stylized model proposed in the contact center literature, we prove that service heterogeneity can cause this underperformance, and, moreover, that such heterogeneity will occur if service closures are not carefully managed. Finally, we demonstrate the practical value of the Hawkes service model in designing co-produced services, where synthetic experiments allow us to explore alternative arrangements of responsiveness and responsibility within the contact center. 

Joint work with Andrew Daw, Antonio Castellanos, Jamol Pender, and Leor Gruendlinger.

Speaker's Bio

Galit Yom-Tov is an Associate Professor at IE&M faculty of the Technion. Her research focuses on operations of service systems, in particular, healthcare and contact centers. Prof. Yom-Tov is the co-director of the SEE-Lab (Service Engineering Enterprise) - a worldwide hub for research and teaching in Service Engineering. Her research aims to build models for understanding the impact of customer and agent behavior on service systems and to incorporate these behaviors into operational models of such systems. Her multidisciplinary research approach applies a combination of Data Science and Stochastic Modeling to archives of digital traces from service systems. Her recent work used such data to study the dynamics of customer emotions in contact centers, the reaction of customers to waiting announcements in emergency departments, as well as other aspects of service delivery. Prof. Yom-Tov has published her work in leading operations research journals, including Management Science, M&SOM, OR, and Stochastic Systems. She is serving as an AE for M&SOM and OR journals.

Abstract

We discuss a number of results on the stability and instability of MaxWeight. We discuss connections between MaxWeight and Blackwell’s Approachability Thoerem. We further connections between online learning and queueing. Finally we discuss more recent work connecting adaptive pricing in revenue management and queueing theory. 

Speaker's Bio

Neil Walton is a Professor in Operations Management at Durham University Business School. He received his undergraduate ('05), Masters ('06) and PhD ('10) in Mathematics at the University of Cambridge. His research is in applied probability and principally concerns the decentralized minimization of congestion in networks. He was a lecturer at University of Amsterdam where he held an NWO Veni Fellowship. He then moved to the University of Manchester where was a Reader in Mathematics. Neil has conducted research visits at Microsoft Research Cambridge, the Basque Centre for Mathematics and the Automatic Control Laboratory ETH Zurich. From 2017 to 2019 Neil was the head of probability and statistics group at the University of Manchester. Neil was a Fellow of the Alan Turing Institute and a guest lecturer at London Business School. He has an honorary position at the Manchester University NHS Foundation Trust. Here he is using queueing theory to reduce the waiting list backlog from the covid pandemic. In Durham, he is Deputy Head of the Department of Management and Marketing. He is an associate editor at the journal Stochastic Systems. He is an area editor for stochastic models at Operations Research. He has won best papers awards at the ACM Sigmetrics conference and he was awarded the 2018 Erlang Prize by the Informs Applied Probability Society.

Abstract

The ability to estimate and control tail risks, besides being an integral part of quantitative risk management, is central to running operations requiring high service levels and cyber-physical systems with high-reliability specifications. Despite this significance, scalable algorithmic approaches have remained elusive: This is due to the rarity with which relevant risky samples get observed, and the critical role experts play in devising variance reduction techniques based on instance-specific large deviations studies. Our goal in this talk is to examine if such tailored variance reduction benefits can be instead achieved by instance-agnostic algorithms capable of scaling well across multitude of tail estimation and optimisation tasks.

To this end, we identify an elementary transformation whose push-forward automatically induces efficient importance sampling distributions across a variety of models by replicating the concentration properties observed in less rare samples. This obviates the need to explicitly identify a good change of measure, thereby overcoming the primary bottleneck in the use of importance sampling beyond highly stylized models. Our novel approach is guided by a large deviations principle which brings out the phenomenon of self-similarity of zero variance distributions. Being a nonparametric phenomenon, this self-similarity is manifest in a rich set of objectives modeled with tools such as linear programs, piecewise linear/quadratic objectives, feature maps specified in terms of neural networks, etc., together with a spectrum of light and heavy-tailed multivariate distributions. Joint work with Anand Deo. 

Speaker's Bio

Karthyek Murthy serves as an Assistant Professor in Singapore University of Technology & Design. His research interests lie in applied probability and optimization under uncertainty, with a focus on developing stochastic models & methods for optimization under limited data/resources. Prior to joining SUTD, he was a postdoctoral researcher in Columbia University IEOR department. He obtained his PhD from Tata Institute of Fundamental Research (Mumbai). His research has been recognised with 2021 INFORMS Junior Faculty Forum (JFIG) Paper competition (Third place) and 2019 WSC Best Paper Award. Karthyek serves as an Associate Editor for Stochastic Systems. 

Abstract

In statistical learning tasks such as clustering, recommendation, or dimension reduction, a notion of distance or similarity between points is crucial but might not be directly available as an input.  In previous work, we proposed a new density-based estimator for weighted geodesic distances that takes into account the underlying density of the data, and that is suitable for nonuniform data lying on a manifold of lower dimension than the ambient space. The consistency of the estimator is proven using tools from first passage percolation. The macroscopic distance obtained depends on a unique parameter and we discuss the choice of this parameter and the properties of the obtained distance for machine learning tasks.

Speaker's Bio

Matthieu Jonckheere received his PhD in applied mathematics from the Ecole Polytechnique (Paris, France). He later completed a postdoc at CWI (Amsterdam) and became an assistant professor at Eindhoven University of Technology. He was a Conicet researcher and professor at the University of Buenos Aires from 2010 to 2020, and an invited Professor at DataIA (Paris) in 2021. Since 2021, he is a Director of Research at LAAS, CNRS (Toulouse). He was the recipient of a Basque Country excellence grant in 2015. He is also the co-founder and was the scientific director of two startups specialized in consulting in machine learning. His work focuses on probability theory, performance evaluation of information and communication systems as well as on unsupervised and reinforcement learning.