  We study dynamic matching in an infinite-horizon stochastic market. While all
agents are potentially compatible with each other, some are hard-to-match and
others are easy-to-match. Agents prefer to be matched as soon as possible and
matches are formed either bilaterally or indirectly through chains. We adopt an
asymptotic approach and compute tight bounds on the limit of waiting time of
agents under myopic policies that differ in matching technology and
prioritization.
  We find that the market composition is a key factor in the desired matching
technology and prioritization level. When hard-to-match agents arrive less
frequently than easy-to-match ones (i) bilateral matching is almost as
efficient as chains (waiting times scale similarly under both, though chains
always outperform bilateral matching by a constant factor), and (ii) assigning
priorities to hard-to-match agents improves their waiting times. When
hard-to-match agents arrive more frequently, chains are much more efficient
than bilateral matching and prioritization has no impact.
  We further conduct comparative statics on arrival rates. Somewhat
surprisingly, we find that in a heterogeneous market and under bilateral
matching, increasing arrival rate has a non-monotone effect on waiting times,
due to the fact that, under some market compositions, there is an adverse
effect of competition. Our comparative statics shed light on the impact of
merging markets and attracting altruistic agents (that initiate chains) or
easy-to-match agents.
  This work uncovers fundamental differences between heterogeneous and
homogeneous dynamic markets, and potentially helps policy makers to generate
insights on the operations of matching markets such as kidney exchange
programs.
