# Stochastic dynamic matching: A mixed graph-theory and linear-algebra approach

Céline Comte, Fabien Mathieu, Ana Bušić

► To cite this version:

Céline Comte, Fabien Mathieu, Ana Bušić. Stochastic dynamic matching: A mixed graph-theory and linear-algebra approach. 2023. hal-03502084v4

HAL Id: hal-03502084

https://hal.science/hal-03502084v4

Preprint submitted on 25 Jun 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
# Online Stochastic Matching: A Polytope Perspective

Céline Comte, Fabien Mathieu, Sushil Mahavir Varma, Ana Bušić

► To cite this version:

Céline Comte, Fabien Mathieu, Sushil Mahavir Varma, Ana Bušić. Online Stochastic Matching: A Polytope Perspective. 2025. hal-03502084v6

HAL Id: hal-03502084

https://hal.science/hal-03502084v6

Preprint submitted on 11 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Stochastic dynamic matching: A mixed graph-theory and linear-algebra approach

Céline Comte<fnref n="1" /> ☑

Eindhoven University of Technology, Eindhoven, The Netherlands

LAAS-CNRS, CNRS, Toulouse, France

Fabien Mathieu ☑

LINCS, Paris, France

Swapcard, Paris, France

Ana Bušić ☑

Inria, Paris, France

DI ENS, CNRS, PSL University, Paris, France

## Abstract

Stochastic dynamic matching problems have recently drawn attention in the stochastic-modeling community due to their numerous applications, ranging from supply-chain management to kidney exchange programs. In this paper, we consider a matching problem in which items of different classes arrive according to independent Poisson processes. Unmatched items are stored in a queue, and compatibility constraints are described by a simple graph on the classes, so that two items can be matched if their classes are neighbors in the graph. We analyze the efficiency of matching policies, not only in terms of system stability, but also in terms of matching rates between different classes.

Our results rely on the observation that, under any stable policy, the matching rates satisfy a conservation equation that equates the arrival and departure rates of each item class. Our main contributions are threefold. We first introduce a mapping between the dimension of the solution set of this conservation equation, the structure of the compatibility graph, and the existence of a stable policy. In particular, this allows us to derive a necessary and sufficient stability condition that is verifiable in polynomial time. Secondly, we describe the convex polytope of non-negative solutions of the conservation equation. When this polytope is reduced to a single point, we give a closed-form expression of the solution; in general, we characterize the vertices of this polytope using again the graph structure. Lastly, we study which vectors of the polytope can be achieved by a stable policy. We show that the set of vectors reached by stable greedy policies is included in the interior of the polytope, and that the inclusion is strict in general. In contrast, we conjecture that non-greedy policies can reach any point of the interior of the polytope; whether they can also reach the boundary of the polytope depends on a simple condition on the vertices.

**2012 ACM Subject Classification** Mathematics of computing → Queueing theory; Mathematics of computing → Markov processes; Mathematics of computing → Matchings and factors

**Keywords and phrases** stochastic dynamic matching, graph theory, linear algebra, stability, matching rates, conservation equation

## 1 Introduction

Stochastic dynamic matching problems, in which items arrive at random instants to be matched with other items, have recently attracted much attention in the stochastic-modeling community. These challenging control problems are highly relevant in many applications, including supply-chain management, pairwise kidney exchange programs, and online markets. In pairwise kidney exchange programs for example, each item represents a donor-receiver pair, and two pairs can be matched if the donor of each pair is compatible

<footnote n="1">¹ Corresponding author.</footnote>
# Online Stochastic Matching: A Polytope Perspective

Céline Comte<fnref n="1" /> ⬄ ⬆ ID

<figure><img src="image_2.png" /></figure>

<figure><img src="image_3.png" /></figure>

Eindhoven University of Technology, Eindhoven, The Netherlands

CNRS and LAAS, Toulouse, France

Fabien Mathieu ⬄ ⬆ ID

<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /></figure>

Swapcard, Paris, France

Sorbonne Université, CNRS, LIP6, Paris, France

Sushil Mahavir Varma ⬄ ⬆ ID

<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /></figure>

Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, US

Ana Bušić ⬄ ⬆ ID

<figure><img src="image_8.png" /></figure>

<figure><img src="image_9.png" /></figure>

Inria, Paris, France

DI ENS, CNRS, PSL University, Paris, France

## Abstract

Stochastic dynamic matching problems have recently gained attention in the stochastic-modeling community due to their diverse applications, such as supply-chain management and kidney exchange programs. In this paper, we study a matching problem where items of different classes arrive according to independent Poisson processes. Unmatched items are stored in a queue, and compatibility between items is represented by a simple graph, where items can be matched if their classes are connected. We analyze matching policies in terms of stability, delay, and long-term matching rate optimization. Our approach relies on the conservation equation, which ensures a balance between arrivals and departures in any stable system. Our main contributions are as follows. We establish a link between the existence of stable policies, the dimensionality of the solution set of the conservation equation, and the compatibility graph’s structure. We describe the convex polytope formed by non-negative solutions to the conservation equation, and we design policies that can achieve or closely approximate the vertices of this polytope. Lastly, we discuss potential extensions of our results beyond the main assumptions of this paper.

**2012 ACM Subject Classification** Mathematics of computing → Queueing theory; Mathematics of computing → Markov processes; Mathematics of computing → Matchings and factors

**Keywords and phrases** stochastic dynamic matching, graph theory, linear algebra, stability, matching rates, conservation equation

**Supplementary Material** Stochastic Matching Package

Software (Python, PyPi): Documentation [35]

## 1 Introduction.

Stochastic dynamic matching problems, in which items arrive at random instants to be matched with other items, have recently attracted much attention in the stochastic-modeling community. These challenging control problems are highly relevant in many applications, including supply-chain management, pairwise kidney exchange programs, and online marketplaces. In pairwise kidney exchange programs for example, each item represents a donor-receiver pair, and two pairs can be matched if the donor of each pair is compatible with the receiver of the other pair. In online marketplaces, items are typically divided into

<footnote n="1">¹ Corresponding author.</footnote>
with the receiver of the other pair. In online marketplaces, items are typically divided into
two categories, called demand and supply, and the goal is to maximize a certain long-term
performance criteria by appropriately matching demand items with supply items.

In this paper, we consider the following dynamic matching problem<fnref n="2" />. Items of different
classes arrive according to independent Poisson processes. Compatibility constraints between
items are described by a simple graph on their classes, such that two items can be matched
if their classes are neighbors in the graph. Unmatched items are stored in the queue of their
class, and the matching policy decides which matches are performed and when. All in all,
a stochastic matching model is described by a triplet (*G*, *λ*, *Φ*), where *G* = (*V*, *E*) is the
compatibility graph, *λ* = (*λ*₁, *λ*₂, ..., *λ*ₙ) is the vector of per-class arrival rates, and *Φ* is the
matching policy. In Figure 1 for instance, there are four item classes numbered from 1 to 4;
classes 2 and 3 are compatible with all classes, while classes 1 and 4 are compatible only
with classes 2 and 3.

<figure><img src="image_1.png" /><figcaption>Figure 1 Illustration of a matching model ($G, \lambda, \Phi$) on the diamond graph.</figcaption></figure>

We consider two performance indicators, namely the stability and the matching rates along edges. Formally, a matching model ($G, \lambda, \Phi$) is said to be stable if the associated Markov chain is positive recurrent. Assuming that this matching model is stable, the matching rate $\mu_k$ along an edge $k \in E$ with endpoints $i, j \in V$ is the rate at which class-i items and class-j items are matched. Our end goal is to characterize the matching rates that are achievable under stable matching policies and to use this characterization to design matching policies that achieve certain matching rate vectors. Our results show that these two performance indicators are sometimes incompatible, in the sense that optimizing a function of the matching rate vector can lead to instability in some settings.

1.1 Motivation

Besides providing us with criteria to compare the long-term impact of different matching policies, stability conditions and matching rates have practical value in many instances of matching models.

<footnote n="2">² Detailed definitions of the concepts discussed here will be given in Section 2.</footnote>
two categories, called demand and supply, and the goal is to maximize a certain long-term performance criteria by appropriately matching demand items with supply items.

In this paper, we consider the following dynamic matching problem$^2$. Items of different classes arrive according to independent Poisson processes. Compatibility constraints between items are described by a simple graph on their classes, such that two items can be matched if their classes are neighbors in the graph. Unmatched items are stored in the queue of their class, and a matching policy decides which matches are performed and when. All in all, a stochastic matching model is described by a triplet $(G, \lambda, \Phi)$, where $G = (V, E)$ is the compatibility graph, $\lambda = (\lambda_1, \lambda_2, \dots, \lambda_n)$ is the vector of per-class arrival rates, and $\Phi$ is the matching policy. Assuming stability, i.e. a steady-state behavior, the matching rate vector, denoted $\mu$, represents the average rates at which each type of match is performed. In Figure 1 for instance, there are four item classes numbered from 1 to 4; classes 2 and 3 are compatible with all classes, while classes 1 and 4 are compatible only with classes 2 and 3.

<figure><img src="image_10.png" /><figcaption>Figure 1 Illustration of a matching model $(G, \lambda, \Phi)$ on the diamond graph.</figcaption></figure>

## 1.1 Motivation.

A central challenge in matching models is to characterize the set of matching rates that can be achieved by stable policies, i.e. policies that guarantee the system remains under control over time, and to understand the delay properties associated with these rates. Criteria like stability, delay, and matching rates are central to comparing the long-term performance of different matching policies and have practical relevance in real applications like organ exchanges or online matching platforms.

Many studies adopt an optimization viewpoint, where each match of type $k \in E$ gets a reward $r_k$, and the objective is to find a policy $\Phi$ that maximizes the long-run reward rate $\sum_{k \in E} r_k \mu_k$. This paradigm has clear practical appeal: for instance, in organ exchange programs, rewards capture metrics such as quality of life and survival rates after transplant [7]. Yet, natural reward-maximizing policies such as greedy priority-based schemes can jeopardize stability, as noted by [34, Section 5]. Moreover, there is no guarantee that the ordering of the resulting matching rates is consistent with the edge priorities.

These issues gain further complexity when a network of matching models is considered. For example, the matching rates $\mu$ from a stable first-level model $(G, \lambda, \Phi)$ can be the

<footnote>$^2$ Detailed definitions of the concepts discussed here will be given in Section 2.</footnote>
## Maximal reward

First assume that a reward $w_k$ is earned every time a match is performed between items of the classes $i$ and $j$ that are endpoints of edge $k$, for each $k \in E$, and that we look for a policy $\Phi$ that maximizes the long-run reward rate $\sum_{k \in E} w_k \mu_k$ while making the system stable. This optimization problem is relevant in applications to organ exchange programs, where the rewards capture the desirability of a given match, accounting for metrics such as the quality of life after transplant and the survival rates of the recipients and donors [7].

Perhaps the most natural policy to consider is a priority policy whereby each incoming item is immediately matched with an unmatched item of the compatible class leading to the highest reward, if any. Unfortunately, it was observed in [26, Section 5] that such a priority policy may lead to instability. Furthermore, the use of a matching policy with a specific priority order for edges does not guarantee that the ordering of the resulting matching rates is consistent with the edge priorities. Depending on the properties of the compatibility graph $G$ and the arrival rate vector $\lambda$, we will introduce either a stable matching policy that yields the optimal reward (if such a stable policy exists) or a family of stable policies that we conjecture get arbitrarily close to the optimal.

## Chained matching

Matching rates become also crucial when a stable “first-level” matching model $(G, \lambda, \Phi)$ is the source of the (non-Poisson) arrival process of a “second-level” matching model (or, more generally, of another stochastic system). The second-level model consists of a compatibility graph $G' = (E, E')$ whose nodes are the edges of $G$. In this context, the matching rate vector $\mu$ of the first-level model represents the arrival rate vector in the second-level model. The ability to control this vector $\mu$ becomes instrumental in stabilizing or optimizing performance in the second-level model. Such two-level matching systems are found in various applications, such as quantum switches [32, 34] for example.

## 1.2 Contributions

We propose a unified approach to study two closely-related performance criteria, namely the stability and the matching rates along edges. The following observation, powerful despite its simplicity, is fundamental to all our results: under any stable policy, the arrival rate of class-i items is equal to the departure rate of these items, which in turn is equal to the sum of the matching rates along the edges that are incident to node $i$. In other words, the matching rates satisfy the following conservation equation:

$$ \sum_{k \in E_i} \mu_k = \lambda_i, \quad i \in V, $$

where $E_i \subseteq E$ is the set of edges that are incident to node $i$. In matrix form, this equation rewrites $A\mu = \lambda$, where $A$ is the incidence matrix of the compatibility graph $G$. The solution set of this conservation equation is related to the structure of the graph $G$ via the linear application $y \in \mathbb{R}^m \mapsto Ay \in \mathbb{R}^n$, where $n$ is the number of nodes (or classes), and $m$ is the number of edges. We say that the graph $G$ is surjective (resp. injective, bijective) if the linear application $y \in \mathbb{R}^m \mapsto Ay \in \mathbb{R}^n$ is surjective (resp. injective, bijective), and we give simple equivalent conditions in terms of the graph structure (Definitions 3.1–3.4 and Proposition 3.5). Our main contributions are threefold, and all rely on these definitions.

We first prove that there exists a direct relation between the form of the solution set of the conservation equation, the structure of the compatibility graph, and the existence of a
(non-Poisson) arrival rates in a second-level model with a compatibility graph $G' = (E, E')$
(the nodes of the second-level model are the edges of $G$).

From a broader perspective, these problems can be viewed through two complementary lenses. The first, inspired by queueing theory, focuses on stability and delay. The second, rooted in linear optimization seeks to maximize reward or minimize regret with respect to an optimal solution. As we will see, the link between these two questions is the polytope defined by the non-negativity constraints. The main goal of this paper is to bridge these perspectives by adopting a “polytope perspective” on matching models.

## 1.2 Contributions.

The foundation of our approach is the conservation equation: any stable policy must satisfy $A\mu = \lambda$, where $A$ is the incidence matrix of the compatibility graph $G$. The properties of the linear mapping $\mu \mapsto A\mu$, particularly injectivity and surjectivity, are shown to be fundamentally linked to the behavior of matching models. We establish precise connections between these linear-algebraic properties and the structure of the underlying graph (Definitions 2–5 and Proposition 6). With some abuse of language, we say that a graph inherits a property, like bijectivity, injectivity, or surjectivity, if the associated linear map does; for example, $G$ is referred to as bijective if $\mu \mapsto A\mu$ is bijective. Building on these concepts, our main contributions are as follows.

First, we connect stability and the conservation equation: There exists a policy $\Phi$ such that the matching model $(G, \lambda, \Phi)$ is stable) if and only if the graph $G$ is surjective (Proposition 7) and the conservation equation has a solution with positive coordinates (Proposition 8). While equivalent results exist, our formulation provides a direct, intuitive, method to verify stabilizability, in polynomial time with respect to the number of classes and edges.

Second, we describe the solutions to the conservation equation, that is, the set $\Pi$ of vectors $\mu \in \mathbb{R}^m$ such that $A\mu = \lambda$ (see (16) in Section 5.1). When $G$ is bijective, we provide a closed-form expression of the unique solution (Proposition 9). When $G$ is surjective-only, we give a parametric expression for $\Pi$ (Proposition 10 and Definition 11) and characterize the polytope $\Pi_{\ge 0}$ of non-negative solutions. We show that the vertices of $\Pi_{\ge 0}$, i.e., its extreme points, correspond to injective solutions in the sense that the subgraph restricted to their support is injective (Proposition 13). Moreover, we show that the vertices are bijective with probability 1 when the vector $\lambda$ is sampled randomly from a reasonable distribution (Proposition 14).

Third, we apply these results to the linear optimization of $\mu$, which for a stable policy amounts to achieving a vertex of $\Pi_{\ge 0}$ (Propositions 15 and 16). If the target vertex is bijective, we propose an explicit optimal policy that attains it (Proposition 17). In contrast, when the vertex is injective-only, a strong trade-off emerges between regret with respect to the optimal solution and delay (Proposition 19). Motivated by this case, we introduce a sequence of policies that provably achieve arbitrarily small regret, at the cost of increasing delay (Proposition 18). While our bijective vertex results align with independently established findings in recent literature, our analysis and guarantees for the injective-only case are, to our knowledge, novel.

At a high level, all the optimizing policies we consider share a common recipe: start from a simple base policy designed for stability, and then adapt its parameters to be “vertex-aware”. While this insight may appear straightforward, it is highly effective in practice, especially for numerical evaluation. Building on this, we developed a modular simulation engine that enables easy integration of existing policies, their modification, and the creation of new heuristics. This flexible framework has been instrumental in validating our theoretical
stable policy. More specifically, we prove that a compatibility graph $G$ is stabilizable (in the sense that there exist a vector $\lambda$ and a policy $\Phi$ such that the matching model $(G, \lambda, \Phi)$ is stable) if and only if the graph $G$ is surjective (Proposition 3.6). We then prove that a matching problem $(G, \lambda)$ is stabilizable (in the sense that there exists a policy $\Phi$ such that the matching model $(G, \lambda, \Phi)$ is stable) if and only if the conservation equation has a solution with positive coordinates (Proposition 3.7). In particular, this allows us to verify stabilizability in a time that is polynomial in the number of classes and edges.

We next describe the affine space of solutions of the conservation equation and the convex polytope of solutions with non-negative coordinates. When this convex polytope is reduced to a single point, we derive a closed-form expression for the solution (Proposition 4.1). When this convex polytope is not reduced to a single point, we characterize its vertices, again using the graph structure. We prove in particular that a non-negative solution of the conservation equation is a vertex of the convex polytope if and only if the subgraph restricted to the support of this vector is injective (Proposition 5.6).

Lastly, we investigate which parts of the polytope can be achieved by a stable policy. We first focus on greedy policies, that is, policies that never postpone a feasible match. We show that greedy policies are limited to the interior of the polytope and that in general, the inclusion is strict (Propositions 6.2, 6.5, 6.7, and 6.8). In contrast, we conjecture that non-greedy policies can potentially reach any point within the interior of this polytope (Conjecture 6.12 and Corollary 6.14). Additionally, depending on the bijectivity of subgraphs of $G$, these policies can also reach parts or the entirety of the polytope's boundary (Proposition 6.11 and Conjecture 6.12). To support our conjectures, we have conducted simulations that provide empirical evidence.

## 1.3 State of the art

We now review the relevant work related to (static or dynamic) matching problems.

### Non-bipartite or general stochastic matching

Our work is part of a broader research effort on the stochastic matching model that was briefly discussed earlier and will be described in details in Section 2 [5, 6, 12, 15, 22, 26, 28]. Among these works, the following are particularly relevant because directly related to our results on stability. The paper [26] is the earliest work on this matching model. It derives necessary and sufficient stability conditions that are instrumental in several of our results, in particular Propositions 3.6 and 3.7. This work also proves that the *match-the-longest* policy is maximally stable (in the sense that it always leads to stability whenever the matching problem $(G, \lambda)$ is stabilizable), a result that is also applied in Proposition 3.7. The papers [15, 28] focus on the *first-come-first-matched* policy. In particular, [28] proves that the first-come-first-matched policy is maximally stable, and [15] provides a new sufficient stability condition we prove to be also necessary in Proposition 3.7.

Other variants of the model were studied recently, and an interesting future work would consist of generalizing our results to these variants. In particular, the paper [22] considers item abandonment, the paper [6] considers graphs with self-loops, and the papers [21, 29, 31] allow matches not limited to two items by replacing the graph with a hypergraph.

The recent paper [5] is perhaps the closest to ours, and we provide a detailed discussion to highlight the relation with our paper. The first statement in [5, Theorem 1] is synonym to the equivalence of statements (ii) and (iii) in Proposition 3.7. Our proof is significantly shorter because it relies more heavily on existing results. Our observation at the beginning
results through extensive simulations, where our policies are systematically compared against state-of-the-art alternatives.

Finally, we outline possible extensions of our work. Through a convexity argument, we demonstrate that it is feasible to optimize nonlinear functions of $\mu$: specifically, any $\mu^*$ in the interior of $\Pi_{\ge 0}$ can be achieved by a stable policy (Propositions 20 and 21). We further explore the optimization of $\mu$ with the additional constraint of using a *greedy* policy (Propositions 23 and 24 and Conjecture 25), present an extension of our model that accommodates arbitrary hypergraphs, allowing for the systematic discard of under-demanded items.

Note that this paper builds upon the original results reported in [14] as a preprint. The overlapping content reflects the continuity and development of our research, with the current manuscript providing a more comprehensive and peer-reviewed presentation.

## 1.3 State of the art.

We now review the relevant work related to (static or dynamic) matching problems.

### Non-bipartite or general stochastic matching.

Our work is part of a broader research effort on the stochastic matching model that was briefly discussed earlier and will be described in details in Section 2, see [5, 6, 12, 16, 26, 34, 36]. Among these works, the following are particularly relevant because directly related to our results on stability. The paper of [34] is the earliest work on this matching model. It derives necessary and sufficient stability conditions that are instrumental in several of our results, in particular Propositions 7 and 8. This work also proves that the Match-the-Longest (ML) policy is maximally stable (in the sense that it always leads to stability whenever the matching problem $(G, \lambda)$ is stabilizable), a result that is also applied in Proposition 8. [16] and [36] focus on the First-Come-First-Match (FCFM) policy. In particular, [36] proves that the FCFM policy is maximally stable, and [16] provides a new sufficient stability condition we prove to be also necessary in Proposition 8.

The recent work of [5] is perhaps the closest to ours, so we provide a detailed discussion to highlight the relation with our paper. The first statement of [5, Theorem 1] is synonym to the equivalence of statements ii and iii in Proposition 8. Our proof is significantly shorter because it relies more heavily on existing results. Our observation at the beginning of Section 4 that the conservation equation has a unique solution if and only if the graph is bijective (and not surjective-only) summarizes [5, Theorem 3]. Some formulas derived in [5, Section 9] are special cases of the formulas derived in Proposition 9. The non-bipartite matching model in [5] is slightly more general because it considers graphs with self-loops, that is, an edge can have identical endpoints, and this paper also considers the bipartite model that will be discussed in the next paragraph. However, [5] does not adopt the polytope approach that allows us to derive the necessary *and sufficient* conditions of Sections 4–6. Furthermore, although we decided to focus on nonbipartite matching models to alleviate the discussion, the general approach we develop in Section 3 equally applies to bipartite graphs and can be used to derive results for bipartite matching model such as those studied in [5].

Other variants of the model were studied recently. In particular, [26] consider item abandonment, [6] consider graphs with self-loops, and [24], [37], [30], [23], [41], and [39] allow matches not limited to two items by replacing the graph with a hypergraph, which is also called multi-way matching in the literature. The generalization of our work to multi-way matching will be discussed in Section 8.3.
of Section 4 that the conservation equation has a unique solution if and only if the graph is bijective (and not surjective-only) summarizes [5, Theorem 3]. Some formulas derived in [5, Section 9] are special cases of the formulas derived in Proposition 4.1. The non-bipartite matching model in [5] is slightly more general because it considers graphs with self-loops, that is, an edge can have identical endpoints, but this paper does not adopt the mixed graph-theory and linear-algebra approach that supports most of our results.

## Bipartite stochastic matching

To the best of our knowledge, the first example of a stochastic matching model with an infinite time horizon in the literature, which predated the model that we consider, is the bipartite matching model introduced in [13] and studied in [1, 2, 3, 9, 10, 11, 16]. In this model, the compatibility graph is bipartite, with two parts that correspond to supply and demand items, respectively. This bipartite model differs from ours by its arrival process: time is slotted and, during each time slot, one demand item and one supply item arrive. Several works have made contributions about stability [2, 9] and matching rates [2], and they obtained results similar to those derived in the literature on our model. The bipartite nature of the graph simplifies some calculations, for instance by allowing the application of flow-maximization algorithms to calculate optimal matching rates.

## Static and fractional matching

The static matching problem, in which the nodes of the graph represent items (rather than classes), has been extensively studied in mathematics, computer science, and economy [25]. Although the questions raised in static and dynamic matching are often different, the conservation equation that we obtain is reminiscent of several results in static matching. For example, finding a maximum-cardinality matching in the graph $G$ (that is, a maximum-cardinality set of edges without common endpoints) is equivalent to finding integers $\mu_k \in \{0, 1\}$ for each edge $k \in E$ that maximize $\sum_{k \in E} \mu_k$ while satisfying the conservation equation with $\lambda_i = 1$ for each $i \in V$. The relaxation of this integer linear program leads to the so-called fractional matching problem, which has been studied in the literature [25, Section 7.2]. Therefore, the fractional matching polytope defined in [25, Section 7.5] is a special case of the convex polytope that we consider in Section 5.2, and our characterization of this convex polytope is a natural generalization of existing characterizations of the fractional polytope <fnref n="3" />.

