Online Assortment Optimization for Two-Sided Matching Platforms

Ali Aouad () and Daniela Saban ()
Additional contact information
Ali Aouad: Management Science and Operations, London Business School, London NW1 4SA, United Kingdom
Daniela Saban: Operations, Information, and Technology, Stanford Graduate School of Business, Stanford University, California 94305

Management Science, 2023, vol. 69, issue 4, 2069-2087

Abstract: 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. After spending some time on the platform, each supplier reviews all the match requests she has received and, based on her preferences, she 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 establish that a simple greedy algorithm is 1/2-competitive against an optimal clairvoyant algorithm that knows in advance the full sequence of customers’ arrivals. However, unlike related online assortment problems, no randomized algorithm can achieve a better competitive ratio, even in asymptotic regimes. To advance beyond this general impossibility, we consider structured settings where suppliers’ preferences are described by the multinomial logit and nested logit choice models. We develop new forms of balancing algorithms, which we call preference-aware , that leverage structural information about suppliers’ choice models to design the associated discount function. In certain settings, these algorithms attain competitive ratios provably larger than the standard “barrier” of 1 − 1 / e in the adversarial arrival model. Our results suggest that the shape and timing of suppliers’ choices play critical roles in designing online assortment algorithms for two-sided matching platforms.

Keywords: online algorithms; two-sided matching; assortment optimization; choice models (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.2022.4464 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:69:y:2023:i:4:p:2069-2087

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().