Details

Autor(en) / Beteiligte

• Blanchet, Jose H.
• Reiman, Martin I.
• Shah, Virag
• Wein, Lawrence M.
• Wu, Linjia

Titel

Asymptotically Optimal Control of a Centralized Dynamic Matching Market with General Utilities

Ist Teil von

• Operations research, 2022-11, Vol.70 (6), p.3355-3370

Ort / Verlag

Linthicum: INFORMS

Erscheinungsjahr

2022

Quelle

Informs PubsOnline

Beschreibungen/Notizen

• The utility of a match in a two-sided matching market often depends on a variety of characteristics of the two agents (e.g., a buyer and a seller) to be matched. In contrast to the matching market literature, this utility may best be modeled by a general matching utility distribution. In “Asymptotically Optimal Control of a Centralized Dynamic Matching Market with General Utilities,” Blanchet, Reiman, Shah, Wein, and Wu consider general matching utilities in the context of a centralized dynamic matching market. To analyze this difficult problem, they combine two asymptotic techniques: extreme value theory (and regularly varying functions) and fluid asymptotics of queueing systems. A key trade-off in this problem is market thickness: Do we myopically make the best match that is currently available, or do we allow the market to thicken in the hope of making a better match in the future while avoiding agent abandonment? Their asymptotic analysis derives quite explicit results for this problem and reveals how the optimal amount of market thickness increases with the right tail of the matching utility distribution and the amount of market imbalance. Their use of regularly varying functions also allows them to consider correlated matching utilities (e.g., buyers have positively correlated utilities with a given seller), which is ubiquitous in matching markets. We consider a matching market where buyers and sellers arrive according to independent Poisson processes at the same rate and independently abandon the market if not matched after an exponential amount of time with the same mean. In this centralized market, the utility for the system manager from matching any buyer and any seller is a general random variable. We consider a sequence of systems indexed by n where the arrivals in the n th system are sped up by a factor of n . We analyze two families of one-parameter policies: the population threshold policy immediately matches an arriving agent to its best available mate only if the number of mates in the system is above a threshold, and the utility threshold policy matches an arriving agent to its best available mate only if the corresponding utility is above a threshold. Using an asymptotic fluid analysis of the two-dimensional Markov process of buyers and sellers, we show that when the matching utility distribution is light-tailed, the population threshold policy with threshold n ln   n is asymptotically optimal among all policies that make matches only at agent arrival epochs. In the heavy-tailed case, we characterize the optimal threshold level for both policies. We also study the utility threshold policy in an unbalanced matching market with heavy-tailed matching utilities and find that the buyers and sellers have the same asymptotically optimal utility threshold. To illustrate our theoretical results, we use extreme value theory to derive optimal thresholds when the matching utility distribution is exponential, uniform, Pareto, and correlated Pareto. In general, we find that as the right tail of the matching utility distribution gets heavier, the threshold level of each policy (and hence market thickness) increases, as does the magnitude by which the utility threshold policy outperforms the population threshold policy. Funding: J. H. Blanchet received financial support from the U.S. National Science Foundation [Grants 1915967, 1820942, and 1838576]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2021.2186 .