Graph Neural Networks Optimize Dynamic Matching Markets

The paper introduces a novel reinforcement learning framework for optimizing dynamic matching markets, which are characterized by continuous arrivals, departures, and evolving opportunities. This framework operates on finite, weighted graphs that change over time, addressing the critical decision of when and whom to match. A key insight is an event-time reduction, proving that optimal decisions only need to be made immediately after exogenous events. The approach uses a Graph Neural Network (GNN) to approximate the optimal edge-wise Q-function, reducing the learning task to graph values rather than state-action values. This GNN is trained using temporal-difference learning and integrated into a forward-greedy matching heuristic. Evaluations on benchmarks like binary-type matching and kidney paired donation demonstrate that the learned policy significantly outperforms immediate or threshold-greedy rules, adapting effectively to connectivity and exit information.