Graph neural networks crack dynamic matching markets in new arXiv study

Dynamic matching markets force a choice: match now for immediate value, or wait for better future matches? A new arXiv paper (2607.28925) from Genta Okada, Shunya Noda, Junpei Komiyama, and Akira Matsushita tackles this with graph neural networks (GNNs) and reinforcement learning. The authors model an infinite-horizon continuous-time system with stochastic arrivals, node-type transitions, and exogenous exits. They prove an event-time reduction—planners only need to act immediately after each external event—and show the optimal edge-wise Q-function collapses to a single continuation-value function on post-decision residual graphs. This dramatically reduces what needs to be learned: from state-action pairs to graph-level values, approximated via a GNN trained with temporal-difference learning and applied through forward-greedy matching.

In experiments, the learned policy substantially outperforms immediate and threshold-greedy rules on a binary-type benchmark, preserving common nodes for rare but valuable matches while forming lower-value matches only in thick pools. On kidney paired donation benchmarks, the GNN policy matches immediate greedy performance when exits are unpredictable, but recovers patient matching logic when exit warnings are reliable. Across intermediate warning probabilities, it beats the better of both greedy baselines. These results demonstrate that residual-graph value learning produces state-dependent matching policies that adapt to realized connectivity and exit information—offering a practical template for organ exchange platforms, ride-hailing, and other two-sided markets where timing is everything.