Performance paradox in matching systems

Shu Li, Ana Bušić, Jean-Michel FourneauSPIRE 2026

TL;DR

In stochastic matching systems, adding more "flexibility" (new matching rules) is intuitively expected to improve performance. This paper demonstrates a counter-intuitive performance paradox: adding an edge to a compatibility graph can actually increase the system's backlog. The authors show this paradox is structurally prevalent, occurring even in systems without "star" subgraphs, in multigraphs, and in systems where items can abandon the queue.

What Problem Does This Paper Address?

The paper investigates stochastic matching systems operated under a First-Come-First-Matched (FCFM) discipline. Imagine a system where different classes of items arrive over time (like tasks and resources, or passengers and taxis). These items are represented as vertices on a "compatibility graph." An edge between two vertices means those two classes of items can be matched and removed from the system.

Common sense suggests that if you add a new edge to this graph—effectively allowing more types of items to match with each other—the system should become more efficient, and the number of items waiting in the buffer (the backlog) should decrease. However, previous research identified a "performance paradox" where the opposite happens. This paper seeks to determine how widespread this paradox is: Does it require specific graph structures like "stars"? Does it persist if items have a "timeout" (abandonment)? Or if the graph allows self-loops?

Methods

The authors use a mix of stochastic modeling, Markov chain theory, and numerical evaluation:

  • Stationary Distribution Analysis: For connected, nonbipartite graphs, they utilize existing closed-form stationary distributions to expand performance metrics based on "independent sets" of the graph.
  • Lumpability: To handle the complexity of systems with abandonment (where items leave the buffer at a rate $\delta$ if not matched), they apply "Ball–Yeo’s strong lumpability." This allows them to simplify complex state spaces (like a complete graph minus one edge) into more tractable forms (like a smaller complete graph) to derive explicit performance regimes.
  • Numerical Evaluation: For multigraphs (which can include self-loops), they use numerical methods to identify specific instances where the paradox occurs.

Datasets

Not discussed in the paper. This is a theoretical and mathematical study; the "data" consists of synthetic arrival rate vectors ($\mu$) and graph topologies used to prove the existence of the paradox.

Key Insights and Ideas

  • Stars are not essential: Previous examples of this paradox relied on "star" subgraphs. This paper proves that paradoxes occur on star-free graphs, meaning the phenomenon is more fundamental to matching dynamics than previously thought.
  • The Abandonment Persistence: One might assume that if items can leave the system on their own (abandonment), the backlog would eventually stabilize and negate the paradox. The authors show that the paradox persists under abandonment, identifying specific arrival rate regimes where adding an edge still increases the long-run backlog.
  • Multigraphs and Self-loops: The paradox extends to multigraphs. However, the authors note a significant exception: they have yet to find a paradox on graphs where every vertex has a self-loop. This suggests that universal self-compatibility might be a "cure" for the paradox.
  • Lumping Logic: The paper provides a neat mathematical trick for analyzing $K_n$ (complete graphs) minus an edge: by merging two classes into one, the system behaves like a smaller complete graph ($K_{n-1}$), allowing for exact performance comparisons.

Key Results

  • Mathematical Proof of Paradox: The authors identify non-empty regions of arrival rates ($\mu$) where the expected backlog $E[G + e, \mu]$ is strictly greater than $E[G, \mu]$.
  • Generalization: They successfully extended the paradox from simple graphs to multigraphs and systems with abandonment.
  • Tractable Families: They provided closed-form expressions for the empty-state probability and expected backlog for complete graphs ($K_n$) under abandonment, which are usually difficult to solve because they lack a standard "product form" solution.

Limitations and Future Work

  • Topology Characterization: While the paper shows the paradox is prevalent, it does not yet provide a complete characterization of which specific graph topologies will always trigger a paradox.
  • Policy Scope: The study focuses primarily on the FCFM discipline. The authors suggest that future work should investigate whether these paradoxes occur under other matching policies (e.g., priority-based or random matching).
  • The Self-Loop Mystery: The observation that graphs with universal self-loops don't seem to exhibit the paradox remains a conjecture that requires further formal investigation.

Summary updated

Abstract

International audience
BibTeX
@inproceedings{li2026performance,
  author = {Shu Li and Ana Bušić and Jean-Michel Fourneau},
  title = {{Performance paradox in matching systems}},
  booktitle = {SPIRE},
  year = {2026},
}

Loading related content...

Figure