eduzhai > Applied Sciences > Computer Science >

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

  • Peter
  • (0) Download
  • 20210219
  • Save

... pages left unread,continue reading

Document pages: 69 pages

Abstract: We consider a matching market where buyers and sellers arrive according toindependent Poisson processes at the same rate and independently abandon themarket if not matched after an exponential amount of time with the same mean.In this centralized market, the utility for the system manager from matchingany buyer and any seller is a general random variable. We consider a sequenceof systems indexed by $n$ where the arrivals in the $n^{ mathrm{th}}$ systemare sped up by a factor of $n$. We analyze two families of one-parameterpolicies: the population threshold policy immediately matches an arriving agentto its best available mate only if the number of mates in the system is above athreshold, and the utility threshold policy matches an arriving agent to itsbest available mate only if the corresponding utility is above a threshold.Using an asymptotic fluid analysis of the two-dimensional Markov process ofbuyers and sellers, we show that when the matching utility distribution islight-tailed, (i.e., the expected value of the maximum of many randomvariables is a regularly varying function with $ alpha=0$) the populationthreshold policy with threshold $ frac{n}{ ln n}$ is asymptotically optimalamong all policies that make matches only at agent arrival epochs. In theheavy-tailed case (i.e., $ alpha in(0,1)$), we characterize the optimalthreshold level for both policies. although they do not attain the performanceof our loose upper bound. We also study the utility threshold policy in anunbalanced matching market with heavy-tailed matching utilities, and find thatthe buyers and sellers have the same asymptotically optimal utility threshold.

Please select stars to rate!


0 comments Sign in to leave a comment.

    Data loading, please wait...