ORIE Colloquium: Daniela Saban (Stanford University), March 16, 2021
From Henry Lam
“Online Assortment Optimization for Two-sided Matching Platforms”
Motivated by online labor
markets, we consider the online assortment optimization problem faced by a
two-sided matching platform that hosts a set of suppliers waiting to match with
a customer. Arriving customers are shown an assortment of suppliers, and may
choose to issue a match request to one of them. Before leaving the platform,
each supplier reviews all the match requests he has received, and based on his
preferences, he chooses whether to match with a customer or to leave unmatched.
We study how platforms should design online assortment algorithms to maximize
the expected number of matches in such two-sided settings.
We show that, when suppliers do not immediately accept/reject match requests, our problem is fundamentally different from standard (one-sided) assortment problems, where customers choose over a set of commodities. We establish that a greedy algorithm, that offers to each arriving customer the assortment that maximizes the expected increase in matches, is 1/2 competitive when compared against the clairvoyant algorithm that knows in advance the full sequence of customers’ arrivals. In contrast with related online assortment problems, we show that there is no randomized algorithm that can achieve a better competitive ratio, even in asymptotic regimes. Next, we introduce a class of algorithms, termed preference-aware balancing algorithms, that achieve significantly better competitive ratios when suppliers' preferences follow the Multinomial Logit and the Nested Logit choice models. Using prior knowledge about the “shape" of suppliers' preferences, these algorithms are calibrated to "balance'' optimally the match requests received by suppliers. Overall, our results suggest that the timing of suppliers' decisions and the structure of suppliers' preferences play a fundamental role in designing online two-sided assortment algorithms. (joint work with Ali Aouad)
Daniela Saban is an associate professor of Operations, Information, and Technology at Stanford University’s Graduate School of Business. Her research explores issues related to the design and operations of online marketplaces, including online matching markets and procurement platforms. Prior to joining Stanford, Daniela spent a semester as a visiting scholar in the Simons Institute for the Theory of Computing at UC Berkeley. She received her PhD in Decision, Risk, and Operations from Columbia Business School and holds a B.Sc. and an M.Sc. in Computer Science from Universidad de Buenos Aires.