Analysis of matching models and the Braess paradox

I. Garin, J. Doncel

Dynamic matching models describe systems in which items of different types arrive randomly over time and are paired according to compatibility constraints. In this work, we study such models under the First-Come–First-Matched (FCFM) policy, focusing on compatibility graphs where every node has a self-loop. The evolution of the system is modeled as a finite-state discrete-time Markov chain.

Our main goal is to investigate the presence of the Braess paradox, a phenomenon where adding connections may worsen performance. Performance is measured through the expected number of unmatched items in steady state. Using product-form results for the stationary distribution, we derive formulas to compare graph structures.

We establish conditions under which the Braess paradox occurs and explore cases such as quasi-complete graphs and symmetric arrivals. These results highlight how increased flexibility can lead to worse outcomes.

Palabras clave: Dynamic matching models, Braess paradox, Markov chains

GT Procesos Estocásticos y sus Aplicaciones III
3 de septiembre de 2026  09:00
Aula 26

C. Cañada Moreno, M. González Velasco, I. M. del Puerto García

I. M. del Puerto García, M. González Velasco, C. Minuesa Abril, A. N. Vidyashankar

M. González, R. E. Lillo, P. Ramírez-Cobo, L. Senade