Dynamic Type Matching
Top Cited Papers
- 1 January 2022
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Manufacturing & Service Operations Management
- Vol. 24 (1) , 125-142
Abstract
Problem definition: We consider an intermediary’s problem of dynamically matching demand and supply of heterogeneous types in a periodic-review fashion. Specifically, there are two disjoint sets of demand and supply types, and a reward for each possible matching of a demand type and a supply type. In each period, demand and supply of various types arrive in random quantities. The platform decides on the optimal matching policy to maximize the expected total discounted rewards, given that unmatched demand and supply may incur waiting or holding costs, and will be fully or partially carried over to the next period. Academic/practical relevance: The problem is crucial to many intermediaries who manage matchings centrally in a sharing economy. Methodology: We formulate the problem as a dynamic program. We explore the structural properties of the optimal policy and propose heuristic policies. Results: We provide sufficient conditions on matching rewards such that the optimal matching policy follows a priority hierarchy among possible matching pairs. We show that those conditions are satisfied by vertically and unidirectionally horizontally differentiated types, for which quality and distance determine priority, respectively. Managerial implications: The priority property simplifies the matching decision within a period, and the trade-off reduces to a choice between matching in the current period and that in the future. Then the optimal matching policy has a match-down-to structure when considering a specific pair of demand and supply types in the priority hierarchy.Keywords
All Related Versions
This publication has 27 references indexed in Scilit:
- Rollout Algorithms for Discrete Optimization: A Survey2013
- Online Stochastic Matching: Online Actions Based on Offline StatisticsMathematics of Operations Research, 2012
- A Broader View of Designing the Liver Allocation SystemOperations Research, 2012
- Exact FCFS Matching Rates for Two Infinite Multitype SequencesOperations Research, 2012
- Perspectives of approximate dynamic programmingAnnals of Operations Research, 2012
- Dynamic Capacity Management with SubstitutionOperations Research, 2009
- Efficient Kidney Exchange: Coincidence of Wants in Markets with Compatibility-Based PreferencesAmerican Economic Review, 2007
- Monge properties, discrete convexity and applicationsEuropean Journal of Operational Research, 2007
- Kidney ExchangeThe Quarterly Journal of Economics, 2004
- On simple linear programming problems1963