Optimal Dynamic Matching under Local Compatibility: An Application to Kidney Exchange

In the past two decades, the design and implementation of living donor kidney exchange clearinghouses have been a major success story in market design. Instead of batching and optimizing exchanges over a fixed pool of incompatible patient-donor pairs, the busiest programs now operate dynamically, matching pairs as they arrive. This feature has also sparked interest in dynamic matching mechanisms. Yet for general matching problems with high-dimensional state spaces, a full characterization of optimal dynamic mechanisms remains elusive, and only approximate solutions are known. We develop a new methodology to characterize and compute dynamically optimal mechanisms for bilateral matching over arbitrary state spaces, provided that compatibility between agent types follows a linear spatial structure. This technique applies to optimal dynamic kidney exchange and extends to other spatial matching problems. Our approach leverages second-order properties of the value function, extending recent advances in Markov Decision Processes and queueing systems, which traditionally focus only on substitutable components.