Algorithms for Online Marketplaces: New Approaches to Order Fulfillment and Recommendation Systems

Abstract

This dissertation explores the development and analysis of new algorithms for sequential decision-making under uncertainty, with a focus on optimizing operations and resource allocations within online marketplaces such as e-commerce and rental platforms. The research initially revisits and expands upon the multi-item order fulfillment model, introducing dynamic policies that combine randomized fulfillment strategies, prophet inequalities, and subgradient methods. Our approaches not only achieve asymptotic optimality and strong approximation guarantees in the multi-item fulfillment setting, but also provide insights on how to construct robust policies in scenarios where you have limited resources. The findings in this dissertation introduce a novel approach to the management of resources in complex environments, presenting a nearly optimal framework for developing policies tailored to the complexities of multi-item order fulfillment. Moreover, our analysis can be extended into the domain of rental operations, showcasing the flexibility and broad applicability of our proposed solutions. In addition, the dissertation addresses the complexities of online recommendation systems through a contextual bandit framework, examining both full-feedback and bandit-feedback settings. By formulating the problem to accommodate arbitrary mappings from user contexts to product feature values, this research provides new online algorithms that effectively minimize regret. The analysis extends to general policy classes, revealing an inherent trade-off between approximation accuracy and statistical error for a given policy class.Collectively, this work advances theoretical knowledge in sequential decision-making and algorithm design, providing actionable strategies for improving decision-making processes such as fulfillment and recommendations in online marketplaces.