## 1.4 Outline

The remainder of the paper is organized as follows. **Section 2** gives a formal definition of the model. **Section 3** introduces the conservation equation and defines the notions of surjectivity, injectivity, and bijectivity for a graph that will be instrumental throughout the paper. We use these definitions to formulate new necessary and sufficient stability conditions. In particular, we show that stability requires the compatibility graph to be surjective (that is, either bijective or surjective-only). In **Section 4**, we focus on bijective graphs and give a closed-form expression of the unique solution of the conservation equation. **Section 5** characterizes the solution set of the conservation equation for surjective-only graphs. Lastly,

<footnote n="3">³ The fractional matching polytope is actually defined using non-strict inequalities rather than equalities. However, one can verify that these two convex polytopes have the same non-zero vertices.</footnote>
**Reward maximization.**

A series of papers on multi-way ([37, 41, 30, 23]) and two-way matching ([29]) focus on maximizing edge-weighted rewards. These works are closely related to our analysis in Section 6, which addresses the same theme. For a thorough discussion, we postpone direct comparison until Section 6.4, following the presentation of our main findings on reward optimization.

**Bipartite stochastic matching.**

While our paper focuses on non-bipartite graphs, there is also an extensive literature on the bipartite case. A major complication with bipartite stochastic matching is that, in general, the model is unstable in the sense that the underlying Markov chain is at best null-recurrent, or transient, but never positive recurrent. To the best of our knowledge, the first example in the literature of a stochastic matching model with an infinite time horizon, which predated the model we consider, is the bipartite matching model introduced in [13], and later studied in by [1, 2, 9, 10, 11, 17]. In this model, the compatibility graph is bipartite, with two parts that correspond to supply and demand, respectively. Stabilizability is enforced by making a synchronization assumption: time is slotted and, during each time slot, one demand item and one supply item arrive. [2] and [9] obtained results on stability and [2] focused on matching rates; these results are similar to those described above regarding the literature on non-bipartite matching. Another work in the literature has obtained a stabilizable matching model by allowing reneging or abandonment [3]. In general, the bipartite nature of the graph simplifies some calculations, for instance by allowing the application of flow-maximization algorithms to calculate optimal matching rates.

**Static and fractional matching.**

The static matching problem, in which the nodes of the graph represent items (rather than classes), has been extensively studied in mathematics, computer science, and economy, see [33]. Although the questions raised in static and dynamic matching are often different, the conservation equation that we obtain is reminiscent of several results on static matching. For example, finding a maximum-cardinality matching in the graph $G$ (that is, a maximum-cardinality set of edges without common endpoints) is equivalent to finding integers $\mu_k \in \{0, 1\}$ for each edge $k \in E$ that maximize $\sum_{k \in E} \mu_k$ while satisfying the conservation equation with $\lambda_i = 1$ for each $i \in V$. The relaxation of this integer linear program leads to the so-called fractional matching problem, which has been studied in the literature, see [33, Section 7.2]. Therefore, the fractional matching polytope defined by [33, Section 7.5] is a special case of the convex polytope that we consider in Section 5.2, and our characterization of this convex polytope is a natural generalization of existing characterizations of the fractional polytope $^3$.

**1.4 Companion package**

This paper is supported by the Python package *Stochastic Matching* by [35], which provides an open-source implementation of all the concepts and results developed here, together with

<footnote n="3">³ The fractional matching polytope is actually defined using non-strict inequalities rather than equalities. However, one can verify that these two convex polytopes have the same non-zero vertices.</footnote>
in **Section 6**, we focus on the set of matching rates that are effectively achievable under a stable matching policy.

## 2 Stochastic dynamic matching

We consider a stochastic dynamic matching system in which items arrive at random times to be matched with other items. Each incoming item may be matched with any unmatched item of a compatible class; in this case, both items disappear immediately. Unmatched items are gathered in a waiting queue. In this paper, such a stochastic dynamic matching system will be described by a triplet $(G, \lambda, \Phi)$, where $G$ is the *compatibility graph*, $\lambda$ is the vector of *arrival rates*, and $\Phi$ is the *matching policy*. We now review each component in details. To facilitate reference and understanding, we provide a summary of our notation in Table 1.

### 2.1 Compatibility graph

Compatibility constraints between items are described by a graph $G = (V, E)$, called the *compatibility graph* of the model, which is simple (undirected and without self-loop). The number of nodes is represented by $n$, while $m$ denotes the number of edges.

We use $V = \{v_1, v_2, \dots, v_n\}$ to denote the set of nodes, where each node corresponds to a class in the matching model. In cases where there is no confusion, we may refer to a class $v_i$ simply by its index $i$. Following the intuition conveyed in Figure 1, we will use the terms “class $i$” and “queue $i$” interchangeably, and refer for instance to the number of unmatched class-$i$ items as the size of queue $i$; this is a convenience of terminology, and this does not prevent matching decisions from being based on additional information, such as the arrival order of items of different classes (see Section 2.3 for more details on matching decisions).

The set of edges is denoted by $E = \{e_1, e_2, \dots, e_m\}$. These edges represent compatibility constraints between item classes, in the sense that a class-$i$ item and a class-$j$ item can be matched with one another if and only if they are adjacent, that is, if there is an edge with endpoints $i$ and $j$. When there is no ambiguity, we may refer to an edge $e_k \in E$ with endpoints $i, j \in V$ by its index $k$ or by its set of endpoints $\{i, j\}$. In Figure 1 for instance, there are four item classes numbered from 1 to 4. Classes 2 and 3 are compatible with all classes, but classes 1 and 4 are only compatible with classes 2 and 3. The absence of self-loop means that an item of a given class cannot be matched with other items of the same class.

Lastly, we let $\mathbb{I}$ denote the family of independent sets of the compatibility graph $G$, where an independent set of $G$ is a non-empty set of nodes that are pairwise non-adjacent. The family of independent sets in the compatibility graph of Figure 1 is $\mathbb{I} = \{\{1\}, \{2\}, \{3\}, \{4\}, \{1, 4\}\}$.

### 2.2 Arrival process

Class-$i$ items arrive according to an independent Poisson process with rate $\lambda_i > 0$, for each $i \in V$. The vector of arrival rates is denoted by $\lambda = (\lambda_1, \lambda_2, \dots, \lambda_n) \in \mathbb{R}_{>0}^n$. Scaling all coordinates of $\lambda$ by the same positive constant is equivalent to changing the time unit, so we can renormalize $\lambda$ without changing the dynamics. For example, we will sometimes use the *unit* normalization, in which $\sum_{i \in V} \lambda_i = 1$. We also let $I = (I_t, t \in \mathbb{N})$ denote the sequence of independent and identically distributed (i.i.d.) item classes, so that $I_t$ is the class of the $(t+1)$-th item, equal to $i$ with probability $\lambda_i/(\sum_{j \in V} \lambda_j)$, for each $t \in \mathbb{N}$. The couple $(G, \lambda)$ is called a *matching problem* or simply a *problem*. Occasionally, when we need to specify the sequence of incoming items and not merely its distribution, we will also refer to the couple $(G, I)$ as a (matching) problem.
additional tools for experimentation. The package is freely available on GitHub and PyPI, and can be readily installed on any recent Python distribution<fnref n="4" />.

The package is designed to remain flexible for extensions. Its main features include:

- Support for both simple graphs and hypergraphs, created either manually or through a built-in graph library, making it possible to test theoretical results on arbitrary structures;

- Automated categorization of graphs G (e.g., surjective, injective) and verification of the stabilizability of any instance $(G, \lambda)$;

- Computation of the solution space $\Pi$ and of the vertices of $\Pi_{\ge 0}$, including the reward-optimal vertex;

- Visualization tools that produce graph-based representations of $\Pi$, vertices, and policy matching rates;

- A scalable simulation framework for evaluating the long-term performance of arbitrary policies (up to $10^{10}$ time steps), together with a curated library of policy implementations that includes the approaches proposed in this paper and state-of-the-art baselines.

The package builds upon SciPy for linear algebra and optimization routines, VisJS Network for graph visualization, and Numba for efficient simulation.

While the package is designed as a standalone tool that can serve a broader community working on stochastic matching and related problems, a dedicated section of its documentation accompanies this article by reproducing all the results presented here and presenting additional examples<fnref n="5" />. We believe that this package constitutes a valuable contribution on its own, as it provides a foundation for future experimental and theoretical work.

## 1.5 Outline.

The remainder of the paper is organized as follows. **Section 2** gives a formal definition of the model. **Section 3** introduces the conservation equation and defines the notions of surjectivity, injectivity, and bijectivity for a graph. We use these definitions to formulate new necessary and sufficient stability conditions. In particular, we show that stability requires the compatibility graph to be surjective (that is, either bijective or surjective-only). In **Section 4**, we focus on bijective graphs and give a closed-form expression of the unique solution to the conservation equation. **Section 5** characterizes the solution set of the conservation equation for surjective-only graphs. **Section 6** focuses on the linear optimization of the matching rates (that is, optimizing a linear combination of the matching rates) under a stable policy. **Section 7** focuses on computing the numerical performance of policies through simulations. Lastly, in **Section 8**, we consider several extensions of our framework: non-linear optimization, restriction to greedy policies, and hypergraph matchings.

### 2 Stochastic dynamic matching.

We consider the following model: items arrive at random times to be matched with other items; each incoming item may be paired with any unmatched item of a compatible class. When a match occurs, the involved items disappear immediately, while unmatched items wait in a queue. In this paper, such a stochastic dynamic matching system is described by a triplet $(G, \lambda, \Phi)$, where G is the compatibility graph, $\lambda$ the vector of arrival rates, and $\Phi$ the matching policy.

<footnote n="4">⁴ For instance, `pip install stochastic-matching` or `uv add stochastic-matching`.</footnote>

<footnote n="5">⁵ https://balouf.github.io/stochastic_matchring/companion/index.html</footnote>
## 2.3 Policy and matching dynamics

Most of the paper will focus on deterministic size-based policies, that is, policies whereby matching decisions are deterministic functions of the queue size vectors. However, as we will see at the end of this section, our results also apply to a more general definition of a policy. Throughout the paper, we assume that the system is initially empty, meaning that it starts with no unmatched item.

### 2.3.1 Size-based policies

A (deterministic) size-based matching policy is defined formally as a function $\Phi: Q \times V \to V \cup \{\perp\}$, where $Q$ is an infinite subset of $\mathbb{N}^n$ that contains the reachable states of the system. We will delve into further discussion on $Q$ in Sections 2.3.2 and 2.3.3. For each $q \in Q$ and $i \in V$, an incoming class-$i$ item that finds the system in state $q$ is matched with an item of class $\Phi(q, i)$ if $\Phi(q, i) \in V$ and is added to the class-$i$ queue if $\Phi(q, i) = \perp$. The matching policy is assumed to be adapted to the compatibility graph $G$ in the sense that

$$ \Phi(q, i) \in \{j \in V_i : q_j \ge 1\} \cup \{\perp\}, \quad q \in Q, \quad i \in V. \qquad (1) $$

The system dynamics is described by a Markov chain $Q = (Q_t, t \in \mathbb{N})$, called the queue-size process, where $Q_t = (Q_{t,1}, Q_{t,2}, \dots, Q_{t,n})$ is an $n$-dimensional vector giving the number of unmatched items of each class right after the arrival of the $t$-th item, for each $t \in \mathbb{N}$, with the assumption that the system is initially empty, that is, $Q_0 = 0$. The system dynamics satisfies the recursion

$$ Q_{t+1} = \begin{cases} Q_t + 1_{I_t} & \text{if } J_t = \perp, \\ Q_t - 1_{J_t} & \text{if } J_t \neq \perp, \end{cases} \qquad (2) $$

where $J_{t+1} = \Phi(Q_t, I_t)$ for each $t \in \mathbb{N}$, and $1_i$ is the $n$-dimensional vector with one in coordinate $i$ and zero elsewhere, for each $i \in V$. We assume that the policy $\Phi$ is such that the Markov chain $Q$ has state space $Q$ and is irreducible. By unfolding the recursion (2), we obtain that, for each $t \in \mathbb{N}$,

$$ Q_{t,i} = L_{t,i} - \sum_{k \in E_i} M_{t,k}, \quad t \in \mathbb{N}, \quad i \in V, \qquad (3) $$

where $E_i \subseteq E$ is the set of edges that are incident to node $i$ in the graph $G$, for each $i \in V$, $L_{t,i}$ is the number of class-$i$ items among the first $t$ arrivals, for each $t \in \mathbb{N}$ and $i \in V$, and $M_{t,k}$ is the number of times that classes $i$ and $j$ are matched over the first $t$ arrivals, for each $t \in \mathbb{N}$ and $\{i, j\} = e_k \in E$:

$$ L_{t,i} = \sum_{s=0}^{t-1} 1_{\{I_s=i\}}, \quad t \in \mathbb{N}, \quad i \in V, \qquad (4) $$

$$ M_{t,k} = \sum_{s=0}^{t-1} 1_{\{I_s, J_s\}=e_k}, \quad t \in \mathbb{N}, \quad k \in E, \qquad (5) $$

with the convention that the sums are zero if $t = 0$. The triplet $(G, \lambda, \Phi)$ is called a matching model, or simply a model. Occasionally, when specifying the sequence of incoming item classes is useful, we will also refer to the triplet $(G, I, \Phi)$ as a (matching) model.
The remainder of this section formalizes the model in detail. Our goal here is to state the model precisely so that the paper remains both rigorous and self-contained. Readers already familiar with queueing theory and matching systems may safely skip ahead to Section 3, as the definitions and notations introduced here do not extend beyond the standard framework.

For convenience, notation is summarized in Table 1.

## 2.1 Compatibility graph.

Compatibility constraints between items are described by a graph $G = (V, E)$, called the compatibility graph of the model, which is simple (undirected and without self-loop). The number of nodes is represented by $n$, while $m$ denotes the number of edges.

We use $V = \{v_1, v_2, \dots, v_n\}$ to denote the set of nodes, where each node corresponds to a class in the matching model. In cases where there is no confusion, we may refer to a class $v_i$ simply by its index $i$. Following the intuition conveyed in Figure 1, we will use the terms “class $i$” and “queue $i$” interchangeably, and refer for instance to the number of unmatched class-$i$ items as the size of queue $i$; this is a convenience of terminology, and this does not preclude the matching policy from using information not captured by this state representation, such as the arrival order of items of different classes (see Section 2.3 for more details).

The set of edges is denoted by $E = \{e_1, e_2, \dots, e_m\}$. These edges represent compatibility constraints between item classes, in the sense that a class-$i$ item and a class-$j$ item can be matched with one another if and only if their classes are adjacent, that is, if there is an edge with endpoints $i$ and $j$. When there is no ambiguity, we may refer to an edge $e_k \in E$ with endpoints $i, j \in V$ by its index $k$ or its set $\{i, j\}$ of endpoints. In Figure 1 for instance, there are four item classes numbered from 1 to 4. Classes 2 and 3 are compatible with all classes, but classes 1 and 4 are only compatible with classes 2 and 3. The absence of self-loop means that an item of a given class cannot be matched with other items of the same class.

Lastly, we let $\mathbb{I}$ denote the family of independent sets of the compatibility graph $G$, where an independent set of $G$ is a non-empty set of nodes that are pairwise non-adjacent. The family of independent sets in the compatibility graph of Figure 1 is $\mathbb{I} = \{\{1\}, \{2\}, \{3\}, \{4\}, \{1, 4\}\}$.

## 2.2 Arrival process.

Class-$i$ items arrive according to an independent Poisson process with rate $\lambda_i > 0$, for each $i \in V$. The vector of arrival rates is denoted by $\boldsymbol{\lambda} = (\lambda_1, \lambda_2, \dots, \lambda_n) \in \mathbb{R}_{>0}^n$. Scaling all coordinates of $\boldsymbol{\lambda}$ by the same positive constant is equivalent to changing the time unit, so we can renormalize $\boldsymbol{\lambda}$ without changing the dynamics. For example, we will sometimes use the *unit* normalization, in which $\sum_{i \in V} \lambda_i = 1$. We also let $I = (I_t, t \in \mathbb{N})$ denote the sequence of independent and identically distributed (i.i.d.) item classes, so that $I_t$ is the class of the $(t+1)$-th item, equal to $i$ with probability $\lambda_i/(\sum_{j \in V} \lambda_j)$, for each $t \in \mathbb{N}$. The couple $(G, \boldsymbol{\lambda})$ is called a *matching problem* or simply a *problem*. Occasionally, when we need to specify the sequence of incoming items and not merely its distribution, we will also refer to the couple $(G, I)$ as a (matching) problem.

## 2.3 Policy and matching dynamics.

Most of the paper focuses on deterministic size-based policies, that is, policies whereby matching decisions are deterministic functions of the queue-size vector. However, as we will briefly explain at the end of this section (and discuss in more details in the supplementary
### 2.3.2 Greedy policies

A policy $\Phi$ is called greedy if an incoming item is matched whenever possible, that is, if there is an unmatched item that is compatible. More formally, the policy $\Phi$ is greedy if

$$ \Phi(q, i) \neq \perp \text{ for each } (q, i) \in \mathcal{Q} \times V \text{ such that } \{j \in V_i : q_j \geq 1\} \neq \emptyset. \qquad (6) $$

Equivalently, a policy $\Phi$ is greedy if the set of unmatched item classes under this policy is an independent set of the compatibility graph, meaning that the state space $\mathcal{Q}$ of the queue-size process is equal to

$$ \mathcal{Q}_G = \{q \in \mathbb{N}^n : q_i q_j = 0 \text{ for each } i, j \in V \text{ such that } \{i, j\} \in E\}. \qquad (7) $$

The following greedy policies will be instrumental in Sections 3 and 6:

- **Match-the-longest:** For each $(q, i) \in \mathcal{Q} \times V$ such that $\sum_{j \in V_i} q_j \geq 1$, we choose $\Phi(q, i) \in \arg\max_{j \in V_i}(q_j)$ (ties are broken arbitrarily). This policy was considered in [26, 6, 22, 5].

- **Edge-priority:** This policy selects matches according to a priority order defined on the edges. More specifically, if we let $\prec$ denote a strict total order on the set $E$ of edges, we let $\Phi(q, i) = \arg\min_{j \in V_i: q_j \geq 1}(\{i, j\})$ for each $(q, i) \in \mathcal{Q} \times V$ such that $\sum_{j \in V_i} q_j \geq 1$, where the $\arg\min$ is to be understood over the ordered set $(E, \prec)$. This definition remains valid if $\prec$ is a partial order compatible with the possible inputs of $\arg\min$, i.e. if all pairs of edges that are incident to the same node and are not part of a triangle are comparable$^4$.

### 2.3.3 Non-greedy policies

The state space $\mathcal{Q}$ under non-greedy policies is a strict superset of the set $\mathcal{Q}_G$ defined in (7). In Section 6, non-greedy policies will be obtained by modifying greedy policies as follows:

- **Filtering:** Given a subset $\underline{E} \subset E$ of edges, replace $V_i$ with $\underline{V}_i = \{j \in V_i : \{i, j\} \in \underline{E}\}$ in the definition (1) of $\Phi$. Intuitively, we eliminate the edges of $E \setminus \underline{E}$ and follow a (greedy or non-greedy) policy on the subgraph $\underline{G} = (V, \underline{E})$.

- **Semi-filtering:** We consider a modified variant of filtering policies in which the subset $\underline{E}$ of edges depends on the system state $q$ at the arrival time. Examples of semi-filtering policies will be given in Section 6.2.

For instance, under the filtering variant of the match-the-longest policy that eliminates edge $\{2, 3\}$ in the matching problem of Figure 1, an incoming class-3 item is either matched with a class-4 item or added to the queue of class 3 (but it is not matched with a class-2 item).

► **Remark 2.1 (Random policies).** Our choice of notation assumes that the policy is deterministic. A random (size-based) policy $\Phi$ can be defined as a function $\Phi: \mathcal{Q} \times V \times (V \cup \{\perp\}) \to [0, 1]$ such that, for each $t \in \mathbb{N}$, $J_t$ is sampled according to the distribution $\Phi(q, i, \cdot)$ given that $Q_t = q$ and $I_t = i$. Saying that the policy is adapted to the compatibility graph $G$ is then equivalent to saying that, for each $q \in \mathcal{Q}$ and $i \in V$, the support of $\Phi(q, i, \cdot)$ is included into $\{j \in V_i : q_j \geq 1\} \cup \{\perp\}$. The policy is greedy if $\Phi(q, i, \perp) = 0$ for each $(q, i) \in \mathcal{Q} \times V$ such that $\{j \in V_i : q_j \geq 1\} \neq \emptyset$ or, equivalently, if $\mathcal{Q} = \mathcal{Q}_G$.

### 2.3.4 Other policies

Although deterministic size-based policies are notationwise convenient, our results apply to a broader family of policies that are either random or require a more complex state descriptor,

<footnote n="4">⁴ If three classes form a triangle in the compatibility graph, at most one of them can be non-empty under a greedy policy, so at most one edge of the triangle can be in the input of $\arg\min$.</footnote>
material), our results also apply to a more general definition of a policy. Throughout the paper, we assume that the system is initially empty, meaning that it starts with no unmatched item.

### 2.3.1 Deterministic size-based policies.

A (deterministic) size-based matching policy is defined formally as a function $\Phi: Q \times V \to V \cup \{\perp\}$, where $Q$ is an infinite subset of $\mathbb{N}^n$ that contains the reachable states of the system. In-depth discussion on $Q$ will come in Sections 2.3.2 and 2.3.3. For each $q \in Q$ and $i \in V$, an incoming class-$i$ item that finds the system in state $q$ is matched with an item of class $\Phi(q, i)$ if $\Phi(q, i) \in V$ and is added to class-$i$ queue if $\Phi(q, i) = \perp$. The matching policy is assumed to be adapted to the compatibility graph $G$ in the sense that

$$ \Phi(q, i) \in \{j \in V_i : q_j \ge 1\} \cup \{\perp\}, \quad q \in Q, \quad i \in V, \qquad (1) $$

where $V_i$ is the neighbor set of node $i$ in $G$. The system dynamics are described by a Markov chain $Q = (Q_t, t \in \mathbb{N})$, called the *queue-size process*. For each $t \in \mathbb{N}$, $Q_t = (Q_{t,1}, Q_{t,2}, \dots, Q_{t,n})$ is an $n$-dimensional vector giving the number of unmatched items of each class right after the arrival of the $t$-th item, with the assumption that the system is initially empty, that is, $Q_0 = 0$. The system dynamics satisfy the recursion

$$ Q_{t+1} = \begin{cases} Q_t + 1_{I_t} & \text{if } J_t = \perp, \\ Q_t - 1_{J_t} & \text{if } J_t \neq \perp, \end{cases} \qquad (2) $$

where $J_t = \Phi(Q_t, I_t)$ for each $t \in \mathbb{N}$, and $1_i$ is the $n$-dimensional vector with one in coordinate $i$ and zero elsewhere, for each $i \in V$. We assume that the policy $\Phi$ is such that the Markov chain $Q$ has state space $Q$ and is irreducible. By unfolding the recursion (2), we obtain that, for each $t \in \mathbb{N}$,

$$ Q_{t,i} = L_{t,i} - \sum_{k \in E_i} M_{t,k}, \quad t \in \mathbb{N}, \quad i \in V, \qquad (3) $$

where $E_i \subseteq E$ is the set of edges that are incident to node $i$ in the graph $G$, for each $i \in V$, $L_{t,i}$ is the number of class-$i$ items among the first $t$ arrivals, for each $t \in \mathbb{N}$ and $i \in V$, and $M_{t,k}$ is the number of times that classes $i$ and $j$ are matched over the first $t$ arrivals, for each $t \in \mathbb{N}$ and $\{i, j\} = e_k \in E$:

$$ L_{t,i} = \sum_{s=0}^{t-1} 1_{\{I_s=i\}}, \quad t \in \mathbb{N}, \quad i \in V, \qquad (4) $$

$$ M_{t,k} = \sum_{s=0}^{t-1} 1_{\{I_s, J_s\}=e_k}, \quad t \in \mathbb{N}, \quad k \in E, \qquad (5) $$

with the convention that the sums are zero if $t=0$. The triplet $(G, \lambda, \Phi)$ is called a *matching model*, or simply a *model*. Occasionally, when specifying the sequence of incoming item classes is useful, we will also refer to the triplet $(G, I, \Phi)$ as a (matching) model.

