2025 Theses Doctoral

Online Decision-Making: Applications in Hiring, Inventory Placement, and Matching

Epstein, Boris

This dissertation studies three online decision-making problems motivated by practical applications in hiring pipelines, inventory placement, and online matching. In all cases, a decision-maker must take actions sequentially, often under time or resource constraints, and with partial or stochastic information about the future. A unifying objective is to develop computationally tractable policies that perform near-optimally relative to natural benchmarks, such as hindsight-optimal solutions or adaptive policies with full information. To this end, we design and analyze approximation algorithms with provable guarantees, drawing on linear programming relaxations, surrogate optimization, and randomized rounding.

The first chapter considers three hiring problems that differ in how offers are made to candidates: sequentially, in parallel, or all at once. We introduce a linear programming framework that captures each of these settings and develop simple, non-adaptive policies that attain approximation factors of at least 1 - 1/𝑒, improving upon prior guarantees. Our results unify and extend existing prophet inequality models, and provide theoretical and numerical insights into how firms should sequence offers based on operational constraints.

In the second chapter, we address the inventory placement problem in e-commerce, where inventory must be allocated to warehouses before facing stochastic demand. We formulate this as a two-stage optimization problem and show that optimizing a surrogate ``offline'' objective yields good performance in the downstream online matching phase. A key technical contribution is the development of tight approximation guarantees via randomized rounding of LP relaxations, even in the multi-product setting. We complement our theoretical findings with extensive simulations, highlighting when optimistic or pessimistic placement heuristics are preferable in practice.

The third chapter focuses on online bipartite matching under limited historical data. We compare a range of algorithmic approaches---model-based, data-agnostic, and simulation-trained neural policies---through the lens of sample efficiency and robustness. Our results show that when data is scarce, structured model-based policies generalize better and offer competitive performance. In contrast, parameterized neural policies perform best in data-rich regimes, but at the cost of longer training and testing times.

Across all three chapters, we emphasize algorithmic strategies that scale efficiently and adapt to real-world constraints. Thematic connections---particularly the use of LP relaxations, surrogate models, and randomized rounding---help bridge seemingly distinct applications, and suggest a broader framework for designing principled, data-aware online decision policies.