Technical Note: Assortment Planning for Two-Sided Sequential Matching Markets

• 成果类型: Article; Early Access
• 署名作者: Ashlagi, Itai; Krishnaswamy, Anilesh K.; Makhijani, Rahul; Saban, Daniela; Shiragur, Kirankumar
• 署名单位: Stanford University; Duke University; Facebook Inc; Stanford University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.2327
• 发表日期: 2022
• 关键词: networks/graphs; matchings; analysis of algorithms; utility/preference; Applications

摘要

Two-sided matching platforms provide users with menus of match recommendations. To maximize the number of realized matches between the two sides (referred to herein as customers and suppliers), the platform must balance the inherent tension between recommending more suppliers to customers to increase the chances that they like one of them and avoiding the conflicts that arise when customers, who are given more options, end up choosing the same suppliers. We introduce a stylized model to study the above tradeoff. The platform offers each customer a menu of suppliers, and customers choose, simultaneously and independently, to either select a supplier from their menu or remain unmatched. Suppliers then see the set of customers that have selected them and choose to either match with one of these customers or remain unmatched. A match occurs if a customer and a supplier choose each other (in sequence). Agents' choices are probabilistic and proportional to the public scores of agents in their menu and a score that is associated with the outside option of remaining unmatched. The platform's problem is to construct menus for customers, so as to maximize the total number of matches. We first show that this problem is strongly NP-hard. Then, we provide an intuitive efficient algorithm that achieves a constant-factor approximation to the optimal expected number of matches. Our algorithm uses bucketing (grouping similar suppliers into buckets) together with linear-programming-based relaxations and rounding techniques.