Online Matching Frameworks Under Stochastic Rewards, Product Ranking, and Unknown Patience
成果类型：
Article
署名作者：
Brubach, Brian; Grammel, Nathaniel; Ma, Will; Srinivasan, Aravind
署名单位：
Wellesley College; University System of Maryland; University of Maryland College Park; Columbia University; Columbia University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.2021.0371
发表日期：
2025
关键词：
摘要：
We study generalizations of online bipartite matching in which each arriving vertex (customer) views a ranked list of offline vertices (products) and matches to (purchases) the first one they deem acceptable. The number of products that the customer has patience to view can be stochastic and dependent on the products seen. We develop a framework that views the interaction with each customer as an abstract resource consumption process and derive new results for these online matching problems under the adversarial, nonstationary, and independent and identically-distributed arrival models, assuming we can (approximately) solve the product ranking problem for each single customer. To that end, we show new results for product ranking under two cascade-click models: an optimal algorithm when each item has its own hazard rate for making the customer depart and a 1/2-approximate algorithm when the customer has a general item-independent patience distribution. We also present a constant-factor 0.027-approximate algorithm in a new model where items are not initially available and arrive over time. We complement these positive results by presenting three additional negative results relating to these problems.