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

Omer Sahin (), Dugyu Sili (), Utku Unver and Özgür Yılmaz
Additional contact information
Omer Sahin: Stanford University
Dugyu Sili: University of Messina

No 1090, Boston College Working Papers in Economics from Boston College Department of Economics

Abstract: 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.

Keywords: Dynamic matching; kidney exchange; dynamic exchange; spatial economics; Poisson arrival; dynamic optimization; Markov Decision Process; discrete convex analysis; D- multimodularity; superconcavity; componentwise concavity; submodularity; supermodularity. (search for similar items in EconPapers)
JEL-codes: C61 C70 C78 D47 D78 (search for similar items in EconPapers)
Date: 2025-06-15
References: Add references at CitEc
Citations:

Downloads: (external link)
http://fmwww.bc.edu/EC-P/wp1090.pdf main text (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:boc:bocoec:1090

Access Statistics for this paper

More papers in Boston College Working Papers in Economics from Boston College Department of Economics Boston College, 140 Commonwealth Avenue, Chestnut Hill MA 02467 USA. Contact information at EDIRC.
Bibliographic data for series maintained by Christopher F Baum ().