### 2.3.2 Greedy policies.

A policy $\Phi$ is called *greedy* if an incoming item is matched whenever possible, that is, if there is an unmatched item that is compatible. More formally, the policy $\Phi$ is greedy if

$$ \Phi(q, i) \neq \perp \text{ for each } (q, i) \in Q \times V \text{ such that } \{j \in V_i : q_j \ge 1\} \neq \emptyset. \qquad (6) $$
or both. We now introduce this family of policies, with the goal of being as general as possible. The remainder of Section 2.3 can be skipped by the first-time reader and referred to when necessary; in this case, $S$ can be understood as $Q$ in all definitions and results.

## Extended definition

Under this more general definition, the match-maker makes decisions based not only on the vector of queue sizes, but also (possibly) on additional information that is captured by the system state. The state space is a couple $(S, |\cdot|)$, where $S$ is a countably infinite set and $|\cdot|: S \to \mathbb{N}^n$ is a function that maps any state $s \in S$ to the vector giving the number of unmatched items of each class in that state, denoted by $|s| = (|s|_1, |s|_2, \dots, |s|_n)$. The existence of the function $|\cdot|$ guarantees that the system state contains enough information to retrieve the number of unmatched items of each class, which is a classical assumption in queueing theory (see for instance [24, Section 3.2]). We assume that there exists a unique state $s \in S$ such that $|s| = 0$. This state is called the empty state and denoted by $\emptyset$. This assumption guarantees that the intuitive notion of system stability will be captured by the positive recurrence of the Markov chain describing the evolution of the system state<fnref n="5" />.

The policy is now a function $\Phi: S \times V \times (V \cup \{\perp\}) \times S \to [0, 1]$ such that $\Phi(s, i, j, s')$ is the conditional probability that, given an incoming class-$i$ item finds the system in state $s$, the matching decision is $j$ and the new state is $s'$. More formally, the dynamics are described by a Markov chain $((S_t, I_t, J_t), t \in \mathbb{N})$, where $I = (I_t, t \in \mathbb{N})$ is the sequence of incoming item classes and, for each $t \in \mathbb{N}$, $i \in V$, $j \in V \cup \{\perp\}$, and $s, s' \in S$, we have

$$ \mathbb{P}(J_t = j, S_{t+1} = s' | S_t = s, I_t = i) = \Phi(s, i, j, s'). $$

The stochastic process $S = (S_t, t \in \mathbb{N})$ is also a Markov chain, with transition probabilities

$$ \mathbb{P}(S_{t+1} = s' | S_t = s) = \frac{\sum_{i \in V} \lambda_i \sum_{j \in V \cup \{\perp\}} \Phi(s, i, j, s')}{\sum_{i \in V} \lambda_i}, \quad t \in \mathbb{N}, \quad s, s' \in S. $$

We assume that the Markov chain $S$ has state space $S$ and is irreducible, and that $S_0 = \emptyset$. The policy is assumed to be adapted to the compatibility graph $G$ and consistent in the sense that, for each $(s, i, j, s') \in S \times V \times (V \cup \{\perp\}) \times S$, we have $\Phi(s, i, j, s') > 0$ only if

$$ j \in \{j' \in V_i : |s|_{j'} \ge 1\} \cup \{\perp\}, \quad \text{and} \quad |s'| = \begin{cases} |s| + 1_i & \text{if } j = \perp, \\ |s| - 1_j & \text{if } j \ne \perp. \end{cases} $$

Using this extended definition, the previously defined policy models can be easily expressed. For example, the matching policy $\Phi$ is called size-based if $|\cdot|$ is the identity (implying $S \subset \mathbb{N}^n$) and deterministic if, for each $s \in S$ and $i \in V$, there exists $(j, s') \in (V \cup \{\perp\}) \times S$ such that $\Phi(s, i, j, s') = 1$. The policy is called greedy if $\sum_{s' \in S} \Phi(s, i, \perp, s') = 0$ for each $(s, i) \in S \times V$ such that $\{j \in V_i : |s|_j \ge 1\} \ne \emptyset$, and non-greedy otherwise. First-come-first-matched [15, 28] is a classical example of a deterministic policy that is not size-based: its state space is a couple $(S, |\cdot|)$ where $S$ is a subset of the set of sequences $c = (c_1, c_2, \dots, c_p)$ made of a finite but arbitrarily large number $p$ of elements of $\mathcal{I}$, and $|c_i|$ is the cardinality of the

<footnote n="5">⁵ Without this assumption, one may construct two Markov chains associated with the same system, one positive recurrent and the other transient, for example if the state of the latter Markov chain embeds the time $t$. This assumption is used only in the proofs of Propositions 6.1 and A.1. In both cases, we can verify that the same conclusion holds as long as the set of states $s \in S$ such that $|s| = 0$ is finite. Assuming that this set is reduced to a singleton is merely a notational convenience.</footnote>
Equivalently, a policy $\Phi$ is greedy if the set of unmatched item classes under this policy is an independent set of the compatibility graph, meaning that the state space $\mathcal{Q}$ of the queue-size process is equal to

$$ \mathcal{Q}_G = \{q \in \mathbb{N}^n : q_i q_j = 0 \text{ for each } i, j \in V \text{ such that } \{i, j\} \in E\}. \quad (7) $$

Here are two examples of greedy matching policies that will appear later in the paper:

- **Match-the-Longest (ML):** For each $(q, i) \in \mathcal{Q} \times V$ such that $\sum_{j \in V_i} q_j \ge 1$, we choose $\Phi(q, i) \in \arg\max_{j \in V_i}(q_j)$ (ties are broken arbitrarily). This policy was considered by [34, 6, 26, 5].

- **Highest-Reward-First (HRF):** This policy selects matches according to rewards defined on edges. If $r$ denotes a vector of $\mathbb{R}^m$ (indexed by the edges) with distinct coordinates, we let $\Phi(q, i) = \arg\max_{j \in V_i: q_j \ge 1} r_{i,j}$ for each $(q, i) \in \mathcal{Q} \times V$ such that $\sum_{j \in V_i} q_j \ge 1$. This definition remains valid if the coordinates of $r$ have ties that do not impact the decision, i.e., if all pairs of edges that are incident to the same node and are not part of a triangle have distinct rewards$^6$. Note that the order induced by $r$ fully defines an HRF policy.

### 2.3.3 Non-greedy policies.

The state space $\mathcal{Q}$ under non-greedy policies is a strict superset of the set $\mathcal{Q}_G$ defined in (7). In Section 6, non-greedy policies are obtained by applying the following modifications to greedy policies:

- **Filtering:** Given a subset $E^* \subset E$ of edges, replace $V_i$ (the neighbors of node $i$) with $V_i^* = \{j \in V_i : \{i, j\} \in E^*\}$ in the definition (1) of $\Phi$. Intuitively, we eliminate the edges of $E \setminus E^*$ and follow a (greedy or non-greedy) policy on the subgraph $G^* = (V, E^*)$.

- **Semi-filtering:** We consider a variant of filtering policies in which the restriction of selecting matches from a subset $E^*$ is not always enforced. Examples of semi-filtering policies will be given in Sections 6 and 7.

### 2.3.4 Other policies.

Although our results are stated for deterministic size-based policies because they are notationally convenient, our results apply to a broader family of policies that are either random or require a more complex state descriptor, or both.

The extension to random policies is standard. A random (size-based) policy $\Phi$ can be defined as a function $\Phi: \mathcal{Q} \times V \times (V \cup \{\perp\}) \to [0, 1]$ such that, for each $t \in \mathbb{N}$, $J_t$ is sampled according to the distribution $\Phi(q, i, \cdot)$ given that $Q_t = q$ and $I_t = i$. Saying that the policy is adapted to the compatibility graph $G$ is then equivalent to saying that, for each $q \in \mathcal{Q}$ and $i \in V$, the support of $\Phi(q, i, \cdot)$ is included into $\{j \in V_i : q_j \ge 1\} \cup \{\perp\}$. The policy is greedy if $\Phi(q, i, \perp) = 0$ for each $(q, i) \in \mathcal{Q} \times V$ such that $\{j \in V_i : q_j \ge 1\} \ne \emptyset$ or, equivalently, if $\mathcal{Q} = \mathcal{Q}_G$.

An even broader set of policies that fit into our framework is described in Appendix A. In a nutshell, the extended definition of a policy starts with a pair $(S, |\cdot|)$, where $S$ is a countably infinite set and $|\cdot|: S \to \mathbb{N}^n$ is a function that maps any state $s \in S$ to the corresponding queue-size vector. The policy is then a function $\Phi: S \times V \times (V \cup \{\perp\}) \times S \to [0, 1]$ such

<footnote>$^6$ If three classes form a triangle in the compatibility graph, at most one of them can be non-empty under a greedy policy, so at most one edge of the triangle can be in the input of arg max.</footnote>
set {$q \in \{1, 2, \dots, p\} : c_q = i$}, for each $i \in \mathcal{I}$. A policy that is neither size-based nor deterministic will appear in the proof of Proposition 6.1.

The stochastic process $Q = (Q_t, t \in \mathbb{N})$ defined by $Q_t = |S_t|$ for each $t \in \mathbb{N}$ is called the *queue-size process*. This process does not satisfy the Markov property in general, but it satisfies the evolution equations (2) and (3), with $L_i = (L_{t,i}, t \in \mathbb{N})$ and $M_k = (M_{t,k}, t \in \mathbb{N})$ defined by (4) and (5) for each $i \in V$ and $k \in E$. The state space of the queue-size process is given by $Q = \{|s|, s \in S\}$. The policy is greedy if $Q = Q_G$ and non-greedy if $Q \supsetneq Q_G$, where $Q_G$ is still given by (7).

**Remark 2.2 (Arrival rates vs. arrival sequence).** We will often identify the matching model $(G, \lambda, \Phi)$ with the Markov chain $S$. This is a slight abuse of language: the triplet $(G, \lambda, \Phi)$ specifies the transition diagram of this Markov chain but, even if $\Phi$ is deterministic, characterizing its sample paths requires specifying the sequence $I$, sampled according to $\lambda = (\lambda_1, \lambda_2, \dots, \lambda_n)$. This slight abuse of language will not cause confusion when discussing stability and matching rates, but the distinction will matter in Section 6.

**Remark 2.3 (Discrete time vs. continuous time).** The discrete-time Markov chain $S$ gives the sequence of states observed by incoming items, and it was analyzed under various policies in [22, 26]. Yet in queueing theory, it is more common to consider the continuous-time Markov chain describing the system state over time. However, as observed in [15, Section 2.2.2], $S$ is the jump chain of this continuous-time Markov chain, and both Markov chains have the same stationary measures because the departure rate from each state in the continuous-time Markov chain is constant equal to $\sum_{i \in V} \lambda_i$. Therefore, our results are equally relevant to study performance metrics like the mean queue size or the mean waiting time of items.

## Equivalent policies

With our extended definition, a decision rule can be associated with an infinite number of policies. For instance, it is always possible to artificially expand the state definition, resulting in an unlimited range of policies. We define here an equivalence relation between policies that captures the intuitive concepts of *yielding identical distributions of matching decisions* (for random policies) and *making the same decisions* (for deterministic policies). This discussion will also prepare the ground for Propositions 6.4 and 6.6.

Consider a policy $\Phi_1$ adapted to a compatibility graph $G = (V, E)$, and let $(S_1, |\cdot|_1)$ denote its state space. Assume that the function $|\cdot|_1 : S_1 \to \mathbb{N}^n$ can be written as a composition of two functions, $\langle \cdot \rangle : S_1 \to S_2$ and $|\cdot|_2 : S_2 \to \mathbb{N}^n$, such that $S_2$ is the image of $S_1$ through $\langle \cdot \rangle$. Moreover, assume that there exists a policy $\Phi_2$ with state space $(S_2, |\cdot|_2)$, adapted to the graph $G$, such that for each $s_2, s'_2 \in S_2$, $i \in V$, and $j \in V \cup \{\perp\}$, we have

$$ \sum_{s'_1 \in S_1 : \langle s'_1 \rangle = s'_2} \Phi_1(s_1, i, j, s'_1) = \Phi_2(s_2, i, j, s'_2) \quad \text{for each } s_1 \in S_1 \text{ such that } \langle s_1 \rangle = s_2. \quad (8) $$

We say that $\Phi_1$ can be *reduced* to $\Phi_2$ and that $\langle \cdot \rangle$ is a *reduction function*. If we let $((S_{1,t}, I_t, J_{1,t}), t \in \mathbb{N})$ and $((S_{2,t}, I_t, J_{2,t}), t \in \mathbb{N})$ denote the Markov chains associated with policies $\Phi_1$ and $\Phi_2$, respectively, under the same sequence $(I_t, t \in \mathbb{N})$ of incoming item classes, then for each $t \in \mathbb{N}$, (i) the conditional distribution of $(J_{1,t}, \langle S_{1,t+1} \rangle)$ given that $S_{1,t} = s_1$ and $I_t = i$ is the same for all states $s_1 \in S_1$ that have the same image $s_2 = \langle s_1 \rangle$, and (ii) $(\langle S_{1,t} \rangle, I_t, J_{1,t})$ and $(S_{2,t}, I_t, J_{2,t})$ have the same distribution. Conclusion (ii) follows from an inductive argument and implies that policies $\Phi_1$ and $\Phi_2$ are stable or unstable under the same conditions and, if stable, yield the same matching rate vector.

The special case where the policy $\Phi_2$ is deterministic will be useful in Propositions 6.4 and 6.6. In this case, (8) says that, for each $s_2 \in S_2$ and $i \in V$, there exist $j \in V \cup \{\perp\}$ and
that $\Phi(s, i, j, s')$ is the conditional probability that, given an incoming class-i item finds the system in state $s$, the matching decision is $j$ and the new state is $s'$. The policy is assumed to be such that the Markov chain $S = (S_t, t \in \mathbb{N})$ defined on $S$ by the evolution of the system state is irreducible. The stochastic process $Q = (Q_t = |S_t|, t \in \mathbb{N})$ is called the *queue-size process*. It no longer satisfies the Markov property in general, but it does satisfy the evolution equations (2) and (3), with $L_i = (L_{t,i}, t \in \mathbb{N})$ and $M_k = (M_{t,k}, t \in \mathbb{N})$ defined by (4) and (5) for each $i \in V$ and $k \in E$. The state space of the queue-size process is given by $Q = \{|s|, s \in S\}$. The policy is greedy if $Q = Q_G$ and non-greedy if $Q \supsetneq Q_G$, where $Q_G$ is still given by (7). First-Come-First-Match (FCFM) (e.g., see [36, 16]) is a classical example of a deterministic policy that requires an expanded state descriptor (remembering the arrival order of items of different classes).

This extended policy definition can initially be ignored, with $S_t$ (resp. $S$) understood as $Q_t$ (resp. $Q$). All results for extended policies remain valid if restated for deterministic size-based policies, except for the convexity result in Proposition 20, which specifically relies on extended policies.

## 2.4 Stability.

We now define the notions of stability and stabilizability, which will be explored further in Section 3.

### ▶ Definition 1 (Stability and stabilizability).

(i) A model $(G, \lambda, \Phi)$ is stable if the Markov chain $(S_t, t \in \mathbb{N})$ is positive recurrent. In this case, we say that the policy $\Phi$ stabilizes the problem $(G, \lambda)$.

(ii) A problem $(G, \lambda)$ is stabilizable if there exists a policy that stabilizes it.

(iii) A compatibility graph $G$ is stabilizable if there exists a vector $\lambda \in \mathbb{R}_{\ge 0}^n$ such that the problem $(G, \lambda)$ is stabilizable.

The ML greedy policy, discussed in Section 2.3.2, has the property of stabilizing all stabilizable matching problems ([34]). The First-Come-First-Match (FCFM) greedy policy has the same property (see [36] for details). When the matching problem $(G, \lambda)$ is clear from the context, we will simply call a policy (adapted to $G$) stable if the corresponding model $(G, \lambda, \Phi)$ is stable.

Stability is a central property in our framework. In addition to ensuring finite waiting times—a desirable feature for dynamic matching applications such as organ donation, assemble-to-order systems, and online marketplaces—it also supports a rigorous theoretical analysis. In particular, it guarantees that matching rates can be properly defined.

### Matching rates.

Consider a stable matching model $(G, \lambda, \Phi)$. We define the matching rate $\mu_k$ along an edge $e_k \in E$, with endpoints $i$ and $j$, as the long-run average number of matches between a class-i item and a class-j item per unit of time, given by:

$$ \left( \sum_{i \in V} \lambda_i \right) \times \frac{1}{t} M_{t,k} \xrightarrow{\text{almost surely } t \to +\infty} \mu_k, \quad k \in E. \qquad (8) $$

This quantity is uniquely defined according to the ergodic theorem, see [38, Theorem 1.10.2]. Note that $M_{t,k}/t$ represents the average number of matches per arrival (out of the first $t$ arrivals), and the factor $(\sum_{i \in V} \lambda_i)$ converts this into the average number of matches per
$s'_2 \in S_2$ such that $\sum_{s'_i \in S_1: \langle s'_i \rangle = s'_2} \Phi_1(s_1, i, j, s'_i) = \Phi_2(s_2, i, j, s'_2) = 1$ for each $s_1 \in S_1$ such that $\langle s_1 \rangle = s_2$. This condition implies that the Markov chains under $\Phi_1$ and $\Phi_2$ are equivalent pathwise (i.e., $\langle S_{1,t} \rangle = S_{2,t}$ and $J_{1,t} = J_{2,t}$ for each $t \in \mathbb{N}$) and not just in distribution.

In general, we say that two policies $\Phi_1$ and $\Phi_2$ adapted to the graph $G$ are equivalent if there exists a policy $\Phi$ adapted to the graph $G$ such that both $\Phi_1$ and $\Phi_2$ can be reduced to $\Phi$. This equivalence between $\Phi_1$ and $\Phi_2$ can be interpreted as indicating that the two policies, when they are in equivalent states, i.e. states that have the same reduction, yield identical distributions of matching decisions. It implies that, if we let $(Q_{1,t}, t \in \mathbb{N})$ and $(Q_{2,t}, t \in \mathbb{N})$ denote the queue-size processes under $\Phi_1$ and $\Phi_2$ with the same sequence $(I_t, t \in \mathbb{N})$ of incoming item classes, then we have $\mathbb{P}(Q_{1,t} = q) = \mathbb{P}(Q_{2,t} = q)$ for each $t \in \mathbb{N}$ and $q \in \mathcal{Q}$.

## 2.4 Performance criteria

We now define the two performance indicators that will be the focus of the paper, namely stability and the matching rate vector. We will see later that the goals of preserving stability and maximizing a certain function of the matching rate vector are sometimes antagonist.

### Stability

We now define the notions of stability and stabilizability, which will be explored in Section 3.

### ► Definition 2.4 (Stability and stabilizability).

(i) A model $(G, \lambda, \Phi)$ is called stable if the Markov chain $(S_t, t \in \mathbb{N})$ is positive recurrent. In this case, we say that the policy $\Phi$ stabilizes the problem $(G, \lambda)$.

(ii) A problem $(G, \lambda)$ is called stabilizable if there exists a policy that stabilizes this problem.

(iii) A compatibility graph $G$ is called stabilizable if there exists a vector $\lambda \in \mathbb{R}_{>0}^n$ such that the problem $(G, \lambda)$ is stabilizable.

Both the match-the-longest and first-come-first-matched greedy policies, discussed in Section 2.3.2 and Section 2.3.4, respectively, possess the property of stabilizing all stabilizable matching problems [26, 28]. When the matching problem $(G, \lambda)$ is clear from the given context, we will call a policy (adapted to the graph $G$) stable if the corresponding model $(G, \lambda, \Phi)$ is stable.

### Matching rates

Consider a stable matching model $(G, \lambda, \Phi)$. We define the matching rate $\mu_k$ along an edge $e_k \in E$ with endpoints $i$ and $j$ as the long-run average number of matches between a class-i item and a class-j item per time unit, that is:

$$ \left( \sum_{i \in V} \lambda_i \right) \times \frac{1}{t} M_{t,k} \xrightarrow{\text{almost sure}} \mu_k, \quad k \in E. \qquad (9) $$

This quantity is uniquely defined according to the ergodic theorem [30, Theorem 1.10.2]. Note that $M_{t,k}/t$ is the average number of matches per arrival (out of the first $t$ arrivals), and the factor $(\sum_{i \in V} \lambda_i)$ only serves to convert this result into the average number of matches per time unit. The vector of matching rates associated with the model $(G, \lambda, \Phi)$ is denoted by $\mu = (\mu_1, \dots, \mu_m) \in \mathbb{R}_{\ge 0}^m$. If confusion can arise, we will use the notation $\mu(\Phi)$ or $\mu(G, \lambda, \Phi)$.
*unit of time.* The vector of matching rates associated with the model $(G, \lambda, \Phi)$ is denoted by $\mu = (\mu_1, \dots, \mu_m) \in \mathbb{R}_{\ge 0}^m$. When necessary, we write $\mu(\Phi)$ or $\mu(G, \lambda, \Phi)$ to indicate the dependence explicitly. Sections 3–5 will investigate the structural constraints that a vector of matching rates must satisfy.

<table><caption>Table 1 Table of key notation.</caption><thead><tr><th colspan="2">General notation</th></tr></thead><tbody><tr><td>$\mathbb{N}, \mathbb{N}_{>0}, \mathbb{R}, \mathbb{R}_{\ge 0}, \mathbb{R}_{>0}$</td><td>Sets of non-negative integers, positive integers, real numbers, non-negative real numbers, positive real numbers.</td></tr><tr><td>$\ge, \le, >, <$</td><td>Coordinate-wise comparison in $\mathbb{R}^n$.</td></tr><tr><td>$|A|$</td><td>Cardinality of the set $A$.</td></tr></tbody><thead><tr><th colspan="2">Graph notation</th></tr></thead><tbody><tr><td>$G = (V, E)$</td><td>Simple graph $G$ with $|V| = n$ vertices and $|E| = m$ edges.</td></tr><tr><td>$v_i$</td><td>Vertex indexed by $i$ (denoted $i$ if there is no ambiguity).</td></tr><tr><td>$e_k, k$, or $\{i, j\}$</td><td>Edge indexed by $k$, with endpoint vertices $i$ and $j$.</td></tr><tr><td>$V_i, V(I)$</td><td>Neighbor set of a node $i$ and of node set $I$.</td></tr><tr><td>$E_i$</td><td>Set of edges incident to node $i$.</td></tr></tbody><thead><tr><th colspan="2">Matching notation</th></tr></thead><tbody><tr><td>$\lambda = (\lambda_i)_{1 \le i \le n}$</td><td>Vector of arrival rates of the item classes.</td></tr><tr><td>$\Phi$</td><td>A matching policy.</td></tr><tr><td>$\mu = (\mu_k)_{1 \le k \le m} = (\mu_{i,j})_{\{i,j\} \in E}$</td><td>Vector of matching rates along the edges.</td></tr></tbody><thead><tr><th colspan="2">Linear-algebra notation</th></tr></thead><tbody><tr><td>$A = (a_{i,k})_{i \in V, k \in E}$</td><td>Incidence matrix of the graph $G$.</td></tr><tr><td>$A^T = (a_{k,i})_{k \in E, i \in V}$</td><td>Transpose of the matrix $A$.</td></tr><tr><td>$\ker(A) = \{y \in \mathbb{R}^m : Ay = 0\}$</td><td>Right kernel of the matrix $A$. Its dimension is called the nullity of $A$.</td></tr><tr><td>$\ker(A^T) = \{x \in \mathbb{R}^n : A^T x = 0\}$</td><td>Left kernel of the matrix $A$. Its dimension is the nullity of $A^T$.</td></tr><tr><td>$d = m - n$</td><td>Dimension of the right kernel of the matrix $A$ if $G$ is surjective.</td></tr></tbody></table>

# 3 Graph theory and linear algebra.

In this section, we present a central result of this paper, namely, the connection between stability and the structure of the compatibility graph. Section 3.1 introduces the conservation equation, a system of linear equations satisfied by all matching rate vectors. Section 3.2 introduces the related concepts of surjectivity, injectivity, and bijectivity that will play a key role throughout the paper. In Section 3.3, we combine these concepts to formulate new necessary and sufficient conditions under which a compatibility graph $G$ or a matching problem $(G, \lambda)$ is *stabilizable* in the sense of Definition 1. Section 3.4 illustrates these results with early examples.

## 3.1 Conservation equation.

Computing the matching rate vector achieved by a given stable policy or characterizing the set of matching rate vectors that can be achieved by stable policies is a difficult problem a priori. To circumvent this difficulty, we first establish a necessary condition known as the *conservation equation*. This equation is satisfied by the matching rate vectors achieved by all
► Remark 2.5 (Zero-rate edges). The following remark will play a key role in Sections 5.2.1 and 6. The matching rate along an edge $e_k \in E$ with endpoints i and j is given by

$$ \mu_k = \lambda_i \sum_{s,s' \in S} \pi(s) \Phi(s, i, j, s') + \lambda_j \sum_{s,s' \in S} \pi(s) \Phi(s, j, i, s'), $$

where $\pi$ is the equilibrium distribution of the Markov chain $(S_t, t \in \mathbb{N})$. Since $\lambda_i > 0$, $\lambda_j > 0$, and the distribution $\pi$ is positive on its support $S$, it follows that the matching rate $\mu_k$ is zero if and only if $\Phi(s, i, j, s') = \Phi(s, j, i, s') = 0$ for each $s, s' \in S$, that is, items of classes i and j are never matched with one another under policy $\Phi$. In this case, the policy $\Phi$ is also adapted to the subgraph $\underline{G} = (V, \underline{E})$ with $\underline{E} = E \setminus \{e_k\}$.

## 2.5 Implementation and numerical results

To support the results presented in this paper, we used the Python package Stochastic Matching [27]. It provides tools to analyze or simulate the behavior of stochastic matching models. We used it to check the characteristics of the examples presented in Section 5 and to perform simulations in Section 6. Unless otherwise stated, a matching model is evaluated by simulating $10^{10}$ arrivals.

# 3 Graph theory and linear algebra

In this section, we present a central result of this paper, the connection between stability and the structure of the compatibility graph. In details, Section 3.1 introduces the conservation equation, a system of linear equations satisfied by all vectors of matching rates. Section 3.2 introduces the related concepts of surjectivity, injectivity, and bijectivity that will play a key role throughout the paper. In Sections 3.3 and 3.4, we combine these concepts to formulate new necessary and sufficient conditions under which a compatibility graph $G$ or a matching problem $(G, \lambda)$ is stabilizable in the sense of Definition 2.4. Section 3.5 illustrates these results with early examples.

## 3.1 Conservation equation

Computing the matching rate vector achieved by a given stable policy or characterizing the set of matching rate vectors that can be achieved by stable policies is a difficult problem a priori. To circumvent this difficulty, we first establish a necessary condition known as the conservation equation. This equation is satisfied by the matching rate vectors achieved by all stable policies. It asserts that, in a stable system, the arrival of items and their departure due to matches balance each other in the long run. More formally, given a stable matching model $(G, \lambda, \Phi)$, the conservation equation (CE) can be derived by dividing (3) by $t$ and taking the limit as $t$ tends to infinity, and it can be written in two equivalent forms, either as a system of linear equations (CE-1) or in matrix form (CE-2):

$$ \sum_{k \in E_i} \mu_k = \lambda_i, \quad i \in V, \qquad (CE-1) $$

$$ A\mu = \lambda, \qquad (CE-2) $$

where the $n \times m$ matrix $A = (a_{i,k})_{i \in \{1, 2, \dots, n\}, k \in \{1, 2, \dots, m\}}$ is the incidence matrix of the graph $G$, defined by $a_{i,k} = 1$ if edge $e_k$ is incident to node $v_i$ and $a_{i,k} = 0$ otherwise. The use of a conservation equation is a conventional approach in queueing theory, but our
stable policies. It asserts that, in a stable system, the arrival of items and their departure due to matches balance each other in the long run. More formally, given a stable matching model (G, λ, Φ), the conservation equation (CE) can be derived by dividing (3) by t and taking the limit as t tends to infinity, and it can be written in two equivalent forms, either as a system of linear equations (CE-1) or in matrix form (CE-2):

$$ \sum_{k \in E_i} \mu_k = \lambda_i, \quad i \in V, \qquad (CE-1) $$

$$ A\mu = \lambda, \qquad (CE-2) $$

where the $n \times m$ matrix $A = (a_{i,k})_{i \in \{1, 2, \dots, n\}, k \in \{1, 2, \dots, m\}}$ is the incidence matrix of the graph G, defined by $a_{i,k} = 1$ if edge $e_k$ is incident to node $v_i$ and $a_{i,k} = 0$ otherwise. Using a conservation equation is common in queueing theory, but our contributions in this paper primarily stem from the novel mixed approach that combines graph theory and linear algebra, which we will elaborate on in the following sections.

The conservation equation (CE) holds significant importance throughout this paper. While our primary focus is to understand the matching rate vector, we often find it beneficial to temporarily depart from interpreting $\lambda$ and $\mu$ as vectors of arrival and matching rates in a matching model. Instead, we view the conservation equation as a linear equation with $\lambda$ as a free variable and $\mu$ as an unknown. This perspective allows us to explore various aspects of the equation and its implications. In this context, we will sometimes allow the coordinates of $\lambda$ and $\mu$ to be negative, even if the vectors of arrival and matching rates in a matching model have non-negative coordinates.

## 3.2 Surjectivity, injectivity, and bijectivity.

Definitions 2–5 below introduce the notions of surjectivity, injectivity, and bijectivity of a graph. In a nutshell, a compatibility graph G is said to be surjective (resp. injective, bijective) if the linear application $\mu \mapsto A\mu$ defined by its incidence matrix A is surjective (resp. injective, bijective). Interestingly, simple equivalent conditions exist in terms of the graph structure. As we will see later, these notions are fundamental to study the stability of matching models and the associated matching rate vector. In particular, we will see that (i) a compatibility graph G is stabilizable if and only if G is surjective, and (ii) the matching rates in a stabilizable matching problem $(G, \lambda)$ are independent of the policy $\Phi$ if and only if G is bijective. Toy examples are shown in Figure 2, and other illustrative examples are discussed in Section 3.4. The equivalence of the conditions given in Definitions 2–4 and the implications in Proposition 6 are proved in Appendix B.1.

**Definition 2 (Surjective graph).** Consider a simple graph G = (V, E) with n nodes and m edges. Let A denote the $n \times m$ incidence matrix of G. The graph G is called surjective if one of the following equivalent conditions is satisfied:

(i) The function $\mu \in \mathbb{R}^m \mapsto A\mu \in \mathbb{R}^n$ is surjective.

(ii) For each $\lambda \in \mathbb{R}^n$, the equation $A\mu = \lambda$ of unknown $\mu \in \mathbb{R}^m$ has at least one solution.

(iii) The left kernel of the matrix A is trivial.

(iv) Each connected component of the graph G is non-bipartite; in other words, each connected component of G contains at least one odd cycle.

**Definition 3 (Injective graph).** Consider a simple graph G = (V, E) with n nodes and m edges. Let A denote the $n \times m$ incidence matrix of G. The graph G is called injective if one of the following equivalent conditions is satisfied:
<table><caption>Table 1 Table of notation.</caption><thead><tr><th colspan="2">General notation</th></tr></thead><tbody><tr><td>$\mathbb{N}, \mathbb{N}_{\ge 0}, \mathbb{R}, \mathbb{R}_{\ge 0}, \mathbb{R}_{> 0}$</td><td>Sets of non-negative integers, positive integers, real numbers, non-negative real numbers, positive real numbers.</td></tr><tr><td>$\ge, \le, >, <$</td><td>Coordinate-wise comparison in $\mathbb{R}^n$.</td></tr><tr><td>$|\mathcal{A}|$</td><td>Cardinality of the set $\mathcal{A}$.</td></tr></tbody><thead><tr><th colspan="2">Graph notation</th></tr></thead><tbody><tr><td>$G = (V, E)$</td><td>Simple graph G with $|V| = n$ vertices and $|E| = m$ edges.</td></tr><tr><td>$v_i$</td><td>Vertex indexed by $i$ (denoted $i$ if there is not ambiguity).</td></tr><tr><td>$e_k, k$, or $\{i, j\}$</td><td>Edge indexed by $k$, with endpoints vertices $i$ and $j$.</td></tr><tr><td>$\mathbb{I}$</td><td>Family of independent sets of the graph $G$.</td></tr><tr><td>$V_i \subseteq V$</td><td>Set of neighbors of node $v_i$ in the graph $G$.</td></tr><tr><td>$V(\mathcal{I}) = \bigcup_{i \in \mathcal{I}} V_i$</td><td>Set of neighbors of the vertices indexed by the independent set $\mathcal{I} \in \mathbb{I}$.</td></tr><tr><td>$d_{i,j}$</td><td>Distance between nodes $i$ and $j$.</td></tr><tr><td>$d_{i,k} = \min(d_{i,j}, d_{i,j'})$</td><td>Distance between node $i$ and edge $k$ with endpoints $j$ and $j'$.</td></tr><tr><td>$K_\ell$</td><td>Complete graph on $\ell \ge 3$ nodes.</td></tr><tr><td>$C_\ell$</td><td>Cycle on $\ell \ge 3$ nodes.</td></tr><tr><td>$P_\ell$</td><td>Path of length $\ell \ge 0$.</td></tr><tr><td>$KP_{\ell,r,p}$</td><td>Kayak paddle: two cycles $C_\ell$ and $C_r$ attached by a path $P_p$.</td></tr></tbody><thead><tr><th colspan="2">Linear-algebra notation</th></tr></thead><tbody><tr><td>$x = (x_1, x_2, \dots, x_n)$</td><td>Arbitrary vector in $\mathbb{R}^n$. All vectors in $\mathbb{R}^n$ are column vectors.</td></tr><tr><td>$y = (y_1, y_2, \dots, y_m)$</td><td>Arbitrary vector in $\mathbb{R}^m$. All vectors in $\mathbb{R}^m$ are column vectors.</td></tr><tr><td>$A = (a_{i,k})_{i \in V, k \in E}$</td><td>Incidence matrix of the graph $G$.</td></tr><tr><td>$A^\top = (a_{k,i})_{k \in E, i \in V}$</td><td>Transpose of the matrix $A$.</td></tr><tr><td>$\ker(A) = \{y \in \mathbb{R}^m : Ay = 0\}$</td><td>Right kernel of the matrix $A$. Its dimension is called the nullity of $A$.</td></tr><tr><td>$\ker(A^\top) = \{x \in \mathbb{R}^n : A^\top x = 0\}$</td><td>Left kernel of the matrix $A$. Its dimension is the nullity of $A^\top$.</td></tr><tr><td>$d = m - n$</td><td>Dimension of the right kernel of the matrix $A$ if $G$ is surjective.</td></tr><tr><td>$\mathcal{B} = (b_1, \dots, b_d)$</td><td>A basis of the right kernel of the matrix $A$ if $G$ is surjective.</td></tr><tr><td>$\Pi = \{y \in \mathbb{R}^m : Ay = \lambda\}$</td><td>Affine space of the solutions of the conservation equation (CE-2).</td></tr><tr><td>$\Pi_{\ge 0} = \{y \in \mathbb{R}^m_{\ge 0} : Ay = \lambda\}$</td><td>Polytope of non-negative solutions of (CE-2).</td></tr><tr><td>$\Pi_{> 0} = \{y \in \mathbb{R}^m_{> 0} : Ay = \lambda\}$</td><td>Set of positive solutions of (CE-2).</td></tr></tbody><thead><tr><th colspan="2">Matching notation</th></tr></thead><tbody><tr><td>$\lambda = (\lambda_i)_{1 \le i \le n}$</td><td>Vector of arrival rates of the item classes.</td></tr><tr><td>$\Phi$</td><td>A matching policy.</td></tr><tr><td>$\mu = (\mu_k)_{1 \le k \le m} = (\mu_{i,j})_{\{i,j\} \in E}$</td><td>Vector of matching rates along the edges.</td></tr><tr><td>$\Pi_P$</td><td>Set of matching rates achieved by stable policies.</td></tr><tr><td>$\Pi_G$</td><td>Set of matching rates achieved by stable greedy policies.</td></tr></tbody></table>

contributions in this paper primarily stem from the novel mixed approach that combines graph theory and linear algebra, which we will elaborate on in the following sections.

The conservation equation (CE) holds significant importance throughout this paper. While our primary focus is to understand the matching rate vector, we often find it beneficial to temporarily depart from interpreting $\lambda$ and $\mu$ as vectors of arrival and matching rates in a matching model. Instead, we view the conservation equation as a linear equation with $\lambda$ as a free variable and $\mu$ as an unknown. This perspective allows us to explore various aspects of
<figure><img src="image_11.png" /><figcaption>(a) Graph that is neither surjective nor injective.
Both $A^\top$ and A have nullity 1.</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>(c) Injective-only graph. The nullity of $A^\top$ is 1 and
that of A is 0.</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>(b) Surjective-only graph. The nullity of $A^\top$ is 0
and that of A is 1.</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>(d) Bijective graph. Both $A^\top$ and A have nullity 0.</figcaption></figure>

Figure 2 Examples of graphs. The nullity of a matrix is the dimension of its kernel.

(i) The function $\mu \in \mathbb{R}^m \mapsto A\mu \in \mathbb{R}^n$ is injective.

(ii) For each $\lambda \in \mathbb{R}^n$, the equation $A\mu = \lambda$ of unknown $\mu \in \mathbb{R}^m$ has at most one solution.

(iii) The right kernel of the matrix A is trivial.

(iv) Each connected component of the graph G contains at most one odd cycle and no even cycle; in other words, each connected component of G is either a tree or a unicyclic graph with an odd cycle.

**► Definition 4 (Bijective graph).** Consider a simple graph $G = (V, E)$ with $n$ nodes and $m$ edges. Let $A$ denote the $n \times m$ incidence matrix of $G$. The graph $G$ is called bijective if the following equivalent conditions are satisfied:

(i) The function $\mu \in \mathbb{R}^m \mapsto A\mu \in \mathbb{R}^n$ is bijective.

(ii) For each $\lambda \in \mathbb{R}^n$, the equation $A\mu = \lambda$ of unknown $\mu \in \mathbb{R}^m$ has exactly one solution.

(iii) The matrix A is invertible.

(iv) Each connected component of the graph G contains one cycle and this cycle is odd.

**► Definition 5 (Surjective-only graph, injective-only graph).** A simple graph G is called surjective-only (resp. injective-only) if G is surjective but not injective (resp. injective but not surjective).

The following proposition gives necessary conditions for surjectivity and injectivity in terms
of the number of nodes and edges in the graph.

**► Proposition 6.** Consider an undirected graph $G = (V, E)$ with $n$ nodes and $m$ edges.

(i) If $G$ is surjective, then $n \le m$.

(ii) If $G$ is injective, then $n \ge m$.

(iii) If $G$ is bijective, then $n = m$.

(iv) If $G$ is surjective, then $G$ is also injective if and only if $n = m$.

(v) If $G$ is injective, then $G$ is also surjective if and only if $n = m$.

**3.3 Necessary and sufficient conditions for stabilizability**

The definitions and results of Sections 3.1 and 3.2 allow us to formulate new necessary and sufficient conditions for stabilizability.
the equation and its implications. In this context, we will sometimes allow the coordinates of $\lambda$ and $\mu$ to be negative, even if the vectors of arrival and matching rates in a matching model have non-negative coordinates. More specifically, the remainder of the paper focuses on the solutions of (CE) and considers, for a given stabilizable problem $(G, \lambda)$, the following sets:

$$ \Pi = \{y \in \mathbb{R}^m : Ay = \lambda\} \text{ (studied in Section 5.1)}, $$

$$ \Pi_{\ge 0} = \{y \in \mathbb{R}^m : Ay = \lambda\} \text{ (studied in Section 5.2)}, $$

$$ \Pi_{>0} = \{y \in \mathbb{R}^m : Ay = \lambda\} \text{ (introduced in Section 6)}, $$

$$ \Pi_G = \{\mu(G, \lambda, \Phi) : \Phi \text{ is a stable greedy policy adapted to } G\} \text{ (studied in Section 6.1)}, $$

$$ \Pi_P = \{\mu(G, \lambda, \Phi) : \Phi \text{ is a stable policy adapted to } G\} \text{ (studied in Sections 5.2.1 and 6.2).} $$

## 3.2 Surjectivity, injectivity, and bijectivity

Definitions 3.1–3.4 below introduce the notions of *surjectivity*, *injectivity*, and *bijectivity* of a graph. In a nutshell, a compatibility graph $G$ is said to be surjective (resp. injective, bijective) if the linear application $\mu \mapsto A\mu$ defined by its incidence matrix $A$ is surjective (resp. injective, bijective). Interestingly, simple equivalent conditions exist in terms of the graph structure. As we will see later, these notions are fundamental to study the stability of stochastic matching models and the associated matching rate vector. In particular, we will see that a compatibility graph $G$ is stabilizable if and only if $G$ is surjective in the sense of Definition 3.1. Later, we will see that the matching rates in a matching problem $(G, \lambda)$ are independent of the matching policy $\Phi$ (as long as the model is stable) if and only if $G$ is bijective in the sense of Definition 3.3. Examples are shown in Figure 2.

<figure><img src="image_2.png" /><figcaption>(a) Graph that is neither surjective nor injective. The nullity of $A^T$ is 1 and the nullity of $A$ is 1.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>(b) Surjective-only graph. The nullity of $A^T$ is 0 and the nullity of $A$ is 1.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>(c) Injective-only graph. The nullity of $A^T$ is 1 and the nullity of $A$ is 0.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>(d) Bijective graph. The nullity of $A^T$ is 0 and the nullity of $A$ is 0.</figcaption></figure>

### Figure 2 Examples of graphs.

**Definition 3.1 (Surjective graph).** Consider a simple graph $G = (V, E)$ with $n$ nodes and $m$ edges. Let $A$ denote the $n \times m$ incidence matrix of $G$. The graph $G$ is called *surjective* if one of the following equivalent conditions is satisfied:

(i) The function $\mu \in \mathbb{R}^m \mapsto A\mu \in \mathbb{R}^n$ is surjective.

(ii) For each $\lambda \in \mathbb{R}^n$, the equation $A\mu = \lambda$ of unknown $\mu \in \mathbb{R}^m$ has at least one solution.

(iii) The left kernel of the matrix $A$ is trivial.

(iv) Each connected component of the graph $G$ is non-bipartite.
### 3.3.1 Stabilizable compatibility graph.

The following proposition gives necessary and sufficient conditions for a graph $G$ to be stabilizable, in terms of either its structure or its incidence matrix.

**Proposition 7.** Let $G$ be a compatibility graph. The following conditions are equivalent:

(i) The graph $G$ is stabilizable.

(ii) The graph $G$ is surjective.

*Proof.* Equivalence between Proposition 7 i and Definition 2iv has been proved by [34, Theorem 1]. ◀

Although the equivalence between Proposition 7i and Definition 2iv is a known result, no prior literature on stochastic matching models (to the best of our knowledge) has explored the connection between Proposition 7i and the alternative definitions of surjectivity introduced in Definition 2. As we will see later, this new characterization of the stabilizability of a graph $G$ will be useful to analyze the relationship between delay and matching rates.

In the remainder, we will use the words “stabilizable” and “surjective” interchangeably. Furthermore, unless stated otherwise, we will assume that the graph $G$ is surjective.

### 3.3.2 Stabilizable matching problem.

We now turn to the stabilizability of a matching problem $(G, \lambda)$. As recalled in Section 2.4, two examples of greedy policies that stabilize the model whenever this matching problem is stabilizable are ML and FCFM, as shown by [34] and [36], respectively. Proposition 8 below provides necessary and sufficient conditions for the matching problem $(G, \lambda)$ to be stabilizable; condition ii was already derived by [34], but condition iii is new$^7$.

**Proposition 8.** Consider a matching problem $(G, \lambda)$ with a surjective graph $G$. The following conditions are equivalent:

(i) The matching problem $(G, \lambda)$ is stabilizable.

(ii) For each independent set $I \in \mathcal{I}$, we have $\sum_{i \in I} \lambda_i < \sum_{i \in V(I)} \lambda_i$, where $V(I) = \bigcup_{i \in I} V_i$ is the neighbor set of $I$.

(iii) The conservation equation (CE) admits a solution $\mu \in \mathbb{R}_{>0}^m$ (i.e., a solution with strictly positive components).

*Proof.* This result is proved in Appendix B.2 using results from [34, 16]. ◀

<figure><img src="image_15.png" /></figure>

One might expect that the time complexity to verify condition ii in Proposition 8 is exponential in the general case, considering that the number of independent sets grows exponentially fast with the number $n$ of classes. However, [34, Proposition 1] proved that there exists a polynomial algorithm for verifying this condition. It is worth noting that this verification process is indirect in that it involves constructing a bipartite double cover of $G$. In contrast, condition iii offers a more direct, polynomial-time method to verify the stabilizability of a matching model $(G, \mu)$. To present this approach more explicitly, we differentiate between two cases based on whether the graph $G$, assumed to be surjective, is surjective-only or bijective.

<footnote>$^7$ [36] concurrently proved a similar result, see Section 1.3.</footnote>
**Proof.** The equivalence of (i), (ii), and (iii) is a well-known result in linear algebra. We prove that conditions (iii) and (iv) are equivalent. This proof is adapted from [17, Lemma 2.2.3].

The key argument consists of observing that a vector $x = (x_1, x_2, \dots, x_n) \in \mathbb{R}^n$ belongs to the left kernel of the matrix $A$ if and only if

$$ \sum_{i=1}^{n} x_i a_{i,k} = 0, \quad k \in \{1, 2, \dots, m\}. $$

For each $k \in \{1, 2, \dots, m\}$, the $k$-th equation reads $x_j = -x_i$, where $i$ and $j$ are the endpoints of edge $k$. An induction argument shows that, for every path $i_1, i_2, \dots, i_k$ in the graph $G$, we have $x_{i_p} = (-1)^{p-1}x_{i_1}$ for each $p \in \{1, 2, \dots, k\}$.

First assume that condition (iv) is satisfied. Let $x \in \mathbb{R}^n$ be a vector of the left kernel of the matrix $A$. Since each connected component of $G$ is non-bipartite, for each $i \in V$, there exists a path of length say $\ell$ that connects node $i$ to a cycle $i_1, i_2, \dots, i_p, i_{p+1} = i_1$ consisting of an odd number $p$ of nodes. We then obtain $x_i = (-1)^{\ell+p+\ell}x_i = -x_i$, which implies that $x_i = 0$. Therefore, the left kernel of $A$ is trivial, meaning that condition (iii) is satisfied.

On the contrary, if condition (iv) is not satisfied, then there exists a connected component of $G$ that is bipartite with parts $V_+$ and $V_-$. We build a non-zero vector in the left kernel of $A$ by choosing $x_i = 1$ for each $i \in V_+$, $x_i = -1$ for each $i \in V_-$, and $x_i = 0$ for each $i \in V \setminus (V_+ \cup V_-)$. This implies that condition (iii) is not satisfied. ◀

**Definition 3.2 (Injective graph).** Consider a simple graph $G = (V, E)$ with $n$ nodes and $m$ edges. Let $A$ denote the $n \times m$ incidence matrix of $G$. The graph $G$ is called injective if one of the following equivalent conditions is satisfied:

(i) The function $\mu \in \mathbb{R}^m \mapsto A\mu \in \mathbb{R}^n$ is injective.

(ii) For each $\lambda \in \mathbb{R}^n$, the equation $A\mu = \lambda$ of unknown $\mu \in \mathbb{R}^m$ has at most one solution.

(iii) The right kernel of the matrix $A$ is trivial.

(iv) Each connected component of the graph $G$ contains at most one odd cycle and no even cycle; in other words, each connected component of $G$ is either a tree or a unicyclic graph with an odd cycle.

**Proof.** The equivalence of conditions (i), (ii), and (iii) is a well-known result in linear algebra. We now prove that conditions (iii) and (iv) are equivalent.

We first assume that the graph $G$ is connected and distinguish the following two cases:

- If $G$ is non-bipartite, according to Definition 3.1, the nullity of $A^\top$ is 0. The rank-nullity theorem implies that the rank of $A^\top$ is $n$, so that the rank of $A$ is also $n$. A second application of the rank-nullity theorem implies that the nullity of $A$ is $m-n$. In particular, $\ker(A) = \{0\}$ if and only if $m=n$.

- If $G$ is bipartite, any non-zero vector of the left kernel of $A$ must be parallel (collinear) to the non-zero vector $x$ constructed in the proof of Definition 3.1. This parallelism is due to the constraints $x_i = -x_j$ for all edges $\{i, j\}$. Based on this, the nullity of $A^\top$ is 1, and we conclude from another double application of the rank-nullity theorem that the nullity of $A$ is $m-n+1$. In particular, $\ker(A) = \{0\}$ if and only if $m=n-1$.

All in all, we obtain that condition (iii) is true if and only if either the graph $G$ is non-bipartite and contains as many edges as nodes, or the graph $G$ is bipartite and contains one less edge than it contains nodes. This, in turn, is equivalent to condition (iv).

If the graph $G$ is not connected, we can rewrite the matrix $A$ as a bloc matrix in which each bloc corresponds to a connected component, and we can then use the previous argument to prove the equivalence for each connected component. ◀
**Remark 1.** As observed by [16, Lemma 12], if the graph $G$ is surjective, condition iii in Proposition 8 gives a simple way of generating vectors $\lambda \in \mathbb{R}_{\ge 0}^n$ such that the problem $(G, \lambda)$ is stabilizable: it suffices to take $\lambda = A\mu$ for some $\mu \in \mathbb{R}_{>0}^m$. For instance, if $\mu = (\beta, \dots, \beta)$ for some $\beta > 0$, then the coordinates of $\lambda$ are proportional to the degree of each node.

**Verify stabilizability when $G$ is bijective.**

If the graph $G$ is bijective, then the matrix $A$ is invertible, and (CE) has a unique solution, namely $A^{-1}\lambda$. Proposition 8 implies that the matching problem $(G, \lambda)$ is stabilizable if and only if all coordinates of $A^{-1}\lambda$ are positive. The special case of bijective graphs will be investigated in detail in Section 4, where we will provide a more direct expression for $A^{-1}\lambda$.

**Verify stabilizability when $G$ is surjective-only.**

If the compatibility graph $G$ is surjective-only, (CE) has multiple solutions. To determine if one of these solutions is positive, it suffices to solve a linear optimization problem that searches for a solution to (CE) whose smallest coordinate is as large as possible:

$$ \begin{array}{ll} \text{Maximize} & z_{m+1}, \\ z=(z_1, z_2, \dots, z_{m+1}) \in \mathbb{R}^{m+1} & \\ \text{Subject to} & A(z_1, z_2, \dots, z_m)^\top = \lambda, \\ & z_i \ge z_{m+1}, \quad i \in \{1, 2, \dots, m\}. \end{array} \qquad (10) $$

Here, the first $m$ coordinates of the vector $z$ are the coordinates of a vector $\mu \in \mathbb{R}^m$ that satisfies (CE), and the last coordinate of $z$ is a lower bound of the coordinates of this vector $\mu$. Indeed, the equality constraint means that $\mu$ satisfies (CE), and the inequality constraint means that the last coordinate of $z$ is less than or equal to its other coordinates. The value to maximize is the last coordinate of the vector $z$.

If $z$ is a solution to (10), we call the corresponding vector $\mu \in \mathbb{R}^m$ a maximin solution to (CE). The optimization problem (10) is a textbook linear optimization problem. It can be solved with a time complexity that is polynomial in the number $n$ of nodes and the number $m$ of edges using many methods, for instance the interior-point-method, see [27].

The linear optimization problem (10) has a solution with positive coordinates if and only if (CE) has a solution with positive coordinates. According to Proposition 8, this is equivalent to saying that the matching problem $(G, \lambda)$ is stabilizable. Therefore, to verify if a matching problem $(G, \lambda)$ is stabilizable, it suffices to find a solution to the linear optimization problem (10) and to check if its last coordinate is positive.

**Remark 2.** Observe that the optimization problem (10) always has solutions with finite coordinates. Indeed, the set of vectors that satisfy the constraints of (10) contains at least one valid solution with real-valued coordinates (this is again a consequence of the surjectivity of $G$). We just need to consider an arbitrary solution $\mu$ of (CE) (see Section 5.1.2 for a concrete example using the Moore-Penrose inverse) and to let $z_\mu = (\mu_1, \mu_2, \dots, \mu_m, \min(\mu))$, where $\min(\mu)$ is the smallest coordinate of the vector $\mu$. Any solution better than $z_\mu$ has all its coordinates lower-bounded by $\min(\mu)$ and upper-bounded by $\max(\lambda) - \min(0, (n-2)\min(\mu))$. The latter bound is obtained by observing that, if edge $k$ is incident to node $i$ and if $(\mu'_1, \mu'_2, \dots, \mu'_m, x')$ is a solution to (10) such that $x' \ge \min(\mu)$, then $\mu'_k = \lambda_i - \sum_{\ell \in E_i \setminus k} \mu'_\ell$ by (CE). We then use the inequalities $\lambda_i \le \max(\lambda)$ and $\sum_{\ell \in E_i \setminus k} \mu'_\ell \ge \min(0, (n-2)x') \ge \min(0, (n-2)\min(\mu))$ (this latter inequality is obtained by distinguishing two cases, depending on whether $\min(\mu) \ge 0$ or $\min(\mu) < 0$). Therefore, the solutions better than $z_\mu$ belong to a compact set of $\mathbb{R}^{m+1}$, which ensures the existence of an optimal solution with finite coordinates.
**► Definition 3.3 (Bijective graph).** Consider a simple graph $G = (V, E)$ with $n$ nodes and $m$ edges. Let $A$ denote the $n \times m$ incidence matrix of $G$. The graph $G$ is called bijective if the following equivalent conditions are satisfied:

(i) The function $\mu \in \mathbb{R}^m \mapsto A\mu \in \mathbb{R}^n$ is bijective.

(ii) For each $\lambda \in \mathbb{R}^n$, the equation $A\mu = \lambda$ of unknown $\mu \in \mathbb{R}^m$ has exactly one solution.

(iii) The matrix $A$ is invertible.

(iv) Each connected component of the graph $G$ contains one cycle and this cycle is odd.

**Proof.** The function $\mu \in \mathbb{R}^m \mapsto A\mu \in \mathbb{R}^n$ is bijective if and only if it is both surjective and injective. Hence, the equivalence of conditions (i) to (iv) follows directly from Definitions 3.1 and 3.2.

◀

**► Definition 3.4 (Surjective-only graph and injective-only graph).** A simple graph $G$ is called surjective-only (resp. injective-only) if $G$ is surjective but not injective (resp. injective but not surjective).

The following proposition gives necessary conditions for surjectivity and injectivity in terms of the number of nodes and edges in the graph.

**► Proposition 3.5.** Consider an undirected graph $G = (V, E)$ with $n$ nodes and $m$ edges.

(i) If $G$ is surjective, then $n \le m$.

(ii) If $G$ is injective, then $n \ge m$.

(iii) If $G$ is bijective, then $n = m$.

(iv) If $G$ is surjective, then $G$ is also injective if and only if $n = m$.

(v) If $G$ is injective, then $G$ is also surjective if and only if $n = m$.

**Proof.** These statements (transposed to $A$) are again well-known in linear algebra.

◀

<figure><img src="image_6.png" /></figure>

## 3.3 Stabilizable compatibility graph

The following proposition gives necessary and sufficient conditions for a graph $G$ to be stabilizable, in terms of either its structure or its incidence matrix.

**► Proposition 3.6.** Let $G$ be a compatibility graph. The following conditions are equivalent:

(i) The graph $G$ is stabilizable.

(ii) The graph $G$ is surjective.

**Proof.** Equivalence between Proposition 3.6 (i) and Definition 3.1(iv) has been proved in [26, Theorem 1].

◀

<figure><img src="image_7.png" /></figure>

In the remainder, we will use the words “stabilizable” and “surjective” interchangeably. Furthermore, unless stated otherwise, we will assume that the graph $G$ is surjective.

Although the equivalence between Proposition 3.6(i) and Definition 3.1(iv) was already proved in [26] in the context of stochastic matching models, no prior literature on stochastic matching models (to the best of our knowledge) has explored the connection between Proposition 3.6(i) and the alternative definitions of surjectivity introduced in Definition 3.1. As we will see later, this new characterization of the stabilizability of a graph $G$ will be useful to analyze the matching rates.
## 3.4 Early examples.

We now provide examples that illustrate the stabilizability results of Propositions 7 and 8 as well as our definitions of surjectivity, injectivity, and bijectivity. These examples will also introduce useful notions that will be further explored in Sections 4–6.

### 3.4.1 Bijective graphs.

We first consider connected compatibility graphs $G$ that are both surjective and injective: the graph contains exactly one cycle, and this cycle is odd. According to Definition 4, (CE) has a unique solution for each vector $\lambda \in \mathbb{R}^n$ of arrival rates. Proposition 8 implies that the matching problem $(G, \lambda)$ is stabilizable if and only if the coordinates of this solution are positive, in which case this solution gives the matching rates achieved by all stable matching policies. By Remark 1, one can always exhibit a vector $\lambda \in \mathbb{R}_{>0}^n$ of arrival rates such that the matching problem $(G, \lambda)$ is stable.

<figure><img src="image_16.png" /><figcaption>(a) Matching rates in the triangle graph $C_3$.</figcaption></figure>

<figure><img src="image_17.png" /><figcaption>(b) Matching rates in the paw graph. $\bar{\lambda}_3 = \lambda_3 - \lambda_4$ denotes the residual rate that class 3 can provide to classes 1 and 2.</figcaption></figure>

<figure><img src="image_18.png" /><figcaption>(c) Matching rates in the square (d) Matching rates in the diamond graph with the normalization graph $C_4$ with the normalization $\lambda_1 + \lambda_4 = \frac{1}{2}$. $2\beta = \lambda_2 + \lambda_3 - \lambda_1 - \lambda_4 = \lambda_2 + \lambda_3 - \frac{1}{2}$ is the difference $\lambda_1 + \lambda_4 = \lambda_2 + \lambda_3 = \frac{1}{2}$. This graph between the arrival rates of the inner part $\{2, 3\}$ and the outer part is not stabilizable.
$\{1, 4\}$. $\bar{\lambda}_2 = \lambda_2 - \beta$ and $\bar{\lambda}_3 = \lambda_3 - \beta$ represent the residual rates that classes 2 and 3 can provide to classes 1 and 4, and they are such that $\lambda_1 + \lambda_4 = \bar{\lambda}_2 + \bar{\lambda}_3 = \frac{1}{2}$, as in Example 3.</figcaption></figure>

<figure><img src="image_19.png" /></figure>

<figure><img src="image_20.png" /><figcaption>(e) Matching rates in the kayak paddle $KP_{3,3,1}$.</figcaption></figure>

<caption>■ **Figure 3** Examples of Section 3.4.</caption>
## 3.4 Stabilizable matching problem

We now turn to the stabilizability of a matching problem $(G, \lambda)$. As recalled in Section 2.4, two examples of greedy policies that stabilize the model whenever this matching problem is stabilizable are *match-the-longest* [26] and *first-come-first-matched* [28]. Proposition 3.7 below provides necessary and sufficient conditions for the matching problem $(G, \lambda)$ to be stabilizable; condition (ii) was already derived in [26], but condition (iii) is new.

**Proposition 3.7.** *Consider a matching problem $(G, \lambda)$ with a surjective graph $G$. The following conditions are equivalent:*

(i) *The matching problem $(G, \lambda)$ is stabilizable.*

(ii) *For each independent set $I \in \mathcal{I}$, we have $\sum_{i \in I} \lambda_i < \sum_{i \in V(I)} \lambda_i$.*

(iii) *The conservation equation (CE) admits a solution $\mu \in \mathbb{R}_{>0}^m$ (i.e., a solution with strictly positive components).*

**Proof.** Equivalence of (i) and (ii) follows from [26, Proposition 2 and Theorem 2]. For completeness, we observe that [26, Proposition 2] is proved under the assumption that the matching policy $\Phi$ is greedy and deterministic and that the state space $(S, |\cdot|)$ has a particular form, but we can verify that the argument remains valid under the assumptions of Section 2. We now prove that (ii) and (iii) are equivalent. Condition (ii) implies condition (iii) because (a) according to [26], under condition (ii), $(G, \lambda, \Phi)$ is stable if $\Phi$ is the *match-the-longest* policy, and (b) the associated vector $\mu$ of matching rates satisfies condition (iii) by ergodicity. That condition (iii) implies condition (ii) was proved in [15, Lemma 12]. ◀

One might expect that the time complexity to verify condition (ii) in Proposition 3.7 is exponential in the general case, considering that the number of independent sets grows exponentially with the number $n$ of classes. However, in [26, Proposition 1], it was proven that there exists an $O(n^3)$-time algorithm for verifying this condition. It is worth noting that this verification process is indirect in the sense that it involves constructing a bipartite double cover of $G$. In contrast, condition (iii) provides a more direct approach to verify the stabilizability of a matching model $(G, \mu)$. To present this approach more explicitly, we differentiate between two cases based on whether the graph $G$, assumed to be surjective, is surjective-only or bijective.

**Remark 3.8.** As observed in [15, Lemma 12], if the graph $G$ is surjective, condition (iii) in Proposition 3.7 gives a simple way of generating vectors $\lambda \in \mathbb{R}_{\ge 0}^n$ such that the problem $(G, \lambda)$ is stabilizable: it suffices to take $\lambda = A\mu$ for some $\mu \in \mathbb{R}_{>0}^m$. For instance, if $\mu = (\beta, \dots, \beta)$ for some $\beta > 0$, then the coordinates of $\lambda$ are proportional to the degree of each node.

### Verify stabilizability when $G$ is bijective

If the graph $G$ is bijective, then the matrix $A$ is invertible, and (CE) has a unique solution, namely $A^{-1}\lambda$. Proposition 3.7 implies that the matching problem $(G, \lambda)$ is stabilizable if and only if all coordinates of $A^{-1}\lambda$ are positive. The special case of bijective graphs will be investigated in detail in Section 4, where we will provide a more direct expression for $A^{-1}\lambda$.

### Verify stabilizability when $G$ is surjective-only

If the compatibility graph $G$ is surjective-only, (CE) has multiple solutions. To determine if one of these solutions is positive, it suffices to solve a linear optimization problem that
**► Example 1 (Triangle).** If the graph G is a triangle graph $C_3$, and the vector $\lambda = (\lambda_1, \lambda_2, \lambda_3)$ is given, the solution to (CE) is unique and shown in Figure 3a. Indeed, a triangle graph contains a unique cycle which is odd, hence it is bijective according to Definition 2. According to Proposition 8iii, $(G, \lambda)$ is stabilizable if and only if all coordinates of the unique solution of (CE) are positive. This condition is equivalent to Proposition 8ii, which states that $\lambda_1 < \lambda_2 + \lambda_3$, $\lambda_2 < \lambda_1 + \lambda_3$, and $\lambda_3 < \lambda_1 + \lambda_2$. Alternatively, this condition can be expressed as $\lambda_1, \lambda_2$, and $\lambda_3$ being the lengths of the sides of a non-degenerate triangle (i.e., they satisfy the triangular inequality). Under these conditions, the model $(G, \lambda, \Phi)$ is stable if $\Phi$ is for instance the (unique) greedy policy adapted to G (Proposition 34 shows that a complete graph G admits a unique greedy policy $\Phi$).

**► Example 2 (Paw graph).** If G is a paw graph, the solution to (CE) is again unique and shown in Figure 3b. Here, $\bar{\lambda}_3 = \lambda_3 - \lambda_4$ is the remaining rate of class 3 after accounting for the needs of class 4. After this subtraction, the matching rates along edges $\{1, 2\}$, $\{1, 3\}$, and $\{2, 3\}$ are defined as in the triangle graph of Figure 3a.

It is important to note that, while the existence of a matching rate vector with positive coordinates guarantees that a greedy policy like ML is stable, there may still exist greedy policies that are unstable. Consider, for instance, the paw graph of Figure 3b and a Highest-Reward-First policy where the edges $\{1, 3\}$ and $\{2, 3\}$ offer higher rewards than $\{3, 4\}$. Even if the problem is stabilizable, this policy might select the edge $\{3, 4\}$ at a slower rate than class-4 items arrive, causing instability (see [34, Section 5]).

### 3.4.2 Bipartite graph (neither injective nor surjective).

Besides explaining intuitively why bipartite graphs cannot be stabilized, the following example will prepare the ground for Example 4.

**► Example 3 (Square graph).** Figure 3c shows a square graph $C_4$. This graph is not surjective because it is bipartite with parts $\{1, 4\}$ (called the outer part) and $\{2, 3\}$ (inner part). Therefore, according to Proposition 7, this graph is not stabilizable. Yet, given a vector $\lambda = (\lambda_1, \lambda_2, \lambda_3, \lambda_4)$ of arrival rates, (CE) may still have a solution with positive coordinates. This does not contradict Proposition 8, as Statement iii is equivalent to Statements i and ii only if the graph G is surjective. Assuming unit normalization, the conservation equation (CE-2) has a solution if and only if

$$ \lambda_1 + \lambda_4 = \lambda_2 + \lambda_3 = \frac{1}{2}. \qquad (11) $$

If (11) is satisfied, the solutions to (CE) can be described with a parameter $\alpha$ as shown in Figure 3c: starting from the particular solution $\mu = (2\lambda_1\lambda_2, 2\lambda_1\lambda_3, 2\lambda_2\lambda_4, 2\lambda_3\lambda_4)$, all solutions can be generated by alternately adding and subtracting $\alpha$ along the (even) cycle $1-2-4-3$. The positive solutions correspond to values of $\alpha$ such that $-2\min(\lambda_1\lambda_2, \lambda_3\lambda_4) < \alpha < 2\min(\lambda_1\lambda_3, \lambda_2\lambda_4)$.

To understand why the matching problem $(C_4, \lambda)$ is not stabilizable even when (CE) has a solution with positive coordinates, let us focus on the system dynamics. We can use (3) to show that the difference in total queue size between the outer part $\{1, 4\}$ and the inner part $\{2, 3\}$ satisfies $Q_{t,1} + Q_{t,4} - (Q_{t,2} + Q_{t,3}) = L_{t,1} + L_{t,4} - (L_{t,2} + L_{t,3})$ for each $t \in \mathbb{N}$. Therefore, the Markov chain $(Q_{t,1} + Q_{t,4} - (Q_{t,2} + Q_{t,3}), t \in \mathbb{N})$ is a random walk on the integer number line $\{\dots, -2, -1, 0, 1, 2, \dots\}$, with transition probability proportional to $\lambda_1 + \lambda_4$ in the increasing direction and to $\lambda_2 + \lambda_3$ in the decreasing direction. If (11) is not satisfied, this random walk is transient, and the difference between the queue sizes of the two parts
searches for a solution of (CE) whose smallest coordinate is as large as possible:

$$
\begin{array}{ll}
\text{Maximize} & z_{m+1}, \\
\text{Subject to} & A(z_1, z_2, \dots, z_m)^\top = \lambda, \\
& z_i \ge z_{m+1}, \quad i \in \{1, 2, \dots, m\}. \qquad (11)
\end{array}
$$

Here, the first *m* coordinates of the vector *z* are the coordinates of a vector *μ* ∈ ℝ*^m* that satisfies (CE), and the last coordinate of *z* is a lower bound of the coordinates of this vector *μ*. Indeed, the equality constraint means that *μ* satisfies (CE), and the inequality constraint means that the last coordinate of *z* is less than or equal to its other coordinates. The value to maximize is the last coordinate of the vector *z*.

If *z* is a solution of (11), we call the corresponding vector *μ* ∈ ℝ*^m* a *maximin* solution of (CE). The optimization problem (11) is a textbook linear optimization problem. It can be solved with a time complexity that is polynomial in the number *n* of nodes and the number *m* of edges using many methods, for instance the interior-point-method [23].

The linear optimization problem (11) has a solution with positive coordinates if and
only if (CE) has a solution with positive coordinates. According to Proposition 3.7, this is
equivalent to saying that the matching problem (G, λ) is stabilizable. Therefore, to verify if a
matching problem (G, λ) is stabilizable, it suffices to find a solution of the linear optimization
problem (11) and to check if its last coordinate is positive.

► Remark 3.9. Observe that the optimization problem (11) always has solutions with finite coordinates. Indeed, the set of vectors that satisfy the constraints of (11) contains at least one valid solution with real-valued coordinates (this is again a consequence of the surjectivity of G). We just need to consider an arbitrary solution µ of (CE) (see Section 5.1.2 for a concrete example using the Moore-Penrose inverse) and to let z_µ = (µ_1, µ_2, ..., µ_m, min(µ)), where min(µ) is the smallest coordinate of the vector µ. Any solution better than z_µ has all its coordinates lower-bounded by min(µ) and upper-bounded by max(λ) - min(0, (n-2)min(µ)). The latter bound is obtained by observing that, if edge k is incident to node i and if (µ'_1, µ'_2, ..., µ'_m, x') is a solution of (11) such that x' ≥ min(µ), then µ'_k = λ_i - Σ_{ℓ∈E_i \setminus k} µ'_ℓ by (CE). We then use the inequalities λ_i ≤ max(λ) and Σ_{ℓ∈E_i \setminus k} µ'_ℓ ≥ min(0, (n-2)x') ≥ min(0, (n-2)min(µ)) (this latter inequality is obtained by distinguishing two cases, depending on whether min(µ) ≥ 0 or min(µ) < 0). Therefore, the solutions better than z_µ belong to a compact set of ℝ^{m+1}, which ensures the existence of an optimal solution with finite coordinates.

**3.5 Early examples**

We now provide illustrative examples that demonstrate the concepts introduced in Propositions 3.6 and 3.7 as well as our definitions of surjectivity, injectivity, and bijectivity. These examples will also introduce useful notions that will be further explored in Sections 4–6.

**3.5.1 Bijective graphs**

We first consider a compatibility graph *G* that is both surjective and injective. According to Definition 3.3, (CE) has a unique solution for each vector *λ* ∈ ℝ*^n* of arrival rates. Proposition 3.7 implies that the matching problem (*G*, *λ*) is stabilizable if and only if the coordinates of this solution are positive. By Remark 3.8, one can easily exhibit a vector *λ* ∈ ℝ*^n*≥₀ of arrival rates that satisfies this condition.
grows linearly with time. On the other hand, if (11) is satisfied, then the random walk does not have this bias, but the model is still unstable because the corresponding Markov chain is null recurrent<fnref n="8" />.

### 3.4.3 Surjective-only graphs.

We finally consider a compatibility graph $G$ that is surjective but not injective. In other words, the graph $G$ is stabilizable and (CE) has an infinite number of solutions. The achievability of these solutions by a stable matching policy will be discussed in Section 6.

**► Example 4 (Diamond (double-fan) graph).** Figure 3d shows the diamond graph $D$, that is, a square graph with an additional edge between nodes 2 and 3. Compared to Example 3, this additional edge makes the graph non-bipartite, and therefore surjective, so that the graph is stabilizable according to Proposition 7. For ease of computation, we assume that the vector $\lambda = (\lambda_1, \lambda_2, \lambda_3, \lambda_4)$ of arrival rates is normalized so that $\lambda_1 + \lambda_4 = \frac{1}{2}$. Under this assumption, and with $\beta = \frac{1}{2}(\lambda_2 + \lambda_3 - \lambda_1 - \lambda_4) = \frac{1}{2}(\lambda_2 + \lambda_3) - \frac{1}{4}$, $\bar{\lambda}_2 = \lambda_2 - \beta$, and $\bar{\lambda}_3 = \lambda_3 - \beta$, the general solution to (CE) can be described with a parameter $\alpha$ as shown in Figure 3d. After subtracting $\beta$ from $\lambda_2$ and $\lambda_3$, the solutions to (CE) for all edges but $\{2, 3\}$ are exactly the same as in the square graph of Example 3.

According to Proposition 8ii, the matching problem $(D, \lambda)$ is stabilizable if and only if

$$ \lambda_2 < \lambda_1 + \lambda_3 + \lambda_4, \quad \lambda_3 < \lambda_1 + \lambda_2 + \lambda_4, \quad \lambda_1 + \lambda_4 < \lambda_2 + \lambda_3, \quad (12) $$

that is, $\bar{\lambda}_3 > 0$, $\bar{\lambda}_2 > 0$, and $\beta > 0$. If these inequalities are satisfied, the positive solutions correspond to values of $\alpha$ such that $-2\min(\lambda_1\bar{\lambda}_2, \bar{\lambda}_3\lambda_4) < \alpha < 2\min(\lambda_1\bar{\lambda}_3, \bar{\lambda}_2\lambda_4)$. Intuitively, compared to the square graph, stabilizable matching problems $(D, \lambda)$ have a positive difference of $2\beta$ between the arrival rates of the inner part $\{2, 3\}$ and the outer part $\{1, 4\}$. This difference is absorbed by the central edge $\{2, 3\}$, which has matching rate $\beta$. Like Example 1 and unlike Example 2, the matching model $(D, \lambda, \Phi)$ is stable for every greedy policy $\Phi$ provided that (12) is satisfied (as shown in Corollary 27 of Appendix B.3).

**► Example 5 (Kayak paddle graph).** Figure 3e shows a kayak paddle $KP_{3,3,1}$, consisting of two triangles linked by an edge. According to Proposition 8, the matching problem $(G, \lambda)$ is stabilizable if and only if there exists $\alpha > 0$ such that $(\lambda_1, \lambda_2, \lambda_3 - \alpha)$ and $(\lambda_4 - \alpha, \lambda_5, \lambda_6)$ are the arrival rate vectors of two stabilizable triangle graphs $C_3$. The solutions to (CE) can be described by varying $\alpha$ as shown in Figure 3e. Assuming the matching problem $(G, \lambda)$ is stabilizable, the solutions to (CE) with positive coordinates correspond to the values of $\alpha$ such that

$$ 0 < \alpha < \min(\lambda_3 - |\lambda_2 - \lambda_1|, \lambda_4 - |\lambda_5 - \lambda_6|). $$

Intuitively, solutions with positive coordinates have a positive matching rate $\alpha$ along edge $\{3, 4\}$. After subtracting this rate from $\lambda_3$ and $\lambda_4$, the subgraphs restricted to nodes 1, 2, and 3 and to nodes 4, 5, and 6, respectively, behave like the triangle of Figure 3a. Like Example 2 and unlike Examples 1 and 4, the fact that $(G, \lambda)$ is stabilizable does not guarantee the stability of all greedy policies.

<footnote n="8">⁸ Some existing studies of matching in bipartite graphs solve this issue by coupling arrivals in the two components, see [2, 9, 13], or by assuming that items have a finite patience time, as in [26].</footnote>
**► Example 3.10 (Triangle).** If the graph $G$ is a triangle graph $C_3$, and the vector $\lambda = (\lambda_1, \lambda_2, \lambda_3)$ is given, the solution of (CE) is unique and shown in Figure 3. According to Proposition 3.7(iii), $(G, \lambda)$ is stabilizable if and only if all coordinates of this solution are positive. This condition is indeed equivalent to Proposition 3.7(ii), which states that $\lambda_1 < \lambda_2 + \lambda_3$, $\lambda_2 < \lambda_1 + \lambda_3$, and $\lambda_3 < \lambda_1 + \lambda_2$. Alternatively, this condition can be expressed as $\lambda_1, \lambda_2$, and $\lambda_3$ being the lengths of the sides of a non-degenerate triangle (which have to satisfy the triangular inequality). Under these conditions, the model $(G, \lambda, \Phi)$ is stable under the unique greedy policy $\Phi$ (as shown in Proposition 6.4).

<figure><img src="image_8.png" /><figcaption>■ **Figure 3** Matching rates in the triangle graph $C_3$.</figcaption></figure>

**► Example 3.11 (Paw graph).** If $G$ is a paw graph, the solution of (CE) is again unique and shown in Figure 4. Here, $\bar{\lambda}_3 = \lambda_3 - \lambda_4$ represents the remaining rate of class 3 after accounting for the needs of class 4. After this subtraction, the matching rates along edges $\{1,2\}$, $\{1,3\}$, and $\{2,3\}$ are defined as in the triangle graph of Figure 3.

It is important to note that, while the existence of a matching rate vector with positive coordinates guarantees the existence of a stable greedy policy like *match-the-longest*, there may still exist greedy policies that lead to instability. For instance, again consider the paw graph of Figure 4 and a *edge-priority* policy where edges $\{1,3\}$ and $\{2,3\}$ are preferred over edge $\{3,4\}$. Intuitively, despite the problem being stabilizable, such a policy may result in a low matching rate $\mu_{3,4}$ due to the priorities: if $\mu_{3,4} < \lambda_4$, this situation would even lead to instability. This observation will be useful in Conjecture 6.10, which requires to develop a greedy policy that does not stabilize a matching problem $(G, \lambda)$ even when it is stabilizable.

<figure><img src="image_9.png" /><figcaption>■ **Figure 4** Matching rates in the paw graph. $\bar{\lambda}_3 = \lambda_3 - \lambda_4$ denotes the residual rate that class 3 can provide to classes 1 and 2.</figcaption></figure>

### 3.5.2 Bipartite graph (that is neither injective nor surjective)

**► Example 3.12 (Square graph).** Figure 5 shows a square graph $G = C_4$. This graph is not surjective because it is bipartite with parts $\{1,4\}$ (outer part) and $\{2,3\}$ (inner part).
4 Matching rates in bijective graphs.

In the remainder, we consider exclusively compatibility graphs $G$ that are stabilizable. According to Definition 2 and Proposition 7, this implies that the graph $G$ is surjective, i.e., that each connected component of $G$ is non-bipartite. By Proposition 6iv and Proposition 8, there are only two possible cases:

1. If $n = m$, the graph $G$ is also bijective: each connected component of $G$ is a unicyclic graph, and its (only) cycle is odd. The conservation equation (CE) has a unique solution given by $\mu = A^{-1}\lambda$. The matching problem $(G, \lambda)$ is stabilizable if and only if all components of this solution are positive, in which case the solution provides the matching rates achievable by any stable policy.

2. If $n < m$, the graph $G$ is surjective-only: each connected component of $G$ is non-bipartite, and at least one of these connected components contains an even cycle or a pair of odd cycles. The conservation equation (CE) has an infinite number of solutions. The matching problem $(G, \lambda)$ is stabilizable if and only if one of them has all-positive components. Case 1 is studied in this section, while case 2 will be studied in Sections 5 and 6.

In Proposition 9 below, we give a simpler expression for the unique solution $\mu = A^{-1}\lambda$ of (CE) in terms of the arrival rate vector $\lambda$, under the assumption that the graph $G$ is bijective. We assume without loss of generality that $G$ is connected, as otherwise we can consider each connected component independently. Compared to the expression $\mu = A^{-1}\lambda$, the advantage of Proposition 9 is twofold: it does not require calculating a matrix inversion, and it highlights the monotonicity of the matching rates with respect to the arrival rates. This result will be illustrated in Examples 6 and 7. Note that a similar result was independently derived in [29, Theorem 4.1]. As discussed in Section 1.3, [29] considers a different setting where the only objective is to maximize reward, without enforcing stability. The analysis in [29] exploits a closed-form characterization of the solution to the conservation equation for both bijective and injective-only graphs. In contrast, Proposition 9 focuses exclusively on the bijective case, which simplifies the proof and discussion.

**Proposition 9.** Consider a problem $(G, \lambda)$ with a compatibility graph $G = (V, E)$ that is connected and bijective, and consider an edge $k \in E$.

(i) If edge $k$ does not belong to the (unique odd) cycle of the graph $G$, then edge $k$ separates the graph $G$ into two parts, namely a tree and a unicyclic graph. If $T_k \subset V$ denotes the set of nodes that belong to the tree (including one endpoint of edge $k$), then the matching rate along edge $k$ is given by

$$ \mu_k = \sum_{i \in T_k} (-1)^{d_{i,k}} \lambda_i, \qquad (13) $$

where $d_{i,k}$ is the distance between node $i$ and edge $k$, defined as the distance between node $i$ and the closest endpoint of edge $k$.

(ii) If edge $k$ belongs to the (unique odd) cycle of the graph $G$, then the matching rate along edge $k$ is

$$ \mu_k = \frac{1}{2} \left( \sum_{i \in V} (-1)^{d_{i,k}} \lambda_i \right). \qquad (14) $$

**Proof.** We first prove (13) for every edge $k$ that does not belong to the cycle. As observed in the proposition, each edge $k$ that does not belong to the cycle separates the graph into two parts, one of which is a tree with node set $T_k$; the rooted tree associated with $k$ is obtained
Therefore, according to Proposition 3.6, this graph is not stabilizable. Yet, given a vector $\lambda = (\lambda_1, \lambda_2, \lambda_3, \lambda_4)$ of arrival rates, (CE) may still have a solution with positive coordinates. This does not contradict Proposition 3.7, as statement (iii) is equivalent to statements (i) and (ii) only if the graph $G$ is surjective. Assuming unit normalization, the conservation equation (CE-2) has a solution if and only if

$$ \lambda_1 + \lambda_4 = \lambda_2 + \lambda_3 = \frac{1}{2}. \qquad (12) $$

If (12) is satisfied, the solutions of (CE) can be described with a parameter $\alpha$ as shown in Figure 5: starting from the particular solution $\mu = (2\lambda_1\lambda_2, 2\lambda_1\lambda_3, 2\lambda_2\lambda_4, 2\lambda_3\lambda_4)$, all solutions can be generated by alternately adding and subtracting $\alpha$ along the (even) cycle 1-2-4-3-1. The positive solutions correspond to values of $\alpha$ such that $-2\min(\lambda_1\lambda_2, \lambda_3\lambda_4) < \alpha < 2\min(\lambda_1\lambda_3, \lambda_2\lambda_4)$.

<figure><img src="image_10.png" /><figcaption>■ Figure 5 Matching rates in the square graph $C_4$ with the normalization $\lambda_1 + \lambda_4 = \lambda_2 + \lambda_3 = \frac{1}{2}$. This graph is not stabilizable.</figcaption></figure>

Focusing on the system dynamics, we can use (3) to prove that the difference in total queue size between the outer part $\{1, 4\}$ and the inner part $\{2, 3\}$ satisfies $Q_{t,1}+Q_{t,4}-(Q_{t,2}+Q_{t,3}) = L_{t,1}+L_{t,4}-(L_{t,2}+L_{t,3})$ for each $t \in \mathbb{N}$. Therefore, the Markov chain $(Q_{t,1}+Q_{t,4}-(Q_{t,2}+Q_{t,3}), t \in \mathbb{N})$ is a random walk on the integer number line $\{\dots, -2, -1, 0, 1, 2, \dots\}$, with transition probability proportional to $\lambda_1 + \lambda_4$ in the increasing direction and to $\lambda_2 + \lambda_3$ in the decreasing direction. If (12) is not satisfied, this random walk is transient, and the difference between the queue sizes of the two parts grows linearly with time. On the other hand, if (12) is satisfied, then the random walk does not have this bias, but the model is still unstable because the corresponding Markov chain is null recurrent$^6$.

### 3.5.3 Surjective-only graphs

We finally consider compatibility graphs $G$ that are surjective but not injective. In other words, the graph $G$ is stabilizable and (CE) has an infinite number of solutions. Whether or not these solutions are achievable by a stable matching policy will be discussed in Section 6.

► **Example 3.13 (Diamond (double-fan) graph).** Figure 6 shows the diamond graph $D$, that is, a square graph with an additional edge between nodes 2 and 3. Compared to Example 3.12, this additional edge makes the graph non-bipartite, and therefore surjective, so that the graph is stabilizable according to Proposition 3.6. For ease of computation, we assume that the vector $\lambda = (\lambda_1, \lambda_2, \lambda_3, \lambda_4)$ of arrival rates is normalized so that $\lambda_1 + \lambda_4 = \frac{1}{2}$. Under

<footnote>$^6$ Existing studies of matching in bipartite graphs usually solve this issue by coupling arrivals in both coordinates [2, 9, 13] or by assuming that items have a finite patience time [22].</footnote>
by designating the corresponding endpoint of edge k as the root. We now prove (13) by induction on the height this rooted tree. Equation (13) is true if the height of this tree is zero. Indeed, in this case, the endpoint of edge k that belongs to the tree, say node i, has no other incident edge, so that applying (CE-1) to node i yields $\mu_k = \lambda_i$, which is consistent with (13). Now assume that the assumption is satisfied for each edge whose associated rooted tree has height at most $h-1$ for some $h \ge 0$, and consider an edge k whose associated rooted tree has height h. By applying (CE-1) to the root i of this associated rooted tree, we obtain

$$ \mu_k = \lambda_i - \sum_{\ell \in E_i \setminus \{k\}} \mu_\ell. \qquad (15) $$

The induction hypothesis guarantees that (13) is satisfied for every $\ell \in E_i \setminus \{k\}$ (as the height of the associated rooted tree is at most $h-1$). After injecting this observation to (15), the result for edge k follows by observing that $d_{j,k} = d_{j,\ell} + 1$ for each $\ell \in E_i \setminus \{k\}$ and $j \in T_\ell$, and that $T_k = \{i\} \cup (\cup_{\ell \in E_i \setminus \{k\}} T_\ell)$ (all sets being disjoint).

We now prove (14) for each edge k that belongs to the cycle. Since the graph G is unicyclic, deleting edge k from G yields a (connected) tree, and therefore a bipartite graph. We let $V_+$ denote set of nodes in the part that contains both endpoints of edge k (that both endpoints belong to the same part follows from the fact that the cycle is odd) and $V_-$ the set of nodes in the other part. We obtain

$$ \sum_{i \in V_+} \lambda_i - \sum_{i \in V_-} \lambda_i = \sum_{i \in V_+} \sum_{\ell \in E_i} \mu_\ell - \sum_{i \in V_-} \sum_{\ell \in E_i} \mu_\ell = 2\mu_k. $$

The first equality follows from (CE-1). The second equality holds because each edge $\ell \in E \setminus \{k\}$ has one endpoint in $V_+$ and another in $V_-$, so that $\mu_\ell$ appears once in the first nested sum and once in the second; on the contrary, since both endpoints of edge k belong to $V_+$, $\mu_k$ appears twice in the first nested sum and zero times in the second. Equation (14) follows by observing that $d_{i,k}$ is even if and only if $i \in V_+$.

$\blacksquare$

We remark that the influence of the arrival rate of a node on the matching rate along an edge only depends on the parity of the distance between the edge and the node. The actual distance does not. In particular, even in a very large (bijective) graph, a node far away from an edge has the same (although possibly reversed) impact on this edge's matching rate as an endpoint of this edge.

<figure><img src="image_21.png" /><figcaption>(a) Matching rates in the pentagon graph $C_5$. Only rate $\mu_{1,2}$ is shown for ease of display. The other rates are deduced by permutation.</figcaption></figure>

<figure><img src="image_22.png" /><figcaption>(b) Matching rates in a “lying puppet” graph with $n = 9$ nodes and $m = 9$ edges. The differences $\lambda_7 = \lambda_7 - \lambda_8 - \lambda_9$, $\bar{\lambda}_4 = \lambda_4 - \lambda_5 - \lambda_6 - \bar{\lambda}_7$, and $\bar{\lambda}_3 = \lambda_3 - \bar{\lambda}_4$ are the residual rates that classes 7, 4, and 3 provide to their neighbors of lower index.</figcaption></figure>

<caption>■ Figure 4 Matching rates in bijective graphs.</caption>
this assumption, and with $\beta = \frac{1}{2}(\lambda_2 + \lambda_3 - \lambda_1 - \lambda_4) = \frac{1}{2}(\lambda_2 + \lambda_3) - \frac{1}{4}$, $\bar{\lambda}_2 = \lambda_2 - \beta$, and $\bar{\lambda}_3 = \lambda_3 - \beta$, the general solution of (CE) can be described with a parameter $\alpha$ as shown in Figure 6. After subtracting $\beta$ from $\lambda_2$ and $\lambda_3$, the solutions of (CE) for all edges but $\{2, 3\}$ are exactly the same as in the square graph of Example 3.12.

<figure><img src="image_11.png" /><figcaption>Figure 6 Matching rates in the diamond graph with the normalization $\lambda_1 + \lambda_4 = \frac{1}{2}$. $2\beta = \lambda_2 + \lambda_3 - \lambda_1 - \lambda_4 = \lambda_2 + \lambda_3 - \frac{1}{2}$ is the difference between the arrival rates of the inner part $\{2, 3\}$ and the outer part $\{1, 4\}$. $\bar{\lambda}_2 = \lambda_2 - \beta$ and $\bar{\lambda}_3 = \lambda_3 - \beta$ represent the residual rates that classes 2 and 3 can provide to classes 1 and 4, and they are such that $\lambda_1 + \lambda_4 = \bar{\lambda}_2 + \bar{\lambda}_3 = \frac{1}{2}$, as in Example 3.12.</figcaption></figure>

According to Proposition 3.7(ii), the matching problem $(D, \lambda)$ is stabilizable if and only if

$$ \lambda_2 < \lambda_1 + \lambda_3 + \lambda_4, \quad \lambda_3 < \lambda_1 + \lambda_2 + \lambda_4, \quad \lambda_1 + \lambda_4 < \lambda_2 + \lambda_3, \quad (13) $$

that is, $\bar{\lambda}_3 > 0$, $\bar{\lambda}_2 > 0$, and $\beta > 0$. If these inequalities are satisfied, the positive solutions correspond to values of $\alpha$ such that $-2\min(\lambda_1\bar{\lambda}_2, \bar{\lambda}_3\lambda_4) < \alpha < 2\min(\lambda_1\bar{\lambda}_3, \bar{\lambda}_2\lambda_4)$. Intuitively, compared to the square graph, stabilizable matching problems $(D, \lambda)$ have a positive difference of $2\beta$ between the arrival rates of the inner part $\{2, 3\}$ and the outer part $\{1, 4\}$. This difference is absorbed by the central edge $\{2, 3\}$, which has matching rate $\beta$.

Like Example 3.10 and unlike Example 3.11, the matching model $(D, \lambda, \Phi)$ is stable for every greedy policy $\Phi$ provided that (13) is satisfied (this will be shown in Corollary A.2).

**Example 3.14 (Kayak paddle graph).** Figure 7 shows a kayak paddle $G = KP_{3,3,1}$, consisting of two triangles linked by an edge. According to Proposition 3.7, the matching problem $(G, \lambda)$ is stabilizable if and only if there exists $\alpha > 0$ such that $(\lambda_1, \lambda_2, \lambda_3 - \alpha)$ and $(\lambda_4 - \alpha, \lambda_5, \lambda_6)$ are the vectors of arrival rates of two stabilizable triangle graphs $C_3$.

The solutions of (CE) can be described by varying $\alpha$ as shown in Figure 7. Assuming that the matching problem $(G, \lambda)$ is stabilizable, the solutions of (CE) with positive coordinates correspond to the values of $\alpha$ such that

$$ 0 < \alpha < \min(\lambda_3 - |\lambda_2 - \lambda_1|, \lambda_4 - |\lambda_5 - \lambda_6|). $$

Intuitively, solutions with positive coordinates have a positive matching rate $\alpha$ along edge $\{3, 4\}$. After subtracting this rate from $\lambda_3$ and $\lambda_4$, the subgraphs restricted to nodes 1, 2, and 3 and to nodes 4, 5, and 6, respectively, behave like the triangle of Figure 3.

Like Example 3.11 and unlike Examples 3.10 and 3.13, the fact that $(G, \lambda)$ is stabilizable does not guarantee the stability of all greedy policies.

# 4 Matching rates in bijective graphs

In the remainder, we will consider exclusively compatibility graphs $G$ that are stabilizable. According to Definition 3.1 and Proposition 3.6, this implies that the graph $G$ is surjective, or equivalently, that each connected component of $G$ is non-bipartite. According to Proposition 3.5(iv) and Proposition 3.7, there are only two possible cases:
**► Example 6 (Cycle graph with 5 nodes).** A cycle graph is the simplest bijective graph that we can consider, as it contains an odd cycle and no other edges. In the cycle graph of Figure 4a, a direct application of Proposition 9ii yields $\mu_{1,2} = \frac{1}{2}(\lambda_1 + \lambda_2 - \lambda_3 + \lambda_4 - \lambda_5)$, as we have $d_{1,\{1,2\}} = d_{2,\{1,2\}} = 0$, $d_{3,\{1,2\}} = d_{5,\{1,2\}} = 1$, and $d_{4,\{1,2\}} = 3$; regarding node 3 for instance, the endpoint of edge $\{1,2\}$ that is closest to node 3 is node 2, hence $d_{3,\{1,2\}}$ is equal to the distance between nodes 2 and 3, which is 1. Matching rates along other edges follow by symmetry. From the point of view of edge $\{1,2\}$, we can partition nodes into two sets, namely $\{1,2,4\}$ and $\{3,5\}$. The former (resp. latter) set contains nodes at an even (resp. odd) distance of edge $\{1,2\}$, and increasing the arrival rate of these nodes increases (resp. decreases) the matching rate along edge $\{1,2\}$.

**► Example 7 (Lying puppet).** We now consider the graph of Figure 4b. Edges $\{1,2\}$, $\{1,3\}$, and $\{2,3\}$ belong to the cycle, and the other edges do not. According to Proposition 9, we have

$$ \mu_{1,2} = \frac{\lambda_1 + \lambda_2 - \bar{\lambda}_3}{2}, \qquad \mu_{1,3} = \frac{\lambda_1 - \lambda_2 + \bar{\lambda}_3}{2}, \qquad \mu_{2,3} = \frac{-\lambda_1 + \lambda_2 + \bar{\lambda}_3}{2}, $$

where $\bar{\lambda}_3 = \lambda_3 - \mu_{3,4}$, and

$$ \begin{aligned} \mu_{4,5} &= \lambda_5, & \mu_{4,6} &= \lambda_6, & \mu_{7,8} &= \lambda_8, \\ \mu_{7,9} &= \lambda_9, & \mu_{4,7} &= \lambda_7 - \mu_{7,8} - \mu_{7,9}, & \mu_{3,4} &= \lambda_4 - \mu_{4,5} - \mu_{4,6} - \mu_{4,7}. \end{aligned} $$

This second set of equations can be obtained either by a direct application of (13) or by applying (CE-1) recursively from the leaves. Indeed, applying (CE-1) to nodes 5, 6, 8, and 9 gives directly the values of $\mu_{4,5}$, $\mu_{4,6}$, $\mu_{7,8}$, and $\mu_{7,9}$, then applying (CE-1) to node 7 gives the value of $\mu_{4,7}$, and finally applying (CE-1) to node 4 gives the value of $\mu_{3,4}$. The values of $\mu_{1,2}$, $\mu_{1,3}$, and $\mu_{2,3}$ are similar to Example 2, where the arrival rate $\lambda_3$ is again replaced with the effective arrival rate $\bar{\lambda}_3$ from the point of view of classes 1 and 2.

# 5 Polytope of solutions in surjective-only graphs.

Section 4 considered the case where the compatibility graph $G$ was bijective, so that the vector of matching rates for any stable policy was the unique solution to (CE). Let us now assume that $G$ is surjective-only, meaning that: each connected component of $G$ contains at least one odd cycle; at least one component contains either an even cycle or a pair of odd cycles (cf. Definitions 2, 3, and 5). In this case, the solution set of (CE) is infinite. The matching rate vector under any stable policy belongs to this set and has non-negative coordinates.

To better control the matching rates, we first need to understand the structure of the solution set of (CE). To this end, Section 5.1 generalizes the earlier examples from Section 3.4 by systematically characterizing the affine space of all real-valued solutions to (CE). Following this, Section 5.2 describes the convex polytope formed by the solutions with non-negative coordinates, in particular its vertices, that is its extreme points. Whether these solutions can be achieved through a stable matching policy is explored in Section 6.

## 5.1 Affine space of real-valued solutions.

We first consider the set of solutions to (CE) with real-valued (positive, zero, or negative) coordinates:

$$ \Pi = \{\mu \in \mathbb{R}^m : A\mu = \lambda\}. \qquad (16) $$
<figure><img src="image_12.png" /><figcaption>Figure 7 Matching rates in the kayak paddle $KP_{3,3,1}$.</figcaption></figure>

1. If $n = m$, the graph $G$ is also bijective: each connected component of the graph $G$ is a unicyclic graph, and its (only) cycle is odd. The conservation equation (CE) has a unique solution given by $\mu = A^{-1}\lambda$. If all components of this solution are positive, then the matching problem $(G, \lambda)$ is stabilizable, and the solution provides the matching rates achievable by any stable policy.

2. If $n < m$, the graph $G$ is surjective-only: each connected component of the graph $G$ is non-bipartite, and at least one of these connected components contains an even cycle or a pair of odd cycles. The conservation equation (CE) has an infinite number of solutions. If one of them has all-positive components, then the matching problem $(G, \lambda)$ is stabilizable. Case 1 is studied in this section, while case 2 will be studied in Sections 5 and 6.

In Proposition 4.1 below, we give a simpler expression for the unique solution $\mu = A^{-1}\lambda$ of (CE) in terms of the arrival rate vector $\lambda$, under the assumption that the graph $G$ is bijective. We assume without loss of generality that the graph $G$ is connected, as otherwise we can consider each connected component independently. Compared to the expression $\mu = A^{-1}\lambda$, the advantage of Proposition 4.1 is twofold: it does not require calculating a matrix inversion, and it highlights the monotonicity of the matching rates with respect to the arrival rates. This result will be illustrated in Examples 4.2 and 4.3.

**Proposition 4.1.** Consider a problem $(G, \lambda)$ with a compatibility graph $G = (V, E)$ that is connected and bijective, and consider an edge $k \in E$.

(i) If edge $k$ does not belong to the (unique odd) cycle of the graph $G$, then edge $k$ separates the graph $G$ into two parts, namely a tree and a unicyclic graph. If $V_k \subset V$ denotes the set of nodes that belong to the tree (including one endpoint of edge $k$), then the matching rate along edge $k$ is given by

$$ \mu_k = \sum_{i \in V_k} (-1)^{d_{i,k}} \lambda_i, \qquad (14) $$

where $d_{i,k}$ is the distance between node $i$ and edge $k$, defined as the minimum distance between node $i$ and an endpoint of edge $k$.

(ii) If edge $k$ belongs to the (unique odd) cycle of the graph $G$, then the matching rate along edge $k$ is given by

$$ \mu_k = \frac{1}{2} \left( \sum_{i \in V} (-1)^{d_{i,k}} \lambda_i \right). \qquad (15) $$

**Proof.** We first prove (14) for every edge $k$ that does not belong to the cycle. As observed in the proposition, each edge $k$ that does not belong to the cycle separates the graph into two parts, one of which is a tree with node set $V_k$; the rooted tree associated with $k$ is obtained
We now delve into the properties of Π. In Section 5.1.1, we recall that Π is an affine space of dimension $d = m - n$ that can be described as a translation of the kernel of the incidence matrix A by a particular solution to (CE). Section 5.1.2 gives examples of particular solutions that can be used. Section 5.1.3 gives an algorithm to construct a basis for the kernel of the incidence matrix using a spanning tree of the graph G.

### 5.1.1 Edge basis, kernel basis.

The following proposition characterizes the solution set Π of (CE) using the incidence matrix of the compatibility graph. Equation (17) shows in particular that, up to translation, this solution set depends only on the structure of the compatibility graph G, while the arrival rate vector $\lambda$ impacts only the translation vector.

**Proposition 10.** Consider a matching problem $(G, \lambda)$ with a surjective-only compatibility graph G, and let A denote the incidence matrix of G. The solution set Π of (CE) is the affine space obtained by translating the kernel $\ker(A)$ of the matrix A by a particular solution $\mu^\circ$ of (CE), that is,

$$ \Pi = \{\mu^\circ + \mu : \mu \in \ker(A)\}. \qquad (17) $$

Furthermore, the vector space $\ker(A)$ and the affine space $\Pi$ have dimension $d = m - n$.

*Proof.* That the set Π is of the form (17) is a well-known result in linear algebra. Definition 2 about surjectivity implies that the rank of A is $n$, and we conclude from the rank-nullity theorem that the nullity of A is $d = m - n$. The affine space Π has the same dimension according to (17). ▶

Thanks to Proposition 10, given a particular solution $\mu^\circ$ of (CE) and a basis $\mathcal{B} = (b_1, b_2, \dots, b_d)$ of $\ker(A)$, we can rewrite the affine space Π as

$$ \Pi = \{\mu^\circ + \alpha_1 b_1 + \alpha_2 b_2 + \dots + \alpha_d b_d : \alpha_1, \alpha_2, \dots, \alpha_d \in \mathbb{R}\}. $$

In fact, we can define the following affine isomorphism between the coordinate space $\mathbb{R}^d$ and the $d$-dimensional affine space Π:

$$ \alpha = (\alpha_1, \alpha_2, \dots, \alpha_d) \in \mathbb{R}^d \mapsto \mu = \mu^\circ + \alpha_1 b_1 + \alpha_2 b_2 + \dots + \alpha_d b_d \in \Pi. \qquad (18) $$

This allows us to define two coordinate systems, edge coordinates and kernel coordinates.

**Definition 11 (Edge basis, kernel basis).** Consider a matching problem $(G, \lambda)$ with a surjective-only graph G. Given a particular solution $\mu^\circ$ of (CE) and a basis $\mathcal{B} = (b_1, b_2, \dots, b_d)$ of $\ker(A)$, there are two natural bases to represent vectors in Π:

- Edge basis: A vector of Π is described by its canonical coordinates $\mu = (\mu_1, \mu_2, \dots, \mu_m) \in \mathbb{R}^m$, solution to (CE), where $\mu_k$ represents a candidate matching rate along edge k, for each $k \in E$.

- Kernel basis: A vector of Π is described by its coordinates $\alpha = (\alpha_1, \alpha_2, \dots, \alpha_d) \in \mathbb{R}^d$ in the basis $\mathcal{B}$, where $d = m - n$ is the dimension of the affine space Π.

If $\mathcal{B}$ is the $m \times d$ matrix giving the coordinates of the vectors of the basis $\mathcal{B}$ in the edge basis, the change-of-basis formulas are as follows:

- A vector of Π with coordinates $\alpha$ in kernel basis has coordinates $\mu = \mu^\circ + B\alpha$ in edge basis;
by designating the corresponding endpoint of edge k as the root. We now prove (14) by induction on the height this rooted tree. Equation (14) is true if the height of this tree is zero. Indeed, in this case, the endpoint of edge k that belongs to the tree, say node i, has no other incident edge, so that applying (CE-1) to node i yields $\mu_k = \lambda_i$, which is consistent with (14). Now assume that the assumption is satisfied for each node whose associated rooted tree has height at most $h-1$ for some $h \ge 0$, and consider an edge k whose associated rooted tree has height h. By applying (CE-1) to the root i of this associated rooted tree, we obtain

$$ \mu_k = \lambda_i - \sum_{\ell \in E_i \setminus \{k\}} \mu_\ell. \qquad (16) $$

The induction hypothesis guarantees that (14) is satisfied for every $\ell \in E_i \setminus \{k\}$ (as the height of the associated rooted tree is at most $h-1$). After injecting this observation to (16), the result for edge k follows by observing that $d_{j,k} = d_{j,\ell} + 1$ for each $\ell \in E_i \setminus \{k\}$ and $j \in V_\ell$, and that $V_k = \{i\} \cup (\cup_{\ell \in E_i \setminus \{k\}} V_\ell)$ (all sets being disjoint).

We now prove (15) for each edge k that belongs to the cycle. Since the graph G is unicyclic, deleting edge k from G yields a (connected) tree, which can be seen as a bipartite graph. We let $V_+$ denote set of nodes in the part that contains both endpoints of edge k (that both endpoints belong to the same part follows from the fact that the cycle is odd) and $V_-$ the set of nodes in the other part. We obtain

$$ \sum_{i \in V_+} \lambda_i - \sum_{i \in V_-} \lambda_i = \sum_{i \in V_+} \sum_{\ell \in E_i} \mu_\ell - \sum_{i \in V_-} \sum_{\ell \in E_i} \mu_\ell = 2\mu_k. $$

The first equality follows from (CE-1). The second equality holds because each edge $\ell \in E \setminus \{k\}$ has one endpoint in $V_+$ and another in $V_-$, so that $\mu_\ell$ appears exactly once in the first nested sum and once in the second; on the contrary, since both endpoints of edge k belong to $V_+$, $\mu_k$ appears twice in the first nested sum and zero times in the second. Equation (15) follows by observing that $d_{i,k}$ is even if and only if $i \in V_+$.

We remark that the influence of the arrival rate of a class on the matching rate along an edge only depends on the parity of the distance between the edge and the node. The actual distance does not. In particular, even in a very large (bijective) graph, a node far away from an edge has the same (although possibly reversed) impact as an endpoint of that edge.

**► Example 4.2 (Cycle graph with 5 nodes).** A cycle graph is the simplest bijective graph that we can consider, as it contains an odd cycle and no other edges. In the cycle graph of Figure 8, a direct application of Proposition 4.1(ii) yields

$$ \mu_{1,2} = \frac{1}{2}(\lambda_1 + \lambda_2 - \lambda_3 + \lambda_4 - \lambda_5). $$

Matching rates along other edges follow by symmetry. From the point of view of edge $\{1,2\}$, we can partition nodes into two sets, namely $\{1,2,4\}$ and $\{3,5\}$. The former (resp. latter) set contains nodes at an even (resp. odd) distance of edge $\{1,2\}$, and increasing the arrival rate of these nodes increases (resp. decreases) the matching rate along edge $\{1,2\}$.

**► Example 4.3 (Lying puppet).** We now consider the graph of Figure 9. Edges $\{1,2\}$, $\{1,3\}$, and $\{2,3\}$ belong to the cycle, and the other edges do not. According to Proposition 4.1, we have

$$ \mu_{1,2} = \frac{\lambda_1 + \lambda_2 - \bar{\lambda}_3}{2}, $$

$$ \mu_{1,3} = \frac{\lambda_1 - \lambda_2 + \bar{\lambda}_3}{2}, $$

$$ \mu_{2,3} = \frac{-\lambda_1 + \lambda_2 + \bar{\lambda}_3}{2}, $$
A vector of $\Pi$ with coordinates $\mu$ in edge basis has coordinates $\alpha = B^{+}(\mu - \mu^{\circ})$ in kernel basis, where $B^{+}$ is the pseudo-inverse $^9$ (or Moore-Penrose inverse) of $B$.

Both bases have advantages. The edge basis, by definition, gives directly the candidate matching rates. The kernel basis allows us to work in lower dimension ($d$ instead of $m$) and to ignore the conservation equation (CE), which is implicitly enforced. In the remainder, we will often use interchangeably the edge coordinates $\mu = (\mu_1, \mu_2, \dots, \mu_m)$ and the kernel coordinates $\alpha = (\alpha_1, \alpha_2, \dots, \alpha_d)$ to describe a given vector in $\Pi$. Which basis we are actually using will be made clear by our choice of letters (either $\mu$ or $\alpha$).

For graphs that have a low kernel dimension $d$, it is convenient to mix both approaches by representing a generic vector of $\Pi$, i.e., a generic solution to (CE), in the form $\mu^{\circ} + \alpha_1 b_1 + \alpha_2 b_2 + \dots + \alpha_d b_d$. The solutions in Examples 4 and 5 displayed in Figures 3d and 3e follow this convention. This representation, along with the possibility to switch between edge basis and kernel basis, will be used extensively in Sections 5.2 and 6.

## 5.1.2 Particular solution.

We propose two ways of computing a particular solution to (CE).

### Maximin solution.

A solution to the linear optimization problem (10) from Section 3.3.2 is a particular solution. Recall that such a solution allows us to determine whether the matching problem $(G, \lambda)$ is stabilizable by checking if all its coordinates are positive.

### Pseudoinverse.

Alternatively, a standard approach to simultaneously finding a particular solution $\mu^{\circ}$ and characterizing $ker(A)$ makes use of the pseudoinverse (or Moore-Penrose inverse) of the matrix $A$. Since Definition 2 on surjectivity implies that the rows of $A$ are linearly independent, the pseudoinverse $A^{+}$ of $A$ has the following simple form:

$$A^{+} = A^{\mathrm{T}}(AA^{\mathrm{T}})^{-1},$$

where the $n \times n$ matrix $AA^{\mathrm{T}}$ is invertible because $ker(AA^{\mathrm{T}}) = ker(A^{\mathrm{T}}) = \{0\}$. We can then describe a particular solution $\mu^{\perp}$ and the kernel $ker(A)$ as follows:

$$\mu^{\perp} = A^{+}\lambda, \qquad \ker(A) = \{(\mathrm{Id}_{m \times m} - A^{+}A)\mu : \mu \in \mathbb{R}^{m}\}, \qquad (19)$$

where $\mathrm{Id}_{m \times m}$ denotes the $m$-dimensional identity matrix. The vector $\mu^{\perp}$ is the least-squares solution to (CE), and it is orthogonal to $ker(A)$. In general, some coordinates of this solution can be negative even if non-negative solutions exist. For example, if $G$ is the diamond graph $D$ of Example 4, then the matching problem $(D, \lambda)$ with $\lambda = (4, 5, 2, 1)$ is stabilizable ($\mu = (\frac{7}{2}, \frac{1}{2}, 1, \frac{1}{2}, \frac{1}{2})$ is a solution to (CE) with positive coordinates), but the solution given by the pseudoinverse is $\mu^{\perp} = (\frac{11}{4}, \frac{5}{4}, 1, \frac{5}{4}, -\frac{1}{4})$.

Equation (19) shows that the pseudoinverse also provides an implicit characterization of $ker(A)$, though this is not very practical, as it relies on a projection from $\mathbb{R}^m$ to $ker(A)$. Section 5.1.3 offers a more direct characterization by constructing a basis for $ker(A)$ based on the structure of the compatibility graph $G$.

<footnote n="9">⁹ The columns of the matrix $B$ are linearly independent because $B$ is a basis, so that the pseudo-inverse $B^{+}$ has the simple expression $B^{+} = (B^{\mathrm{T}}B)^{-1}B^{\mathrm{T}}$, where the $d \times d$ matrix $B^{\mathrm{T}}B$ is invertible because $ker(B^{\mathrm{T}}B) = ker(B) = \{0\}$.</footnote>
<figure><img src="image_13.png" /><figcaption>Figure 8 Matching rates in the pentagon graph $C_5$. Only rate $\mu_{1,2}$ is shown for ease of display. The other rates are deduced by permutation.</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>Figure 9 Matching rates in a “lying puppet” graph with $n = 9$ nodes and $m = 9$ edges. The differences $\bar{\lambda}_7 = \lambda_7 - \lambda_8 - \lambda_9$, $\bar{\lambda}_4 = \lambda_4 - \lambda_5 - \lambda_6 - \lambda_7$, and $\bar{\lambda}_3 = \lambda_3 - \bar{\lambda}_4$ are the residual rates that classes 7, 4, and 3 provide to their neighbors of lower index.</figcaption></figure>

where $\bar{\lambda}_3 = \lambda_3 - \mu_{3,4}$, and

$$\mu_{4,5} = \lambda_5,$$

$$\mu_{4,6} = \lambda_6,$$

$$\mu_{7,8} = \lambda_8,$$

$$\mu_{7,9} = \lambda_9,$$

$$\mu_{4,7} = \lambda_7 - \mu_{7,8} - \mu_{7,9},$$

$$\mu_{3,4} = \lambda_4 - \mu_{4,5} - \mu_{4,6} - \mu_{4,7}.$$

This second set of equations can be obtained either by a direct application of (14) or by applying (CE-1) recursively from the leaves. Indeed, applying (CE-1) to nodes 5, 6, 8, and 9 gives directly the values of $\mu_{4,5}$, $\mu_{4,6}$, $\mu_{7,8}$, and $\mu_{7,9}$, then applying (CE-1) to node 7 gives the value of $\mu_{4,7}$, and finally applying (CE-1) to node 4 gives the value of $\mu_{3,4}$. The values of $\mu_{1,2}$, $\mu_{1,3}$, and $\mu_{2,3}$ are similar to Example 3.11, where the arrival rate $\lambda_3$ is again replaced with the effective arrival rate $\bar{\lambda}_3$ from the point of view of classes 1 and 2.

## 5 Solution of the conservation equation in surjective-only graphs

Consider a surjective-only compatibility graph $G$. According to Definitions 3.1, 3.2, and 3.4, each connected component of the graph $G$ is non-bipartite, and at least one of these connected components contains an even cycle or a pair of odd cycles. This means that (CE) has an infinite number of solutions. This section describes these solutions. Section 5.1 characterizes the affine space of all real-valued solutions of (CE). Section 5.2 focuses on stabilizable matching problems and describes the convex polytope made of the solutions with non-negative coordinates. Whether or not these solutions are achievable by a matching policy will be discussed in Section 6.
### 5.1.3 Basis of the kernel of the incidence matrix.

Recall that a vector $\mu \in \mathbb{R}^m$ belongs to $\ker(A)$ if and only if $A\mu = 0$, which reads $\sum_{k \in E_i} \mu_k = 0$ for each $i \in V$. In other words, a vector $\mu \in \mathbb{R}^m$ belongs to $\ker(A)$ if and only if, for each $i \in V$, the sum of the coordinates of $\mu$ associated with the edges that are incident to node $i$ is zero. Using this observation, we first give examples of vectors that belong to $\ker(A)$, and then we give an algorithm that generates a basis $\mathcal{B} = (b_1, b_2, \dots, b_d)$ of $\ker(A)$.

First observe that an even cycle, if it exists, is the support of a vector in $\ker(A)$: it suffices to assign alternatively the values +1 and -1 to the edges of this cycle and the value 0 to all other edges. In the diamond graph of Example 4, if edges are numbered in lexicographical order, then $y = (1, -1, 0, -1, 1)$ is a vector of the unidimensional kernel ($d = m - n = 1$), with support the even cycle 1-2-4-3 (see Figure 5a). Intuitively, even cycles can be used to move weight between “odd” and “even” edges of the cycle without modifying the value of the product $A\mu$. Actually, in this example, Figure 3d shows that the only way to increase the matching rate along edges $\{1, 2\}$ and $\{3, 4\}$ is if we reduce the matching rate along edges $\{1, 3\}$ and $\{2, 4\}$, and conversely.

Apart from even cycles, other structures of interest are kayak paddles $KP_{\ell,r,p}$, made of two odd cycles (of lengths $\ell$ and $r$) connected by a path (of length $p$). Such graphs have a unidimensional kernel, and a base vector can be found by assigning properly the values +1 and -1 along the cycles and the values +2 and -2 along the path. Figure 5b shows such an assignment for $KP_{3,5,2}$.

Surprisingly, for any surjective graph $G$, one can build a basis of $\ker(A)$ using only subgraphs of $G$ that are even cycles and kayak paddles. Algorithm 1, derived from [21], describes such a construction. Appendix C.1 gives a more detailed description of this algorithm and proof that it terminates and returns the desired result.

Figure 6 shows a possible run of Algorithm 1 for the codomino graph: in Figure 6a, a spanning tree $T$ (plain back edges) and a pivotal edge $a$ such that $T \cup \{a\}$ contains an odd cycle (dotted edge) are selected. Then, for each edge $s_i$ that does not belong to $T \cup \{a\}$, we build a base vector of the kernel space with support included into $T \cup \{a, s_i\}$, after observing that $T \cup \{a, s_i\}$ contains either an even cycle or a kayak paddle similar to those shown in Figure 5. Other examples are shown in Appendix C.1.

**Remark 3.** Equation (17) implies that, given an edge $k \in E$, all solutions to (CE) have the same value along edge $k$ if and only if edge $k$ does not belong to the support of any basis vector. According to Algorithm 1, this is equivalent to saying that edge $k$ belongs neither to an even cycle nor to a kayak paddle. In the diamond graph of Example 4 for instance, the edge $\{2, 3\}$ is the only one that does not belong to the even cycle 1-2-4-3, and it is indeed the only one with a fixed rate $\beta$. In general, if an edge $k \in E$ satisfies this unicity condition,

<figure><img src="image_23.png" /><figcaption>(a) Vector of the kernel space of the diamond graph.</figcaption></figure>

<figure><img src="image_24.png" /><figcaption>(b) Vector of the kernel space of the kayak paddle $KP_{3,5,2}$.</figcaption></figure>

<figure><img src="image_25.png" /><figcaption>Figure 5 Base vectors of kernel spaces of two toy graphs.</figcaption></figure>
Note that most of the results stated in this section are also applicable to bijective graphs. However, due to the uniqueness of the solution, which is already provided in a closed-form expression in Section 4, bijective graphs hold limited interest in this context. This is why our focus primarily lies on surjective-only graphs.

## 5.1 Affine space of real-valued solutions

We first consider the set of solutions of (CE) with real-valued (positive, zero, or negative) coordinates:

$$ \Pi = \{\mu \in \mathbb{R}^m : A\mu = \lambda\}. \qquad (17) $$

In the following, we delve into the properties of $\Pi$. In Section 5.1.1, we observe that $\Pi$ is an affine space of dimension $d = m - n$ that can be described as a translation of the kernel of the incidence matrix $A$ by a particular solution of (CE). Section 5.1.2 gives examples of particular solutions that can be used. Section 5.1.3 gives an algorithm to construct a basis for the kernel of the incidence matrix directly from the graph.

### 5.1.1 Edge basis, kernel basis

The following proposition characterizes the solution set $\Pi$ of (CE) using the incidence matrix of the compatibility graph. Equation (18) says that, up to translation, this solution set depends only on the structure of the compatibility graph $G$, while the arrival rate vector $\lambda$ impacts only the translation vector.

**Proposition 5.1.** *Consider a surjective-only compatibility graph $G$, and let $A$ denote the incidence matrix of $G$. The solution set $\Pi$ of (CE) is the affine space obtained by translating the kernel $\ker(A)$ of the matrix $A$ by a particular solution $\mu^\circ$ of (CE), that is,*

$$ \Pi = \{\mu^\circ + \mu : \mu \in \ker(A)\}. \qquad (18) $$

*Furthermore, the vector space $\ker(A)$ and the affine space $\Pi$ have dimension $d = m - n$.*

**Proof.** That the set $\Pi$ is of the form (18) is a well-known result in linear algebra. Definition 3.1 about surjectivity implies that the rank of $A$ is $n$, and we conclude from the rank-nullity theorem that the nullity of $A$ is $d = m - n$. The affine space $\Pi$ has the same dimension according to (18). ◀

Thanks to Proposition 5.1, given a particular solution $\mu^\circ$ of (CE) and a basis $\mathcal{B} = (b_1, b_2, \dots, b_d)$ of $\ker(A)$, we can rewrite the affice space $\Pi$ as

$$ \Pi = \{\mu^\circ + \alpha_1 b_1 + \alpha_2 b_2 + \dots + \alpha_d b_d : \alpha_1, \alpha_2, \dots, \alpha_d \in \mathbb{R}\}. $$

In fact, we can define the following affine isomorphism between the coordinate space $\mathbb{R}^d$ and the $d$-dimensional affine space $\Pi$:

$$ \alpha = (\alpha_1, \alpha_2, \dots, \alpha_d) \in \mathbb{R}^d \mapsto \mu = \mu^\circ + \alpha_1 b_1 + \alpha_2 b_2 + \dots + \alpha_d b_d \in \Pi. \qquad (19) $$

Therefore, given a particular solution $\mu^\circ$ of (CE) and a basis $\mathcal{B} = (b_1, b_2, \dots, b_d)$ of $\ker(A)$, there are two natural bases to represent vectors in $\Pi$:

* **Edge basis:** A vector of $\Pi$ is described by its canonical coordinates $\mu = (\mu_1, \mu_2, \dots, \mu_m) \in \mathbb{R}^m$, where $\mu_k$ represents a candidate matching rate along edge $k$, for each $k \in E$.
**Data:** A connected surjective-only compatibility graph $G = (V, E)$

**Result:** A basis $\mathcal{B}$ of the kernel of the incidence matrix $A$ of $G$

1. $\mathcal{T} \leftarrow$ Edges of a spanning tree of $G$

2. $a \leftarrow$ An edge in $E \setminus \mathcal{T}$ such that $\mathcal{T} \cup \{a\}$ contains an odd cycle

3. $\mathcal{B} \leftarrow \emptyset$

4. **for** $s \in E \setminus (\mathcal{T} \cup \{a\})$ **do**

5. Select from $\mathcal{T} \cup \{a, s\}$ an even cycle or a kayak paddle made of two odd cycles

6. Weight the selected edges like in Figure 5 (unselected edges have weight 0)

7. Add resulting kernel vector to $\mathcal{B}$

8. **return** $\mathcal{B}$

**Algorithm 1** High-level description of the construction of a basis of the kernel of the incidence matrix $A$ of a compatibility graph $G$. See Appendix C.1 for detailed description.

<figure><img src="image_26.png" /><figcaption>**Figure 6** A possible execution of Algorithm 1 for the codomino graph.</figcaption></figure>

then the matching rate along edge $k$ in a stable matching model $(G, \lambda, \Phi)$ is independent of the policy $\Phi$. Note that there is no straightforward relation between the number of edges with uniquely-defined matching rates and the dimensionality $d$ of the affine space $\Pi$.

## 5.2 Polytope description

We continue to focus exclusively on matching problems $(G, \lambda)$ that are stabilizable. Let $\Pi_{\ge 0}$ denote the set of solutions to (CE) that have non-negative coordinates, defined as

$$ \Pi_{\ge 0} = \Pi \cap \mathbb{R}_{\ge 0}^m = \{\mu \in \mathbb{R}^m : A\mu = \lambda, \mu \ge 0\}. \quad (20) $$

The set $\Pi_{\ge 0}$ is a $d$-dimensional convex polytope in $\mathbb{R}^m$, as it is the intersection of a $d$-dimensional affine space with the positive orthant $\mathbb{R}_{\ge 0}^m$, both of which are convex. This set $\Pi_{\ge 0}$ is neither empty nor degenerated to a dimension lower than $d$ because the matching problem $(G, \lambda)$ is assumed to be stabilizable, which by Proposition 8 means that $\Pi$ contains a vector with positive coordinates (i.e., in the interior of the positive orthant). It is bounded because each $\mu \in \Pi_{\ge 0}$ satisfies $0 \le \mu_{i,j} \le \min\{\lambda_i, \lambda_j\}$ for each $\{i, j\} \in E$.

Equation (20) describes $\Pi_{\ge 0}$ in the edge basis. As $\Pi_{\ge 0}$ is a subset of $\Pi$, we can also express its elements in the kernel basis introduced in Section 5.1.1. In the kernel basis, $\Pi_{\ge 0}$ is defined by the vectors whose coordinates belong to

$$ \tilde{\Pi}_{\ge 0} = \{\alpha \in \mathbb{R}^d : \mu^0 + \alpha_1 b_1 + \alpha_2 b_2 + \dots + \alpha_d b_d \ge 0\}. \quad (21) $$

As (20) and (21) basically represent the same polytope up to the change-of-basis formulas of Definition 11, in the remainder, we will use the same notation $\Pi_{\ge 0}$ to describe both sets; the underlying basis will be made clear by our choice of letters (as before, $\mu$ for the edge basis and $\alpha$ for the kernel basis).
■ **Kernel basis:** A vector of Π is described by its coordinates $\alpha = (\alpha_1, \alpha_2, \dots, \alpha_d) \in \mathbb{R}^d$ in the basis $\mathcal{B}$, where $d = m - n$ is the dimension of the affine space Π.

Both bases have advantages. The edge basis, by definition, gives directly the candidate matching rates. The kernel basis allows us to work in lower dimension ($d$ instead of $m$) and to ignore the conservation equation (CE), which is implicitly enforced. In the remainder, we will often use interchangeably the edge coordinates $\mu = (\mu_1, \mu_2, \dots, \mu_m)$ and the kernel coordinates $\alpha = (\alpha_1, \alpha_2, \dots, \alpha_d)$ to describe a given vector in Π. Which basis we are actually using will be made clear by our choice of letters (either $\mu$ or $\alpha$).

For graphs that have a low kernel dimension $d$, it is convenient to mix both approaches and to represent a generic vector of Π, i.e., a generic solution of (CE), in the form $\mu^\circ + \alpha_1 b_1 + \alpha_2 b_2 + \dots + \alpha_d b_d$. For instance, the solutions on Examples 3.13 and 3.14 are actually displayed in Figures 6 and 7 using that convention. This representation, along with the possibility to switch between edge basis and kernel basis, will be used extensively in Sections 5.2 and 6.

► **Remark 5.2 (Change-of-basis formulas).** If $\mathcal{B}$ is the $m \times d$ matrix giving the coordinates of the vectors of the basis $\mathcal{B}$ in the edge basis, the change-of-basis formulas are as follows:

■ A vector of Π with coordinates $\alpha$ in kernel basis has coordinates $\mu^\circ + B\alpha$ in edge basis;

■ A vector of Π with coordinates $\mu$ in edge basis has coordinates $B^+(\mu - \mu^\circ)$ in kernel basis, where $B^+$ is the pseudo-inverse (or Moore-Penrose inverse) of $\mathcal{B}$.

The columns of the matrix $\mathcal{B}$ are linearly independent because $\mathcal{B}$ is a basis, so that the pseudo-inverse $B^+$ has the simple expression $B^+ = (B^\top \mathcal{B})^{-1} B^\top$, where the $d \times d$ matrix $B^\top \mathcal{B}$ is invertible because $\ker(B^\top \mathcal{B}) = \ker(\mathcal{B}) = \{0\}$.

### 5.1.2 Particular solution

We briefly discuss the derivation of a particular solution $\mu^\circ$ of (CE), which can be used as an origin for Π. The choice of a basis $\mathcal{B}$ of the kernel of the incidence matrix of the compatibility graph $\mathcal{G}$ will be discussed in Section 5.1.3.

#### Pseudoinverse

A standard way to simultaneously find a particular solution $\mu^\circ$ and characterize $\ker(A)$ consists of using the pseudoinverse (or Moore-Penrose inverse) of the matrix $A$. Definition 3.1 about surjectivity implies that the rows of $A$ are linearly independent, so that the pseudoinverse $A^+$ of $A$ has the following simple expression:

$$A^+ = A^\top (A A^\top)^{-1},$$

where the $n \times n$ matrix $A A^\top$ is invertible because $\ker(A A^\top) = \ker(A^\top) = \{0\}$. We can then describe a particular solution $\mu^\perp$ and the kernel $\ker(A)$ as follows:

$$\mu^\perp = A^+ \lambda, \quad \ker(A) = \{(\mathrm{Id}_{m \times m} - A^+ A)\mu : \mu \in \mathbb{R}^m\}, \quad (20)$$

where $\mathrm{Id}_{m \times m}$ is the $m$-dimensional identity matrix. The vector $\mu^\perp$ is the least-squares solution of (CE), and it is orthogonal to $\ker(A)$. In general, some coordinates of this solution can be negative even if non-negative solutions exist. For example, if $\mathcal{G}$ is the diamond graph $\mathcal{D}$ of Example 3.13, then the matching problem $(\mathcal{D}, \lambda)$ with $\lambda = (4, 5, 2, 1)$ is stabilizable ($\mu = (\frac{7}{2}, \frac{1}{2}, 1, \frac{1}{2}, \frac{1}{2})$ is a positive solution), but the solution given by the pseudoinverse is $\mu^\perp = (\frac{11}{4}, \frac{5}{4}, 1, \frac{5}{4}, -\frac{1}{4})$.

Equation (20) shows that the Moore-Penrose inverse also provides an implicit characterization of $\ker(A)$. However, this characterization is not very practical as it relies on a projection from $\mathbb{R}^m$ to $\ker(A)$. In Section 5.1.3, we will give a more direct characterization by building a basis for $\ker(A)$ based on the structure of the compatibility graph $\mathcal{G}$.
<figure><img src="image_27.png" /><figcaption>■ **Figure 7** Matching problem $(G, \lambda)$, where $G$ is the codomino graph and $\lambda = (2, 3, 3, 2, 3, 3) \in \mathbb{R}^6$.</figcaption></figure>

### 5.2.1 Vertex characterization

The vertices of a convex polytope, also known as its corners or extreme points, are instrumental in optimization, which will be the object of Section 6. Definition 12 provides the formal definitions of vertices, along with faces and facets.

**Definition 12 (Vertices, faces, and facets; adapted from [42]).** Let $\Upsilon$ denote a convex polytope of dimension $d \in \mathbb{N}_{\ge 0}$. A (non-empty) face of $\Upsilon$ is a non-empty intersection of $\Upsilon$ with a hyperplane such that $\Upsilon$ is included into one of the two halfspaces defined by the hyperplane. A vertex of $\Upsilon$ is a face of dimension 0. Equivalently, a vector $\mu \in \Upsilon$ is a vertex of $\Upsilon$ if, and only if, it cannot be written as a convex combination of points in $\Upsilon \setminus \{\mu\}$. A facet of $\Upsilon$ is a face of dimension $d-1$.

Proposition 13 below gives a simple yet powerful characterization of the vertices of $\Pi_{\ge 0}$.

**Proposition 13.** Consider a vector $\mu \in \Pi_{\ge 0}$. Let $E^* = \{k \in E : \mu_k > 0\}$ denote the support of the vector $\mu$ and $G^* = (V, E^*)$ its support graph. The following statements are equivalent:

(i) The vector $\mu$ is a vertex of $\Pi_{\ge 0}$.

(ii) The graph $G^*$ is injective.

In particular, if $\mu$ is a vertex, we can distinguish two cases depending on the value of $|E^*|$:

1. If $|E^*| = n$ then $G^*$ is bijective.

2. If $|E^*| < n$ then $G^*$ is injective-only.

With a slight abuse of notation, we say that a vertex $\mu \in \Pi_{\ge 0}$ is bijective (resp. injective-only) if the support graph $G^*$ of $\mu$ is bijective (resp. injective-only).

**Proof (borrowed from [15]).** See Appendix C.2. ▼

<figure><img src="image_28.png" /></figure>

Figures 7 and 8 shows $\Pi_{\ge 0}$ for the codomino graph. In each figure, the left part displays a generic solution to (CE) on the graph, while the right part shows the polytope $\Pi_{\ge 0}$ and its vertices in the kernel basis. In Figure 7, $\Pi_{\ge 0}$ has five vertices. The vertex $\alpha = (0, 1)$ is bijective, as $|E^*| = |E \setminus \{\{2, 3\}, \{5, 6\}\}| = 6$. One can verify that the remaining four vertices are injective-only (as at least three edge coordinates are null). In Figure 8, $\Pi_{\ge 0}$ has three vertices, all of which are bijective.

For further details, we encourage the reader to consult Appendix C.3, which provides additional results on the relationships between vertex properties and the edge positivity inequalities from Equation (21), along with more detailed examples of polytopes and their vertices.
### Maximin solution

Alternatively, we can utilize a maximin solution by solving the linear optimization problem (11). Recall that the maximin solution allows us to verify if the matching problem $(G, \lambda)$ is stabilizable by checking if all edge coordinates of $\mu^\circ$ are positive.

#### 5.1.3 Basis of the kernel of the incidence matrix

Recall that a vector $y \in \mathbb{R}^m$ belongs to $\ker(A)$ if and only if $Ay = 0$, which reads $\sum_{k \in E_i} y_k = 0$ for each $i \in V$. In other words, a vector $y \in \mathbb{R}^m$ belongs to $\ker(A)$ if and only if, for each $i \in V$, the sum of the coordinates of $y$ associated with the edges that are incident to node $i$ is zero. Using this observation, we first give examples of subgraphs that are supports of vectors that belong to $\ker(A)$, and then we give an algorithm that generates a basis $B = (b_1, b_2, \dots, b_d)$ of $\ker(A)$.

First observe that an even cycle, if it exists, is the support of a vector in $\ker(A)$: it suffices to assign alternatively the values +1 and -1 to the edges of this cycle and the value 0 to all other edges. In the diamond graph of Example 3.13 for instance, if edges are numbered in lexicographical order, then $y = (1, -1, 0, -1, 1)$ is a vector of the unidimensional kernel, associated with the even cycle 1-2-4-3 (see Figure 10). Intuitively, even cycles can be used to move weights between “odd” and “even” edges without modifying the value of the product $Ay$. Actually, in this particular example, we can see on Figure 6 that the only way to increase the matching rate along edges {1,2} and {3,4} is if we reduce the matching rate along edges {1,3} and {2,4}, and conversely.

<figure><img src="image_15.png" /><figcaption>Figure 10 Vector of the kernel space of the diamond graph.</figcaption></figure>

Apart from even cycles, other structures of interest are kayak paddles $KP_{\ell,r,p}$ in which the lengths $\ell$ and $r$ of both cycles are odd. These graphs have a unidimensional kernel, and a base vector can be found by assigning properly the values +1 and -1 along the cycles and the values +2 and -2 along the path. Figure 11 shows such an assignment for $KP_{3,5,2}$.

<figure><img src="image_16.png" /><figcaption>Figure 11 Vector of the kernel space of the kayak paddle $KP_{3,5,2}$.</figcaption></figure>

Surprisingly, for any surjective graph $G$, one can build a basis of $\ker(A)$ using only subgraphs of $G$ that are even cycles and kayak paddles. This is what Algorithm 1 does. It
<figure><img src="image_29.png" /><figcaption>Figure 8 Matching problem $(G, \lambda)$, where $G$ is the codomino graph and $\lambda = (4, 4, 3, 4, 3, 4) \in \mathbb{R}^6$.</figcaption></figure>

### 5.2.2 Probability of bijectivity

Section 6 will show that the bijectivity of vertices is central for optimizing the matching rates achieved by a stable policy. It is thus natural to wonder how frequent (or rare) bijective vertices are. Proposition 14 gives a part of the answer.

**Proposition 14.** Let $G$ be a surjective-only graph, and assume that the arrival rate vector $\lambda$ is drawn according to a positive Lebesgue density over $\Delta^{n-1}$, the standard simplex of $\mathbb{R}^n$. Then,

$$ \mathbb{P}(\text{All vertices of } \Pi_{\ge 0} \text{ are bijective}|(G, \lambda) \text{ stabilizable}) = 1. $$

**Proof.** See Appendix C.4.

<figure><img src="image_30.png" /></figure>

Proposition 14 suggests that under random arrival rates, the polytope $\Pi_{\ge 0}$ is likely to have only bijective vertices. This result also holds if each coordinate of $\lambda$ follows a continuous, independent probability distribution, provided that the distribution's projection on $\Delta^{n-1}$ has a positive measure and includes at least one vector $\lambda$ for which $(G, \lambda)$ is stabilizable. In practice, injective-only vertices may still occur, especially when the coordinates of $\lambda$ display certain regularities, such as being proportional to node degrees (as in Figure 7). Moreover, injective-only vertices offer unique theoretical challenges worth exploring.

In a sense, Proposition 14 resembles the statement *with probability 1, a square matrix is invertible*: while generally true under suitable conditions, this does not imply that non-invertible matrices can be ignored.

## 6 Stable policy optimization.

In Section 5, we identified the matching rate vectors $\mu$ that may be achieved by a stable policy when the compatibility graph $G$ is surjective-only. We now build on these results to characterize and optimize the performance *actually* achieved by stable policies.

The remainder of this section is organized as follows. Section 6.1 introduces our two main performance metrics—*delay* and *regret*. Section 6.2 recalls that optimizing linear rewards amounts to reaching a vertex of the polytope. We show that when the vertex is bijective, the optimal solution is trivially achieved by a stable policy; in contrast, if the vertex is injective-only, no stable policy can achieve it. Section 6.3 presents $\epsilon$-filtering, a parameterized policy that can get arbitrarily close to a vertex, even when it is injective-only, with a guaranteed trade-off in performance. Finally, Section 6.4 relates our results to the most recent work on matching policy optimization.
first identifies an edge set $E \setminus (T \cup \{a\})$ of cardinality $d = m - n$, where $T$ is a spanning tree of the graph $G$ and $a$ is an edge in $E \setminus T$ such that $T \cup \{a\}$ contains an odd cycle. Then, for each edge $s \in E \setminus (T \cup \{a\})$, the algorithm builds a base vector $b$ whose support (i) is either an even cycle or a kayak paddle and (ii) contains $s$ and is included into $T \cup \{a, s\}$. We assume without loss of generality that the graph $G$ is connected (in addition to being surjective-only). If not, we can apply the algorithm to each connected component separately, and then we embed the obtained vectors to $\mathbb{R}^n$ via zero padding.

**Data:** A connected surjective-only compatibility graph $G = (V, E)$

**Result:** A basis $\mathcal{B}$ of the kernel of the incidence matrix $A$ of $G$

1. $\mathcal{B} \leftarrow \emptyset$

2. $T \leftarrow$ the set of edges of a spanning tree of $G$

3. $a \leftarrow$ an edge in $E \setminus T$ such that $T \cup \{a\}$ contains an odd cycle

4. **for** $s \in E \setminus (T \cup \{a\})$ **do**

5. &nbsp;&nbsp;&nbsp;&nbsp;$b \leftarrow (0, 0, \dots, 0) \in \mathbb{R}^m$

6. &nbsp;&nbsp;&nbsp;&nbsp;**if** $T \cup \{a, s\}$ contains an even cycle $C_\ell$ **then**

7. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$c_1, \dots, c_\ell \leftarrow$ consecutive edges of $C_\ell$

8. &nbsp;&nbsp;&nbsp;&nbsp;**for** $d \in \{1, \dots, \ell\}$ **do**

9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$k \leftarrow$ index of $c_d$ in $E$

10. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$b_k \leftarrow (-1)^d$

11. **else**

12. &nbsp;&nbsp;&nbsp;&nbsp;**T** $\cup \{a, s\}$ contains a kayak paddle $KP_{\ell,r,p}$ with $\ell$ odd, $r$ odd, and $p \ge 0$

13. &nbsp;&nbsp;&nbsp;&nbsp;$v_i \leftarrow$ node connecting the kayak's cycle $C_\ell$ to the kayak central path $P_p$

14. &nbsp;&nbsp;&nbsp;&nbsp;$v_j \leftarrow$ node connecting the kayak's cycle $C_r$ to the kayak central path $P_p$

15. &nbsp;&nbsp;&nbsp;&nbsp;$c_1, \dots, c_\ell \leftarrow$ consecutive edges of $C_\ell$, starting and ending at node $v_i$

16. &nbsp;&nbsp;&nbsp;&nbsp;**for** $d \in \{1, \dots, \ell\}$ **do**

17. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$k \leftarrow$ index of $c_d$ in $E$

18. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$b_k \leftarrow (-1)^d$

19. &nbsp;&nbsp;&nbsp;&nbsp;$c_1, \dots, c_p \leftarrow$ consecutive edges of $P_p$, starting at node $v_i$ and ending at node $v_j$

20. &nbsp;&nbsp;&nbsp;&nbsp;**for** $d \in \{1, \dots, p\}$ **do**

21. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$k \leftarrow$ index of $c_d$ in $E$

22. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$b_k = 2(-1)^{d+1}$

23. &nbsp;&nbsp;&nbsp;&nbsp;$c_1, \dots, c_r \leftarrow$ consecutive edges of $C_r$, starting and ending at node $v_j$

24. &nbsp;&nbsp;&nbsp;&nbsp;**for** $d \in \{1, \dots, r\}$ **do**

25. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$k \leftarrow$ index of $c_d$ in $E$

26. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$b_k \leftarrow (-1)^{d+p+1}$

27. $\mathcal{B} \leftarrow \mathcal{B} \cup \{b\}$

28. **return** $\mathcal{B}$

■ **Algorithm 1** Construction of a basis of the kernel of the incidence matrix $A$ of the compatibility graph $G$. This algorithm was initially introduced in [20, Section 3] to build a basis of the eigenspace associated with the eigenvalue $-2$ of the adjacency matrix of a line graph (i.e., a graph whose nodes and edges represent, respectively, the edges and their incidence relations in another graph).

Figures 12 and 13 show possible runs of Algorithm 1 on the triandum and codomino graphs, which both have a two-dimensional kernel. Note that the basis is not unique and depends on our choice of the spanning tree $T$ and the augmenting edge $a$ (see lines 2 and 3 in Algorithm 1). We now verify that Algorithm 1 terminates and yields the desired result.
## 6.1 Performance criteria.

Delay and regret are our two main performance indicators. Later in this section, we will show that these indicators can sometimes be antagonistic, meaning that certain matching problems may require trade-offs between them.

### Delay.

In a stable matching model $(G, \lambda, \Phi)$, the delay is defined as the long-term average waiting times of the items (with waiting equal to zero if the item is matched immediately upon arrival). By Little's law [31, 32], the delay $D(\Phi)$ is given by

$$D(\Phi) = \frac{\sum_{i \in V} \mathbb{E}[Q_i^\infty]}{\sum_{i \in V} \lambda_i},$$

where $Q^\infty = (Q_1^\infty, Q_2^\infty, \dots, Q_n^\infty)$ is a random vector distributed according to the stationary distribution of the Markov chain $Q = (Q_t, t \in \mathbb{N})$ under policy $\Phi$.

### Regret.

To turn a matching rate vector into a scalar performance metric, we assume that the quality of a matching rate vector can be evaluated by some reward function $f: \mu \in \mathbb{R}^m \to f(\mu) \in \mathbb{R}$. The regret of a policy $\Phi$ is then defined as

$$R(\Phi) = f_{\text{sup}} - f(\mu(\Phi)),$$

where $f_{\text{sup}} = \sup_{\Psi:(G,\lambda,\Psi) \text{ stable}} f(\mu(\Psi))$ is the supremum of the rewards achievable by any stable policy.

Unless otherwise stated, we consider linear reward functions of the form

$$f: \mu \in \mathbb{R}^m \to r^\top \mu,$$

where $r = (r_1, \dots, r_m) \in \mathbb{R}^m$ is a vector of rewards associated with the edges of $G$.

**Remark 4.** In reward-driven analyses of matching models, a single regret metric is commonly used to quantify total reward loss compared to a hindsight-optimal policy. In effect, this global regret encompasses both metrics considered in our study: delay, which reflects queue sizes and is related to short-term regret ([30, Theorem 3.1 and discussion]), and regret as we define it, which coincides with the long-term regret metric in [29, Definition 2.2, Equation (9)].

Delay fundamentally measures the stability of the system. It depends solely on the actual dynamics of the network, irrespective of the reward vector, and is therefore critical in applications such as organ donation, assemble-to-order systems, and online marketplaces, where reducing the waiting time of agents is essential. In contrast, (long-term) regret captures the cumulative shortfall in reward that is due to suboptimal matching decisions. Recognizing this essential difference, which sets up inherent tensions explored in this Section, we deliberately keep these metrics separate throughout our analysis.

As a first example, consider the matching problem in Figure 9 with associated rewards $(1, 1, 1, 0, 0)$, i.e. matches involving class 4 are not rewarded. In this case, one can verify that $r$ is orthogonal to $ker(A)$, so that all stable policies yield the same reward, equal to 5. On the other hand, if matching class-4 items are abandoned and a Match-the-Longest (ML) policy restricted to the triangle $\{1, 2, 3\}$ is applied, the resulting matching model has infinite delay (class 4 items never leave the system) but achieves a higher reward of 6.
<figure><img src="image_17.png" /></figure>

<figure><img src="image_18.png" /><figcaption>(a) Construction A.</figcaption></figure>

<figure><img src="image_19.png" /><figcaption>(b) First vector for A ($KP_{3,3,0}$).</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>(c) Second vector for A ($C_4$).</figcaption></figure>

<figure><img src="image_21.png" /><figcaption>(d) Construction B.</figcaption></figure>

<figure><img src="image_22.png" /><figcaption>(e) First vector for B ($C_4$).</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>(f) Second vector for B ($C_4$).</figcaption></figure>

Figure 12 Two possible constructions of a kernel basis for the triamond graph. Construction A yields the basis vectors $b_1 = (1, -1, -1, -1, 1, 1, 0)$ and $b_2 = (0, 0, 1, 0, -1, -1, 1)$. Construction B yields the basis vectors $b_1 = (-1, 1, 0, 1, 0, 0, -1)$ and $b_2 = (0, 0, -1, 0, 1, 1, -1)$.

**Proposition 5.3.** *Algorithm 1 terminates and returns a basis of the kernel of the incidence matrix A of the compatibility graph G.*

*Proof.* See Appendix B.

<figure><img src="image_24.png" /></figure>

Importantly, equation (18) states that, given an edge $k \in E$, all solutions of (CE) have the same value along edge $k$ if and only if edge $k$ does not belong to the support of any basis vector. According to Algorithm 1, this is equivalent to say that edge $k$ belongs neither to an even cycle nor to a kayak paddle. In the diamond graph of Example 3.13 for instance, the edge $\{2, 3\}$ is the only one that does not belong to the even cycle $1-2-4-3$, and it is also the only one with a fixed value $\beta$. In general, if an edge $k \in E$ satisfies this unicity condition, then the matching rate along edge $k$ in a stable matching model $(G, \lambda, \Phi)$ is independent of the policy $\Phi$. Note that there is no general relation between the number of edges with uniquely-defined matching rates and the dimensionality $d$ of the affine space $\Pi$.

## 5.2 Convex polytope of positive solutions

In the remainder, we will focus exclusively on matching problems $(G, \lambda)$ that are stabilizable. Next, we consider the set $\Pi_{\ge 0}$ of solutions of (CE) that have non-negative coordinates, defined as

$$ \Pi_{\ge 0} = \Pi \cap \mathbb{R}_{\ge 0}^m = \{\mu \in \mathbb{R}^m : A\mu = \lambda, \mu \ge 0\}. \quad (21) $$

The set $\Pi_{\ge 0}$ is a $d$-dimensional convex polytope in $\mathbb{R}^m$, as it is the intersection of a $d$-dimensional affine space with the positive orthant $\mathbb{R}_{\ge 0}^m$, both of which are convex. The set $\Pi_{\ge 0}$ is neither empty nor degenerated to a dimension lower than $d$ because the matching problem $(G, \lambda)$ is assumed to be stabilizable, which means that $\Pi$ contains a vector with positive coordinates (i.e., in the interior of the positive orthant). It is bounded because each $\mu \in \Pi_{\ge 0}$ satisfies $0 \le \mu_k \le \min_{i \in V_k}(\lambda_i)$ for each $k \in E$.