This example highlights the trade-off between maximizing rewards and ensuring system stability, or more generally, keeping the expected total queue length small. The polytope approach provides a systematic way to identify and analyze such trade-offs. For readers specifically interested in reward maximization without stability guarantees, we refer to [29, 30]. In Section 8.3.2, we further demonstrate that the issue illustrated by Figure 9 actually has a simple solution within the hypergraph formalism: the addition of a discarding mono-edge.

<figure><img src="image_31.png" /><figcaption>Figure 9 A matching problem where all stable policies have the same reward if $r = (1, 1, 1, 0, 0)$.</figcaption></figure>

## 6.2 Vertex optimality

We first recall a classical result from convex optimization; namely, a convex optimization problem defined on a convex polytope always admits a vertex of the polytope as solution. More specifically, Proposition 15 states that for optimizing a linear reward function, it is sufficient to be able to reach the vertices of $\Pi_{\ge 0}$. Proposition 16 shows that, most of the time, it is also necessary.

**Proposition 15.** Let $(G, \lambda)$ a stabilizable matching problem with a surjective-only compatibility graph $G$, and let $r = (r_1, \dots, r_m) \in \mathbb{R}^m$ be a vector of rewards associated with the edges of $G$. Consider the problem of finding a solution to (CE) with non-negative components that maximizes the reward rate $r^\top \mu$, and let $F = \{\mu \in \Pi_{\ge 0} : r^\top \mu = \max_{z \in \Pi_{\ge 0}} r^\top z\}$. Then $F$ is a non-empty face of $\Pi_{\ge 0}$. In particular, there exists a vertex $\mu \in \Pi_{\ge 0}$ that maximizes the reward (i.e., $\mu \in F$).

**Proof.** This is a standard result from convex optimization. Since $\Pi_{\ge 0}$ is closed and bounded, there is a maximum $r_{\max}$ among the rewards associated with vectors inside $\Pi_{\ge 0}$. The set $F$ is the intersection of the hyperplane $\{y \in \mathbb{R}^m : r^\top y = r_{\max}\}$ with $\Pi_{\ge 0}$. Therefore, it is a non-empty face of $\Pi_{\ge 0}$. That any non-empty face contains a vertex follows from the lattice structure of the faces of polytopes. ◀

**Proposition 16.** Let $(G, \lambda)$ a stabilizable matching problem with a surjective-only compatibility graph $G$, and let $r \in \Delta^{m-1}$ be a vector of rewards drawn according to a positive Lebesgue density over $\Delta^{m-1}$, the standard simplex of $\mathbb{R}^m$. Let $F = \{\mu \in \Pi_{\ge 0} : r^\top \mu = \max_{z \in \Pi_{\ge 0}} r^\top z\}$ be the set of the optimal matching rate vectors for $r$. Then, with probability 1, $F = \{\mu_r\}$, where $\mu_r$ is a vertex of $\Pi_{\ge 0}$.

**Proof.** As in Proposition 15, the non-empty face $F$ is the intersection of the hyperplane $\{y \in \mathbb{R}^m : r^\top y = \max_{z \in \Pi_{\ge 0}} r^\top z\}$ with $\Pi_{\ge 0}$. If its dimension is more than 0, it contains a 1-dimensional face of $\Pi_{\ge 0}$ (an edge). Let $b \in \mathbb{R}^m \setminus \{0\}$ be a direction of that edge. We have $b^\top r = 0$. The set $\{r \in \Delta^{m-1} : b^\top r = 0\}$, if it exists, has a dimension at most $m-2$, so the probability that $b^\top r = 0$ is 0. As the number of edges of $\Pi_{\ge 0}$ is finite, we conclude that, with
<figure><img src="image_25.png" /><figcaption>(a) Construction A.</figcaption></figure>

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

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

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

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

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

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

Equation (21) 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^\circ + \alpha_1 b_1 + \alpha_2 b_2 + \dots + \alpha_d b_d \ge 0 \}. \quad (22) $$

As Equations (21) and (22) basically represent the same polytope up to the change-of-basis formulas introduced in Section 5.1.1, in the remainder, we will use the same notation $\Pi_{\ge 0}$ to describe both sets; which basis we are (implicitly) using will be made clear by our choice of letters ($\mu$ for the edge basis and $\alpha$ for the kernel basis).

### 5.2.1 Vertices of the convex polytope

Vertices can be informally defined as the corners or extreme points of a convex polytope. Definition 5.4 gives a formal definition of a vertex (as well as those of a face and a facet, which will be useful later).

**Definition 5.4** (Vertices and facets, adapted from [33]). Consider a convex polytope $\Upsilon$ 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, while a facet of $\Upsilon$ is a face of dimension $d-1$. A vertex can also be defined as follows: a vector $y \in \Upsilon$ is a vertex of $\Upsilon$ if, and only if, it cannot be written as a convex combination of points in $\Upsilon \setminus \{y\}$.

The vertices of $\Pi_{\ge 0}$ are important if one wants to optimize a linear function of the matching rate vector, as stated in Proposition 5.5 below. Such optimization problems occur in many applications of dynamic matching systems (see the first example in Section 1.1).

**Proposition 5.5.** Let $w = (w_1, \dots, w_m) \in \mathbb{R}^m$ be a vector of rewards associated with the edges of the compatibility graph. Consider the problem of finding a non-negative solution of (CE) that maximizes the reward rate $w^\top \mu$:

$$ F = \{ \mu \in \Pi_{\ge 0} : w^\top \mu = \max_{z \in \Pi_{\ge 0}} w^\top z \}. \quad (23) $$
probability 1, F does not contain any edge of $\Pi_{\ge 0}$, which means it is reduced to a single vertex. ◀

Building on Propositions 15 and 16, a natural question is: Can a given vertex be achieved by a stable policy? It is answered by Proposition 17.

**Proposition 17.** Let $(G, \lambda)$ be a stabilizable matching problem with a surjective-only compatibility graph $G$. Let $\Pi_P$ be the set of matching rate vectors achieved by stable policies adapted to $(G, \lambda)$, $\mu$ a vertex of the polytope $\Pi_{\ge 0}$ associated to $(G, \lambda)$, and $E^* \subset E$ the support of $\mu$. We distinguish two cases, depending on whether $\mu$ is bijective or injective-only (cf Proposition 13).

(i) If $\mu$ is bijective (meaning that $|E^*| = n$), then $\mu \in \Pi_P$. In fact, $\mu = \mu(\Phi_{E^*})$, where $\Phi_{E^*}$ is the Match-the-Longest (ML) policy adapted to $G$ with a filter on $E^*$, i.e. ML applied to the subgraph $G = (V, E^*)$.

(ii) If $\mu$ is injective-only (meaning that $|E^*| < n$), then $\mu \notin \Pi_P$: no stable policy can achieve $\mu$.

**Proof.** Let $G^* = (V, E^*)$ be the subgraph of $G$ associated with $\mu$, $p = |E^*|$ be the number of positive coordinates of $\mu$, and let $A^*$ denote the $n \times p$ incidence matrix of $G^*$. As $G^*$ is injective (Proposition 13), the restriction $\tilde{\mu}$ of the vector $\mu$ to its positive coordinates is the only solution of the conservation equation $A^* \tilde{z} = \lambda$, of unknown $\tilde{z} \in \mathbb{R}^p$. We now consider the two cases separately:

(i) If $G^*$ is bijective, Proposition 8 implies that the matching problem $(G^*, \lambda)$ is stabilized by the ML policy: $G^*$ is surjective and $\tilde{\mu}$, the unique solution to the conservation equation $A^*z = \lambda$, has positive coordinates. The unicity of $\tilde{\mu}$ ensures that it is the matching rate achieved by that policy. To prove $\mu \in \Pi_P$, we consider the ML policy with a filter on $E^*$ on the matching problem $(G, \lambda)$, denoted $\Phi_{E^*}$. $\Phi_{E^*}$ behaves exactly like the greedy ML policy on $(G^*, \lambda)$, which is stable with matching rate $\tilde{\mu}$, as we just saw. Hence, the model $(G, \lambda, \Phi_{E^*})$ is stable, and its matching rate, which is $\tilde{\mu}$ on $E^*$ and 0 elsewhere, coincides with $\mu$. This proves that $\mu \in \Pi_P$.

(ii) If $G^*$ is injective-only, Proposition 7 implies that the matching problem $(G^*, \lambda)$ is not stabilizable. We prove that $\mu \notin \Pi_P$ by contradiction. Suppose that $\mu \in \Pi_P$, and let $\Phi$ be a stable policy on $(G, \lambda)$ such that $\mu(\Phi) = \mu$. We have $\mu_k(\Phi) = 0$ for each $k \in E \setminus E^*$. But the matching rate $\mu_k(\Phi)$ along an edge $e_k \in E$ with endpoints $i$ and $j$ is also given by

$$ \mu_k(\Phi) = \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(\Phi)$ 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, $\Phi$ also defines a stable policy on the matching problem $(G^*, \lambda)$, which contradicts the instability of the matching problem $(G^*, \lambda)$. Therefore, $\mu \notin \Pi_P$. ◀

Proposition 17 shows that optimizing linear rewards is straightforward when the vertex is bijective: we simply need to forbid the edges outside the support of the vertex. Thus, no inherent trade-off exists between reward maximization and system stability in this case. Note that a trade-off can still exist between optimizing the reward and minimizing the
F is a non-empty face of $\Pi_{\ge 0}$. In particular, there exists a vertex $\mu \in \Pi_{\ge 0}$ that maximizes the reward (i.e., $\mu \in F$).

**Proof.** This is a standard result from convex optimization. The fact that $\Pi_{\ge 0}$ is bounded guarantees the existence of a maximum $r_{\max}$ amongst the rewards associated with vectors inside $\Pi_{\ge 0}$. The set $F$ is the intersection of the hyperplane $\{y \in \mathbb{R}^m : w^T y = r_{\max}\}$ with $\Pi_{\ge 0}$, and it is therefore a non-empty face of $\Pi_{\ge 0}$. The fact that any non-empty face contains a vertex is a consequence of the lattice structure of the faces of polytopes. ◀

The interest of Proposition 5.5 is the following: if for every vertex $\mu$ of $\Pi_{\ge 0}$ one can provide a stable policy $\Phi$ whose matching rate is $\mu$, or is at least arbitrarily close to $\mu$, then we can maximize any linear reward function (or at least get arbitrarily close to the optimal) with a stable policy. Finding such policies will be the main focus of Section 6.2.

Proposition 5.6 below gives a simple yet powerful characterization of the vertices of $\Pi_{\ge 0}$. The proof of this proposition is borrowed from [14].

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

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

(ii) The graph $\underline{G}$ is injective.

**Proof.** We actually prove that the negations of (i) and (ii) are equivalent. Let $\underline{A}$ denote the incidence matrix of $\underline{G}$.

By Definition 5.4, if $\mu$ is not a vertex of $\Pi_{\ge 0}$, there exist $z_1, z_2 \in \Pi_{\ge 0} \setminus \{\mu\}$ and $0 < \theta < 1$ such that $\mu = \theta z_1 + (1 - \theta)z_2$. The coordinates of the vectors $z_1$ and $z_2$ are non-negative, so this equality implies that their supports are included into the support $\underline{E}$ of the vector $\mu$. In particular, if $\underline{\mu}$ and $\underline{z}_1$ denote the restrictions of $\mu$ and $z_1$ to coordinates in $\underline{E}$, respectively, then $\underline{A}\underline{\mu} = \underline{A}\underline{\mu} = \lambda = \underline{A}z_1 = \underline{A}\underline{z}_1$ with $\underline{\mu} \neq \underline{z}_1$, which means that $\underline{G} = (\underline{V}, \underline{E})$ is not injective.

Conversely, if $\underline{G}$ is not injective, there exists a non-zero vector $\underline{z}$ in $\mathbb{R}^{|\underline{E}|}$ such that $\underline{A}\underline{z} = 0$. If we embed $\underline{z}$ into $\mathbb{R}^{|\underline{E}|}$ with zero-padding, we obtain a non-zero vector $z$ such that $Az = 0$, and whose support is included into that of the vector $\mu$. This implies that there exists $\varepsilon > 0$ such that both $\mu - \varepsilon z$ and $\mu + \varepsilon z$ belong to $\Pi_{\ge 0}$. The convex combination $\mu = \frac{1}{2}(\mu - \varepsilon z) + \frac{1}{2}(\mu + \varepsilon z)$ proves that the vector $\mu$ is not a vertex of $\Pi_{\ge 0}$. ◀

Examples of vertices are shown in Figures 14–16 and will be discussed in details later. For now, it is sufficient to observe that, since the subgraph restricted to the support of a vertex is injective, this subgraph is either bijective (as in Figures 14d–14h and 16c–16f) or injective-only (as in Figures 15d–15f and 16g).

Proposition 5.7 below characterizes the stabilizability of the matching problem $(\underline{G}, \lambda)$ for a vertex $\mu$ of $\Pi_{\ge 0}$, and relates it to the existence of a policy that stabilizes the matching problem $(\underline{G}, \lambda)$ and achieves $\mu$.

**Proposition 5.7.** Let $\Pi_{\mathcal{P}}$ be the set of matching rates achieved by stable policies, as defined in Section 3.1:

$$ \Pi_{\mathcal{P}} = \{\mu(G, \lambda, \Phi) : \Phi \text{ is a stable policy adapted to the compatibility graph } G\}. $$

Consider a vertex $\mu$ of $\Pi_{\ge 0}$, and define $\underline{E}$ and $\underline{G}$ as in Proposition 5.6. We distinguish two cases, depending on the value of $p = |\underline{E}|$:

(i) If $p = n$, i.e., exactly $d$ coordinates of the vertex $\mu$ are zero, then the subgraph $\underline{G}$ is bijective and the matching problem $(\underline{G}, \lambda)$ is stabilizable. Moreover, $\mu \in \Pi_{\mathcal{P}}$.
expected sum of queue lengths, as forbidding a subset of edges limits the flexibility of the policy. In contrast, for the injective-only case, optimality requires a trade-off with stability. To navigate this balance between these two key objectives, we now present the so-called $\epsilon$-filtering policies.

## 6.3 $\epsilon$-filtering policy

Given an injective vertex $\mu$ of $\Pi_{\ge 0}$, we now construct a sequence of policies, that we call $\epsilon$-filtering policies, which converge to the vertex $\mu$ as $\epsilon \downarrow 0$ while also upper bounding the expected queue lengths. Note that the distance to $\mu$ and the expected queue length are directly tied to our main scalar performance metrics, namely regret and delay<fnref n="10" />. The principle of these policies is as follows: when a new item arrives, it is marked with low probability as eligible for all matches in $E$. For a match outside $E^*$ to be made, the selected pair must contain at least one such marked item. Marks allow some matches to be made outside $E^*$, which ensures stability. Their low probability ensures that the resulting matching rate vector is close to the target vertex $\mu$.

Formally, given $0 < \epsilon < 1$, we label each incoming arrival by ‘-’ (marked) with probability $\epsilon$ and ‘+’ (unmarked) otherwise, independently of everything else. An item with class $i$ and label $\ell \in \{+, -\}$ is said to have type-$i^\ell$. We denote the number of items of type $i^\ell$ at time $t$ by $Q_{t,i^\ell}$. Thus, the total number of class-$i$ items at time $t$ is $Q_{t,i} = Q_{t,i^+} + Q_{t,i^-}$. Now, we restrict our attention to policies that do not match type-$i^+$ items to type-$j^+$ items for all $\{i, j\} \in E \setminus E^*$. The policies that follow this restriction in the original graph $G$ can be viewed as policies operating on the augmented graph $G' = (V', E')$, with $V' = \{i^\ell : i \in V, \ell \in \{+, -\}\}$ and $E' = E^+ \cup E^\pm \cup E^-$, where

$$E^+ = \{\{i^+, j^+\} : \{i, j\} \in E^*\}, \quad E^\pm = \{\{i^+, j^-\} : \{i, j\} \in E\}, \quad E^- = \{\{i^-, j^-\} : \{i, j\} \in E\}.$$

The arrival-rate vector in the augmented graph is given by $\lambda'_\epsilon \in \mathbb{R}_{\ge 0}^{2n}$ with $\lambda'_{\epsilon, i^+} = (1 - \epsilon)\lambda_i$ and $\lambda'_{\epsilon, i^-} = \epsilon\lambda_i$ for each $i \in V$. An $\epsilon$-filtering policy adapted to $(G, \lambda)$ with filter $E^*$ refers to a policy adapted to $(G', \lambda'_\epsilon)$. For example, an $\epsilon$-filtering ML policy adapted to $(G, \lambda)$ with filter $E^*$ mimics the ML policy adapted to $(G', \lambda'_\epsilon)$. To be more precise, for a given state $q \in \mathbb{R}_{\ge 0}^{2n}$, an incoming item of type $i^\ell$ is matched with a type in the set $\max_{j \in V'} \{i^\ell, j \in E\} \in E^*$.

Note that, for any greedy policy adapted to $(G', \lambda'_\epsilon)$, most of the arrivals are matched using edges in $E^+$, or equivalently $E^*$, as items are labeled ‘+’ with probability $1 - \epsilon$. As $G^*$ is the support graph of the vertex $\mu$, we can then show that such a policy ensures that the matching rate on $\{i^+, j^+\}$ is $O(\epsilon)$ close to $\mu_{i,j}$ for all $\{i, j\} \in E^*$. Next, to bound the expected queue lengths, we define $\delta(G, \lambda)$, the Complete Resource Pooling Gap (CRPG), as follows:

$$\delta(G, \lambda) = \min_{\mathcal{I} \in \mathcal{I}} \left\{ \sum_{j \in V(\mathcal{I})} \lambda_j - \sum_{i \in \mathcal{I}} \lambda_i \right\}. \qquad (22)$$

<footnote n="10">¹⁰ Queue length and delay are related by Little’s law (see Section 2.4). Consider a stable policy $\Phi$ with matching rate $\mu(\Phi) \in \Pi_{\ge 0}$ and regret $R(\Phi)$. We have $R(\Phi) = r^T(\mu - \mu(\Phi)) = \cos(\theta)||r||_2||\mu - \mu(\Phi)||_2$, where $\theta$ denotes the angle between $r$ and $\mu - \mu(\Phi)$. In particular, $R(\Phi) \le ||r||_2||\mu - \mu(\Phi)||_2$: if you are close to $\mu$, your regret is low. Conversely, if $\alpha$ denotes the minimum possible cosine between $r$ and $\mu - \mu'$ for $\mu' \in \Pi_{\ge 0} \setminus \{\mu\}$ (i.e., $\alpha = \min_{\mu' \in \Pi_{\ge 0} \setminus \{\mu\}} \frac{r^T(\mu - \mu')}{||r||_2 ||\mu - \mu'||_2}$), we obtain $R(\Phi) \ge \alpha||r||_2||\mu - \mu(\Phi)||_2$. Therefore, $\alpha||r||_2||\mu - \mu(\Phi)||_2 \le R(\Phi) \le ||r||_2||\mu - \mu(\Phi)||_2$. Note that if $\mu$ is the unique optimal solution (as is often the case; see Proposition 16), then $\alpha > 0$: if you are far from $\mu$, your regret is high.</footnote>
(ii) If $p < n$, i.e., strictly more than $d$ coordinates of the vertex $\mu$ are zero, then the subgraph $\underline{G}$ is injective-only and the matching problem $(\underline{G}, \lambda)$ is not stabilizable. Moreover, $\mu \notin \Pi_{\mathcal{P}}$.

**Proof.** Let $\underline{A}$ denote the incidence matrix of $\underline{G}$. We know from Proposition 5.6 that $\underline{G}$ is injective. In particular, the restriction $\underline{\mu}$ of the vector $\mu$ to its positive coordinates is the only solution of the conservation equation $\underline{A}\underline{z} = \lambda$, of unknown $\underline{z} \in \mathbb{R}^p$. It also follows from Proposition 3.5 that $p \le n$, and that the subgraph $\underline{G}$ is bijective if and only if $p = n$. We now consider the two cases separately:

(i) If $p = n$, then $\underline{G}$ is bijective. Proposition 3.7 implies that the matching problem $(\underline{G}, \lambda)$ is stabilizable, as $G$ is surjective and $\underline{\mu}$ is a solution of the conservation equation $\underline{A}\underline{z} = \lambda$ with positive coordinates. To prove $\underline{\mu} \in \Pi_{\mathcal{P}}$, we consider the *match-the-longest* policy with a filter on $\underline{E}$ on the matching problem $(G, \lambda)$, denoted $\Phi$. $\Phi$ behaves exactly like the greedy *match-the-longest* policy on the matching problem $(\underline{G}, \lambda)$, which is stable with matching rate $\underline{\mu}$ as we just saw. Hence the matching model $(G, \lambda, \Phi)$ is stable and its matching rate $\underline{\mu}(\Phi)$ is necessarily equal to $\underline{\mu}$. This proves that $\underline{\mu} \in \Pi_{\mathcal{P}}$.

(ii) If $p < n$, then $\underline{G}$ is injective-only. Proposition 3.6 implies that the matching problem $(\underline{G}, \lambda)$ is not stabilizable. We prove that $\underline{\mu} \notin \Pi_{\mathcal{P}}$ by contradiction. Suppose that $\underline{\mu} \in \Pi_{\mathcal{P}}$, and let $\Phi$ be a stable policy on the matching problem $(G, \lambda)$ such that $\underline{\mu}(\Phi) = \underline{\mu}$. Since $\underline{\mu}_k(\Phi) = 0$ for each $k \in E \setminus \underline{E}$, we know from Remark 2.5 that $\Phi$ never performs a match supported by an edge in $E \setminus \underline{E}$. Hence, $\Phi$ also defines a stable policy on the matching problem $(\underline{G}, \lambda)$, which contradicts the instability of the matching problem $(\underline{G}, \lambda)$. Therefore, $\underline{\mu} \notin \Pi_{\mathcal{P}}$. $\quad \blacksquare$

In a nutshell, Proposition 5.7 states that the vertices with a bijective support graph can be achieved by stable policies, while those that define an injective-only support graph cannot. This is the first step towards a full characterization of $\Pi_{\mathcal{P}}$, which will be further developed in Section 6.2.

**Remark 5.8.** We can further explore the relationship between vertices and their support graph. Again consider a vertex $\underline{\mu}$ of $\Pi_{\ge 0}$, and define $\underline{G}$ and $\underline{A}$ as in Proposition 5.6. According to Definitions 3.1, 3.2, and 3.4, the subgraph $\underline{G}$ is injective if and only if each connected component of $\underline{G}$ is either a tree or a unicyclic graph with an odd cycle. For each connected component of $\underline{G}$ that is a tree, and therefore a bipartite graph with parts $V_+$ and $V_-$, the existence of vertex $\underline{\mu}$ implies that

$$ \sum_{i \in V_+} \lambda_i = \sum_{i \in V_-} \lambda_i. \qquad (24) $$

This equation follows by summing (CE-1) over the nodes in $V_+$ on the one hand, summing (CE-1) over the nodes in $V_-$ on the other hand, and verifying that the left-hand sides of both equations are equal. In fact, one can verify that the vector $\lambda$ belongs to the image of $\underline{A}$ if and only if $\lambda$ satisfies (24) for each connected component of $\underline{G}$ that is a tree. Note that this condition is void if $\underline{G}$ is bijective because, in this case, none of the connected components of $\underline{G}$ is a tree.

Conversely, one can wonder which injective subgraph $\underline{G}$ of $G$ defines a vertex of $\Pi_{\ge 0}$. Satisfying (24) for each tree connected component of $\underline{G}$ only guarantees the existence of a (unique) solution $z \in \mathbb{R}^p$ to the conservation equation $\underline{A}z = \lambda$. If each component of $z$ is positive, then we indeed obtain a vertex of $\Pi_{\ge 0}$ by embedding $z$ in $\mathbb{R}^m$ with zero padding; otherwise, $\underline{G}$ does not define a vertex of $\Pi_{\ge 0}$.
Note that, by Proposition 8, the matching problem $(G, \lambda)$ is stabilizable if and only if $\delta(G, \lambda) > 0$. Intuitively, $\delta(G, \lambda)$ characterizes the minimum slack between the arrival rate of any independent set $\mathcal{I}$ and its neighbors $V(\mathcal{I})$. The arrival rate of the neighbors acts as a service rate for $\mathcal{I}$, and the CRPG $\delta(G, \lambda)$ is reminiscent of the heavy-traffic parameter for a single-server queue. The CRPG is also related to the General Position Gap (GPG) (KAG23), which we discuss in Section 6.4. Now, we are ready to state the main result of this section that formalizes the trade-off between reward and expected queue lengths.

**Proposition 18.** Consider a vertex $\mu$ of $\Pi_{\ge 0}$ with support graph $G^* = (V, E^*)$, where $E^* = \{k \in E : \mu_k > 0\}$. For each $\epsilon > 0$, let $\Phi_\epsilon$ denote the $\epsilon$-filtering ML policy adapted to $(G, \lambda)$ with filter $E^*$. Then, $(G, \lambda, \Phi_\epsilon)$ is stable and there exist $C_1, C_2 \in \mathbb{R}_{\ge 0}$ such that, for all $\epsilon \in (0, 0.5)$, we have

$$ \|\mu(\Phi_\epsilon) - \mu\|_1 \le C_2\epsilon, \quad \mathbb{E}\left[\sum_{i \in V} Q_i\right] \le \frac{C_1}{\min\{\epsilon \min_{i \in V} \lambda_i + \delta(G^*, \lambda), \delta(G, \lambda)\}}. $$

Now we present a sketch of the proof of Proposition 18 that highlights the intuition behind the result.

**Sketch of the Proof (See Appendix D.2 for the complete proof).** We first consider an arbitrary matching problem $(G, \lambda)$. Note that the CRPG $\delta(G, \lambda)$ is reminiscent of the heavy-traffic parameter for a single-server queue. We make this intuition rigorous by showing that, under the ML policy, we have

$$ \mathbb{E}\left[\sum_{i \in V} Q_i\right] = O\left(\frac{1}{\delta(G, \lambda)}\right). \qquad (23) $$

The above result holds for any matching problem $(G, \lambda)$ operating under the ML policy as long as $\delta(G, \lambda) > 0$ (equivalently, whenever the matching problem $(G, \lambda)$ is stabilizable). Now, we use the above result to analyze the $\epsilon$-filtering ML policy adapted to $(G, \lambda)$ with filter $E^*$. Recalling that this is exactly the ML policy adapted to $(G', \lambda'_\epsilon)$, we turn our attention to the augmented matching problem $(G', \lambda'_\epsilon)$ and prove the following:

**Expected queue length bound:** We show that $\delta(G', \lambda'_\epsilon) = \Omega(\min\{\epsilon+\delta(G^*, \lambda), \delta(G, \lambda)\})$, and so, the expected queue length is $O(1/\min\{\epsilon + \delta(G^*, \lambda), \delta(G, \lambda)\})$ by (23). The idea is that, the edges in $E^+$ contribute $\delta(G^*, \lambda)$ to the CRPG because $E^+$ mimics $E^*$. In addition, matching $\Theta(\epsilon)$ arrivals using the edges in $E^\pm \cup E^-$ contributes an additional $\Omega(\epsilon)$ to the CRPG because $E^\pm \cup E^-$ mimics $E$. Thus, we have $\delta(G', \lambda'_\epsilon) = \Omega(\min\{\epsilon + \delta(G^*, \lambda), \delta(G, \lambda)\})$, which by (23) implies the expected queue length in steady state is at most $O(1/\min\{\epsilon + \delta(G^*, \lambda), \delta(G, \lambda)\})$. The minimum with $\delta(G, \lambda)$ is intuitive as $\delta(G, \lambda)$ is the CRPG of the original graph $G$, which is the best case scenario of using all edges to make matches.

**Matching rate is $O(\epsilon)$ close to $\mu$:** We show that we are $O(\epsilon)$ close to the vertex $\mu$ by bounding the frequency of “bad” matches, i.e., the matches that do not correspond to the support graph $G^*$. Such edges are of the form $(i^+, j^-)$ or $(i^-, j^-)$. We use the conservation equations given by (CE-1) along with the fact that the arrival rate to vertices $\{i^- : i \in V\}$ is $O(\epsilon)$ to prove this statement.

Combining the two steps above completes the proof of the proposition.

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

Now we discuss the implications of the above proposition separately for bijective and injective vertex.
### 5.2.2 Bijective vertices and facets of the convex polytope

With a slight abuse of notation, we will say that a vertex $\mu \in \Pi_{\ge 0}$ is bijective (resp. injective-only) if the subgraph $\bar{G}$ induced by $\mu$ is bijective (resp. injective-only). As stated above, the bijectivity of vertices plays an important role in the study of the matching rates that can be achieved by stable policies, which will be the matter of Section 6. We now detail the relationship between the bijectivity of vertices and the inequalities that define $\Pi_{\ge 0}$. While the remainder of this section helps in Section 6.2 to describe the set of matching rate vectors that can be achieved by an arbitrary stable policy, it can be skipped on first reading.

Following Proposition 5.7, the bijectivity of a vertex is determined by the number of its coordinates that are positive in edge coordinates, that is, by the cardinality of the set of edges that form its support. Recall that the $d$-dimensional polytope $\Pi_{\ge 0}$ is actually characterized by the $m$ inequalities $\mu_k \ge 0$ for each $k \in E$. In particular, this polytope has at most $m$ facets, one for each inequality, but it typically has fewer. Indeed, some inequalities may be redundant and/or not tight, in a sense that will be defined in Definition 5.9 below. For example, by looking more closely at the general solution obtained for the diamond graph in Figure 6, we conclude that:

- The inequality $\mu_{2,3} \ge 0$ is satisfied trivially by every vector $\mu \in \Pi$, as we have $\mu_{2,3} = \beta > 0$. Therefore, this inequality does not define a facet of $\Pi_{\ge 0}$.

- If $\lambda_1\bar{\lambda}_2 < \bar{\lambda}_3\lambda_4$, the inequality $\mu_{1,2} \ge 0$ supersedes the inequality $\mu_{3,4} \ge 0$, and conversely. If $\lambda_1\bar{\lambda}_2 = \bar{\lambda}_3\lambda_4$, these two inequalities are equivalent. In both cases, the inequalities $\mu_{1,2} \ge 0$ and $\mu_{3,4} \ge 0$ lead to a single facet of $\Pi_{\ge 0}$.

- If $\lambda_1\bar{\lambda}_3 < \bar{\lambda}_2\lambda_4$, the inequality $\mu_{1,3} \ge 0$ supersedes the inequality $\mu_{2,4} \ge 0$, and conversely. If $\lambda_1\bar{\lambda}_3 = \bar{\lambda}_2\lambda_4$, these two inequalities are equivalent. In both cases, the inequalities $\mu_{1,3} \ge 0$ and $\mu_{2,4} \ge 0$ lead to a single facet of $\Pi_{\ge 0}$.

All in all, the 1-dimensional convex polytope $\Pi_{\ge 0}$ associated with the diamond graph of Example 3.13 has two facets, even if it is defined by five inequalities. Definition 5.9 below will help us relate these notions to the number of zero coordinates of the vertices of the convex polytope $\Pi_{\ge 0}$.

**► Definition 5.9 (Adapted from [4, 33]).** Let $k \in E$.

(i) The inequality $\mu_k \ge 0$ is said to be tight if there exists a vector $\mu \in \Pi_{\ge 0}$ such that $\mu_k = 0$, in which case we also say that this inequality is tight for the vector $\mu$.

(ii) The inequality $\mu_k \ge 0$ is said to be redundant if removing this inequality does not change the polytope $\Pi_{\ge 0}$, in the sense that

$$ \Pi_{\ge 0} = \{\mu \in \mathbb{R}^m : A\mu = \lambda \text{ and } \mu_l \ge 0 \text{ for each } l \in E \setminus \{k\}\}. $$

Otherwise, this inequality is called irredundant.

(iii) The matching problem $(G, \lambda)$ is called essential if all tight inequalities are irredundant.

(iv) The polytope $\Pi_{\ge 0}$ is said to be simple if every vertex of $\Pi_{\ge 0}$ belongs to exactly $d$ facets, which is the minimal number of facets a vertex belongs to.

Importantly, the number of positive coordinates of a vertex $\mu$ (considered in Proposition 5.7) is the number of inequalities that are not tight for this vertex. More generally, Definition 5.9 has the following intuitive interpretation. An inequality is tight if the convex polytope $\Pi_{\ge 0}$ intersects the hyperplane obtained by transforming this inequality into an equality. Non-tight inequalities are “useless” (and redundant) because they are never satisfied as equalities by any vector in $\Pi_{\ge 0}$. The matching problem $(G, \lambda)$ is essential if each tight inequality defines a distinct facet of the convex polytope $\Pi_{\ge 0}$. Under this condition, the number of facets
### 6.3.1 Approaching bijective vertex

When $\mu$ is a bijective vertex, we have $\delta(G^*, \lambda) > 0$ as $(G^*, \lambda)$ is stabilizable (Proposition 17). Thus, we can let $\epsilon \to 0$ in Proposition 18 to conclude $\mu(\Phi_0) = \mu$ and $\mathbb{E}[\sum_{i \in V} Q_i] \le \frac{C_1}{\delta(G^*, \lambda)} < \infty$. Thus, we observe no trade-off between stability and approaching a bijective vertex. In fact, the $\epsilon$-filtering ML policy converges to the ML policy with filter $E^*$ as $\epsilon \to 0$, which is stable by Proposition 17. Moreover, Proposition 18 implies that the trade-off between the reward and the expected queue lengths still exists. In particular, if $\delta(G^*, \lambda) < \delta(G, \lambda)$, then, as $\epsilon$ increases, the expected queue lengths decreases at the expense of moving $\epsilon$ away from the vertex $\mu$. Intuitively, as $\epsilon$ increases, we more frequently use all the edges in the graph to make matches, which helps to reduce the expected queue lengths. At the same time, we more often use the edges $E \setminus E^*$ resulting in moving away from the vertex $\mu$. Note that, the expected queue lengths is always $O(1/\delta(G, \lambda))$ for any choice of $\epsilon > 0$. This upper bound corresponds to the best case scenario (see Lemma 31 in Appendix D.2) of using all the edges in $E$ to make matches. In Section 7, we analyze this trade-off via simulations and observe a mild trade-off (compared to the injective-only case) between the two objectives, aligning with the result of Proposition 18.

### 6.3.2 Approaching injective-only vertex

For an injective-only vertex, we have $\delta(G^*, \lambda) = 0$, and so, Proposition 18 implies the following:

$$ \|\mu(\Phi_{\epsilon}) - \mu\|_{1} \le C_{2}\epsilon, \quad \mathbb{E}\left[\sum_{i \in V} Q_{i}\right] \le \frac{C_{1}}{\min\{\epsilon \min_{i \in V} \lambda_{i}, \delta(G, \lambda)\}} \quad (24) $$

As $\epsilon \to 0$, the expected queue lengths increases to infinity, substantiating that the matching problem $(G^*, \lambda)$ is unstable as shown in Proposition 17. In other words, (24) establishes the trade-off between approaching an injective-only vertex and ensuring a stable system. Moreover, (24) also establishes a $O(1/\epsilon)$ expected queue length bound, while being $\epsilon$ close to the injective-only vertex $\mu$. We now show that this trade-off is fundamental: no sequence of matching policies can converge to an injective-only vertex of $\Pi_{\ge 0}$ while maintaining finite queue lengths. The next proposition captures this fundamental trade-off.

**Proposition 19.** Consider an injective-only vertex $\mu$ of $\Pi_{\ge 0}$. For each policy $\Phi$ adapted to $G$ and such that the matching model $(G, \lambda, \Phi)$ is stable, if $\|\mu(\Phi) - \mu\|_1 \le \epsilon$, then $\mathbb{E}[\|\hat{Q}\|_2^2] \ge \Omega(1/\epsilon)$.

**Proof.** See Appendix D.1.

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

The above proposition provides a bound of the order $\Omega(1/\epsilon)$ on the second moment of the queue length. We believe such a lower bound is not tight. In particular, we expect an $\Omega(1/\epsilon)$ lower bound on the first moment. Nonetheless, the result demonstrates that the trade-off between approaching an injective-only vertex and keeping the queue lengths small is fundamental. Remind, however, that such a trade-off does not exist for bijective vertices, as discussed before.

**Remark 5.** Appendix D.1 actually proves a more general version of Proposition 19 where we consider matching policies that can form at most M pairs of items at each time step, for some $M \in \mathbb{N}_{>0}$.
that contain a vertex is equal to the number of inequalities that are tight for this vertex. In particular, as we will see in Proposition 5.13, if the matching problem $(G, \lambda)$ is essential and the polytope $\Pi_{\ge 0}$ is simple, then every vertex satisfies exactly $d$ (tight) inequalities as equalities, which means that this vertex has $d$ zero coordinates, and therefore $n = m - d$ positive coordinates, so that this vertex is bijective.

All these notions are illustrated in Examples 5.10–5.12 below, which show in particular that a matching problem $(G, \lambda)$ may be essential even if the polytope $\Pi_{\ge 0}$ is not simple, and conversely. Consistently with Example 3.13 above, these examples use a kernel basis to verify effortlessly whether an inequality is tight and/or irredundant.

<table><caption>(a) Inequalities.</caption><thead><tr><th>Edge basis</th><th>Kernel basis</th><th>Tight?</th><th>Irredundant?</th></tr></thead><tbody><tr><td>μ<sub>1,2</sub> ≥ 0</td><td>α<sub>1</sub> ≤ 2</td><td>✗</td><td>✗</td></tr><tr><td>μ<sub>1,6</sub> ≥ 0</td><td>α<sub>1</sub> ≥ -2</td><td>✗</td><td>✗</td></tr><tr><td>μ<sub>2,3</sub> ≥ 0</td><td>α<sub>1</sub> - α<sub>2</sub> ≥ -1</td><td>✓</td><td>✓</td></tr><tr><td>μ<sub>2,6</sub> ≥ 0</td><td>α<sub>2</sub> ≥ -2</td><td>✗</td><td>✗</td></tr><tr><td>μ<sub>3,4</sub> ≥ 0</td><td>α<sub>1</sub> ≤ 1</td><td>✓</td><td>✓</td></tr><tr><td>μ<sub>3,5</sub> ≥ 0</td><td>α<sub>2</sub> ≥ -1</td><td>✓</td><td>✓</td></tr><tr><td>μ<sub>4,5</sub> ≥ 0</td><td>α<sub>1</sub> ≥ -1</td><td>✓</td><td>✓</td></tr><tr><td>μ<sub>5,6</sub> ≥ 0</td><td>α<sub>1</sub> + α<sub>2</sub> ≤ 1</td><td>✓</td><td>✓</td></tr></tbody></table>

<figure><img src="image_31.png" /><figcaption>(b) Generic solution of (CE).</figcaption></figure>

<figure><img src="image_32.png" /><figcaption>(c) Polytope $\Pi_{\ge 0}$ in kernel basis.</figcaption></figure>

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

<figure><img src="image_34.png" /><figcaption>(d) Edge coordinates of (0, 1).</figcaption></figure>

<caption>(e) Edge coordinates of (-1, 0).</caption>

<figure><img src="image_35.png" /><figcaption>(f) Edge coordinates of (1, 0).</figcaption></figure>

<figure><img src="image_36.png" /><figcaption>(g) Edge coordinates of (-1, -1).</figcaption></figure>

<caption>(h) Edge coordinates of (1, -1).</caption>

■ **Figure 14** An essential matching problem $(G, \lambda)$ with a simple polytope $\Pi_{\ge 0}$. The vector of arrival rates is $\lambda = (4, 5, 3, 2, 3, 5) \in \mathbb{R}^6$, a particular solution of (CE) is $\mu^* = (2, 2, 1, 2, 1, 1, 1) \in \mathbb{R}^8$, and the chosen base vectors for $\ker(A)$ are $b_1 = (-1, 1, 1, 0, -1, 0, 1, -1)$ and $b_2 = (0, 0, -1, 1, 0, 1, 0, -1)$.
## 6.4 Connections to the Literature

Maximizing edge-weighted rewards has recently received considerable attention in the literature ([37, 41, 23, 29, 30]). Among these, our work introduces a key novelty: leveraging stability, specifically via the conservation law (CE), to provide a global characterization of optimal solutions through the polytope. With the notable exception of [37], most related results were developed independently of our own, initiated with [14], resulting in some overlap in findings. In this section, we highlight both the originality of our approach and its strong parallels with related contributions in policy optimization. A detailed comparison of numerical performance is provided in Section 7.

### 6.4.1 Comparison with [29, 30, 23]

A recent line of work on stochastic matching focuses on maximizing a finite-time reward allows the system to be unstable. Specifically, this literature considers the Static Planning Problem (SPP), defined as

$$ \max_{Az+s=\lambda, z,s \ge 0} r^T z, \qquad (25) $$

where s represents slack variables allowing a fraction of the arrivals to be “thrown away” ([29]). A key assumption in this framework is the General Position Condition (GPC), which states that the optimal solution $(z^*, s^*)$ to Equation (25) is unique and non-degenerate ([29, Definition 3.1]).

Our framework is closely connected to this approach through several structural and conceptual parallels:

**SPP and polytope vertices.** Consider a matching problem $(G, \lambda)$ where $G$ is surjective, and a reward vector $r$ such that Equation (25) admits one unique solution $(z^*, s^*)$ with $s^* = 0$. In this case, $(G, \lambda)$ is stabilizable, $z^*$ is a vertex of the polytope $\Pi_{\ge 0}$, and GPC is satisfied if and only if $z^*$ is bijective.

**Filtering policies.** When GPC is satisfied and $s^* = 0$, our optimal policy $\Phi_{E^*}$ proposed in Proposition 17 (originally introduced in [14, Proposition 6.10]) coincides exactly with the match-the-longest-queue optimal policy in [29].

**Similarity between GPG and CRPG.** When GPC is satisfied, the smallest non-zero element of $(z^*, s^*)$, denoted $\tilde{\epsilon} > 0$ and called General Position Gap (GPG), is used to study the performance of the system<fnref n="11" />. Both $\tilde{\epsilon}$ and the CRPG $\delta(G, \lambda)$ measure, in different ways, the robustness of an optimal policy. If $s^* = 0$ and if $G^* = (V, E^*)$ denotes the support graph of the vertex $z^*$, they are related through the following equation:

$$ \delta(G, \lambda) \ge \delta(G^*, \lambda) \ge \tilde{\epsilon}. \qquad (26) $$

**Differences between GPG and CRPG.** While $\delta(G, \lambda)$ is a function only of the graph and arrival rates, $\tilde{\epsilon}$ additionally captures the effect of rewards. The two parameters are only connected (through Equation (26)) when GPC is satisfied and $s^* = 0$. For example, consider the diamond graph from Figure 1 with arrival rate $\lambda = (1, 2, 2, 1)$. In this case, one can check that $\delta = 2 > 0$. For a reward vector $r = (1, 0, 1, 0, 1)$, the SPP solution is $z^* = (1, 0, 1, 0, 1)$, $s^* = 0$, which is degenerate (i.e. injective-only) and thus $\tilde{\epsilon}$ is not defined. Conversely, one can have $\delta \le 0$ (meaning that the problem $(G, \lambda)$ is not stabilizable) and

<footnote n="11">¹¹We denote the GPG by $\tilde{\epsilon}$ to avoid conflict with our $\epsilon$-filtering notation.</footnote>
**► Example 5.10 (Essential matching problem).** Figure 14 considers a codomino graph with the vector of arrival rates $\lambda = (4, 5, 3, 2, 3, 5)$. A particular solution of (CE) is $\mu^° = (2, 2, 1, 2, 1, 1, 1, 1) \in \mathbb{R}^8$, and the basis of ker(A) consists of the vectors $b_1 = (-1, 1, 1, 0, -1, 0, 1, -1)$ and $b_2 = (0, 0, -1, 1, 0, 1, 0, -1)$ obtained in construction B of Figure 13. The generic solution of (CE) is shown in Figure 14b.

The inequalities are listed in Figure 14a. The 2-dimensional polytope $\Pi_{\ge 0}$, shown in Figure 14c in kernel basis, is characterized by five tight inequalities which are also irredundant:

$$-1 \le \alpha_1 \le 1, \quad \alpha_2 \ge -1, \quad \alpha_1 - \alpha_2 \ge -1, \quad \alpha_1 + \alpha_2 \le 1.$$

The matching problem $(G, \lambda)$ is essential. In kernel basis, the vertices of the convex polytope $\Pi_{\ge 0}$ are $(0, 1), (-1, 0), (1, 0), (-1, -1)$, and $(1, -1)$, and we can verify on Figure 14c that each vertex belongs to exactly 2 facets. Therefore $\Pi_{\ge 0}$ is simple (more generally, all 2-dimensional polytopes are simple). All in all, each vertex of $\Pi_{\ge 0}$ has 2 zero coordinates and 6 positive coordinates in edge coordinates, so that this vertex is bijective. These vertices are represented in edge basis in Figures 14d–14h.

**► Example 5.11 (Non-essential matching problem).** Figure 15 shows the same codomino graph as in Example 5.10, with the same basis of ker(A), but with the vector of arrival rates $\lambda = (2, 4, 4, 2, 2, 2)$. A particular solution of (CE) is $\mu^° = (1, 1, 2, 1, 1, 1, 0)$, and the general solution is shown in Figure 15b.

The inequalities are listed in Figure 15a. The 2-dimensional convex polytope $\Pi_{\ge 0}$ is shown in kernel basis in Figure 15c. All inequalities are tight, but only one is irredundant, so we conclude that the matching problem $(G, \lambda)$ is not essential, even if the polytope $\Pi_{\ge 0}$ is still simple. Correspondingly, even if each vertex belongs to exactly two facets, they all have more than 2 zero coordinates, so none of them is bijective. For example, the vertex $(1, -1)$ in kernel basis has coordinates $(0, 2, 4, 0, 0, 2, 0)$ in edge basis (Figure 15f). This vertex has 5 zero coordinates in edge coordinates (and only 3 positive coordinates) even if it belongs to only 2 facets.

**► Example 5.12 (Non-simple polytope).** We finally exhibit an essential matching problem with a non-simple associated polytope. As 2-dimensional polytopes are simple, we need to consider a more complex example. We consider the matching problem of Figure 16a. The arrival rate is $\lambda = (3, 3, 6, 3, 4, 4, 6, 3, 4, 4) \in \mathbb{R}^{10}$. The particular solution and kernel basis are shown on the edges. The set $\Pi_{\ge 0}$, shown in Figure 16b in kernel basis, is an Egyptian pyramid characterized by the following tight inequalities:

$$\alpha_3 \ge 0, \quad 1 + \alpha_1 - \alpha_3 \ge 0, \quad 1 - \alpha_1 - \alpha_3 \ge 0, \quad 1 + \alpha_2 - \alpha_3 \ge 0, \quad 1 - \alpha_2 - \alpha_3 \ge 0.$$

These five inequalities are irredundant (each one corresponds to exactly one of the five facets), so we conclude that the matching problem $(G, \lambda)$ is essential. In kernel basis, the vertices of this convex polytope are $(-1, -1, 0), (1, -1, 0), (1, 1, 0), (-1, 1, 0)$, and $(0, 0, 1)$. These vertices are shown in edge basis in Figures 16c–16g. The polytope $\Pi_{\ge 0}$ is not simple because the vertex $(0, 0, 1)$ (the “top” of the pyramid) belongs to 4 facets, while the polytope has dimension 3. Consistently, we can see in Figure 16g that this vertex has 4 zero coordinates and only 9 positive coordinates in edge basis; the subgraph defined by the support of this vertex is injective-only.

In light of the examples above, we can give the following characterization of the bijective vertices of $\Pi_{\ge 0}$.
$\tilde{\epsilon} > 0$ (meaning that arrival rates are “imbalanced”). Consider for example $V = \{1, 2\}$ and $E = \{\{1, 2\}\}$ with arrival rates $\lambda_1 > \lambda_2 > 0$. $G$ is not stabilizable, so $\delta \le 0$ (more precisely, $\delta = \lambda_2 - \lambda_1 < 0$). On the other hand, the SPP solution is $z^* = \lambda_2$, $s^* = (\lambda_1 - \lambda_2, 0)$, so $\tilde{\epsilon} = \min\{\lambda_1 - \lambda_2, \lambda_2\} > 0$.

**Elimination of slack variables.** [23] extends the model from [29, 30] by considering multi-way matching and variable arrival rates, and explores the meaning of the GPC in that context. Assuming that the solution of SPP is a bijective vertex with support $E^*$, they propose to use a filtering policy on $E^*$. Since ML can become unstable in multi-way matching, a *Sum-of-Squares* policy operating on a virtual queue is instead employed. They also eliminate the need for a slack variable $s$ by augmenting the graph with mono-edges of zero reward for each node. Applied to our framework, or more exactly its hypergraph extension presented in Section 8.3, this trick ensures that SPP solutions always correspond to a polytope face, and GPC is satisfied if and only if that face is a bijective vertex.

**Proof of Equation (26).** We first prove $\delta(G, \lambda) \ge \delta(G^*, \lambda)$: as $E^* \subseteq E$, if $\mathcal{I}$ is an independent set of $G$, it is also an independent set of $G^*$, and $V_{G^*}(\mathcal{I}) \subseteq V_G(\mathcal{I})$, where $V_G(\mathcal{I})$ (resp. $V_{G^*}(\mathcal{I})$) is the neighbor set of $\mathcal{I}$ in $G$ (resp. $G^*$). We conclude by comparing Equation (22) applied to $\delta(G, \lambda)$ and $\delta(G^*, \lambda)$.

For the second part of the inequality, by the definition of $\tilde{\epsilon}$, we have $z_k^* \ge \tilde{\epsilon}$ for all $k \in E^*$. For any $\epsilon < \tilde{\epsilon}$, we define $z(\epsilon) \in \mathbb{R}_+^{|E^*|}$ as $z_k(\epsilon) = z_k^* - \epsilon > 0$ for all $k \in E^*$, and note that $z(\epsilon)$ is the unique solution to $A^*z = \lambda(\epsilon)$ with $\lambda_j(\epsilon) = \lambda_j - \epsilon d_j^* > 0$ for all $j \in V$ ($d_j^*$ denotes the degree of $j$ in $G^*$). Thus, by Proposition 8iii, we have

$$ \sum_{j \in V_{G^*}(\mathcal{I})} \lambda_j - \sum_{i \in \mathcal{I}} \lambda_i > \epsilon \left( \sum_{j \in V_{G^*}(\mathcal{I})} d_j^* - \sum_{i \in \mathcal{I}} d_i^* \right), \quad \forall \mathcal{I} \in \mathbb{I}_{G^*}. $$

As $G^*$ is bijective, it has no bipartite component, which implies

$$ \sum_{j \in V_{G^*}(\mathcal{I})} d_j^* - \sum_{i \in \mathcal{I}} d_i^* \ge 1, \quad \forall \mathcal{I} \in \mathbb{I}_{G^*}. $$

By minimizing over all independent sets $\mathcal{I} \subseteq \mathbb{I}_{G^*}$, we obtain

$$ \epsilon < \min_{\mathcal{I} \in \mathbb{I}_{G^*}} \left( \sum_{j \in V_{G^*}(\mathcal{I})} \lambda_j - \sum_{i \in \mathcal{I}} \lambda_i \right) = \delta(G^*, \lambda). $$

As $\epsilon < \tilde{\epsilon}$ is arbitrary, we get

$$ \tilde{\epsilon} \le \delta(G^*, \lambda). $$

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

### 6.4.2 Comparison with [37, 41]

[37] introduced the Extended Greedy Primal-Dual (EGPD) policies, a family of reward-based stable policies developed for general multi-way matching settings. Under their stabilizability condition ([37, Assumption 5]), which is equivalent to our condition Proposition 8 (i.e., surjective compatibility graph and existence of a positive solution to (CE)), they prove that EGPD asymptotically maximizes a concave function of the matching rewards while ensuring system stability. Notably, EGPD provides a canonical alternative to $\epsilon$-filtering for approaching any vertex (bijective or injective) of $\Pi_{\ge 0}$ under the stability constraint.
<table><caption>(a) Inequalities</caption><thead><tr><th>Edge basis</th><th>Kernel basis</th><th>Tight?</th><th>Irredundant?</th></tr></thead><tbody><tr><td>μ<sub>1,2</sub> ≥ 0</td><td>α<sub>1</sub> ≤ 1</td><td>✓</td><td>✗</td></tr><tr><td>μ<sub>1,6</sub> ≥ 0</td><td>α<sub>1</sub> ≥ -1</td><td>✓</td><td>✗</td></tr><tr><td>μ<sub>2,3</sub> ≥ 0</td><td>α<sub>1</sub> - α<sub>2</sub> ≥ -2</td><td>✓</td><td>✗</td></tr><tr><td>μ<sub>2,6</sub> ≥ 0</td><td>α<sub>2</sub> ≥ -1</td><td>✓</td><td>✗</td></tr><tr><td>μ<sub>3,4</sub> ≥ 0</td><td>α<sub>1</sub> ≤ 1</td><td>✓</td><td>✗</td></tr><tr><td>μ<sub>3,5</sub> ≥ 0</td><td>α<sub>2</sub> ≥ -1</td><td>✓</td><td>✗</td></tr><tr><td>μ<sub>4,5</sub> ≥ 0</td><td>α<sub>1</sub> ≥ -1</td><td>✓</td><td>✗</td></tr><tr><td>μ<sub>5,6</sub> ≥ 0</td><td>α<sub>1</sub> + α<sub>2</sub> ≤ 0</td><td>✓</td><td>✓</td></tr></tbody></table>

<figure><img src="image_37.png" /><figcaption>(b) Generic solution of (CE).</figcaption></figure>

<figure><img src="image_38.png" /><figcaption>(c) Polytope Π≥0 in kernel basis. Dashed lines show tight redundant inequalities.</figcaption></figure>

<figure><img src="image_39.png" /><figcaption>(d) Edge coordinates of (-1, 1).</figcaption></figure>

<figure><img src="image_40.png" /><figcaption>(e) Edge coordinates of (-1, -1).</figcaption></figure>

<figure><img src="image_41.png" /><figcaption>(f) Edge coordinates of (1, -1).</figcaption></figure>

■ **Figure 15** Non-essential matching problem $(G, \lambda)$ with a simple polytope $\Pi_{\ge 0}$. The vector of arrival rates is $\lambda = (2, 4, 4, 2, 2, 2) \in \mathbb{R}^6$, a particular solution of (CE) is $\mu^0 = (1, 1, 2, 1, 1, 1, 0) \in \mathbb{R}^8$, and the chosen base vectors for $\ker(A)$ are $b_1 = (-1, 1, 1, 0, -1, 0, 1, -1)$ and $b_2 = (0, 0, -1, 1, 0, 1, 0, -1)$.

**► Proposition 5.13.** Let $\mu$ be a vertex of $\Pi_{\ge 0}$. The following statements are equivalent:

(i) $\mu$ is bijective.

(ii) $\mu$ belongs to exactly $d$ facets of $\Pi_{\ge 0}$ and none of the inequalities tight for $\mu$ is redundant. In particular, all vertices of $\Pi_{\ge 0}$ are bijective if, and only if, the matching problem $(G, \lambda)$ is essential and the polytope $\Pi_{\ge 0}$ is simple.

**Proof.** To prove the equivalence of (i) and (ii), we first remark that the number of zero edge coordinates of a vector $\mu \in \Pi_{\ge 0}$ is by definition the number of inequalities that are tight for $\mu$. It is in particular at least the number of facets that intersect $\mu$, with equality if, and only if, none of the inequalities tight for $\mu$ is redundant.

If a vector $\mu$ is a vertex of $\Pi_{\ge 0}$, then $\mu$ belongs to at least $d$ facets of $\Pi_{\ge 0}$. Now, the vector $\mu$ is bijective if, and only if, $d$ of its coordinates are zero, which in view of the remark above is equivalent to say that $\mu$ belongs to exactly $d$ facets of $\Pi_{\ge 0}$ and none of the inequalities tight for $\mu$ is redundant.

As for the last statement, it follows a directly from Definition 5.9. ◀

<figure><img src="image_42.png" /></figure>
Their work is instrumental for extending our results beyond simple graphs to multi-way matching (cf Section 8.3). In particular, the EGPD algorithm is built on a variant of the ML policy that operates over a virtual queue system. This variant stabilizes any stabilizable problem $(G, \lambda)$, regardless of whether $G$ is simple or contains multi-edges, and can thus be used as a direct replacement for the standard ML policy in multi-way matching contexts. We call this policy Virtual-Queue Match-the-Longest (VQML).

While EGPD ensures stability and asymptotic optimality, it does not provide explicit guarantees on queue lengths. In contrast, our analysis establishes concrete bounds on queue lengths, a contribution beyond [37]. Specifically, we show that for bijective vertices, the reward is achieved exactly (rather than just asymptotically) with bounded queue lengths. For injective-only vertices, we prove that one can approach the optimal reward to within $\epsilon$ at a cost of $O(1/\epsilon)$ for queue lengths. These explicit bounds are, to our knowledge, new relative to [37].

More recently, [41] introduced the Constant-Regret Primal-Dual (CRPD) policy, a variant of EGPD. They use an alternative, but related, GPC based on the dual of the reward-maximization problem $\max_{z \in \Pi_{\ge 0}} r^T z$, which excludes the case where the primal solution is a unique but degenerate (i.e. injective-only) vertex. CRPD features two key modifications compared to the original policy:

1. The edge reward vector $r$ is replaced by $r' = r - UA$, where $U$ represents shadow prices on the nodes, chosen to solve $\min_{UA \ge r} U\lambda$. If the arrival rates $\lambda$ are not known, they are replaced by empirical estimates $\hat{\lambda}$ based on observed arrivals so far. Under the assumption that the optimal point corresponds to a bijective vertex of support $G^* = (V, E^*)$, it can be shown that $r' \le 0$ and $r'_k = 0$ if and only if $k \in E^*$. Thus, $r'$ acts as a re-weighted reward that penalizes edges outside the optimal support.

2. The parameter $\beta$ controlling the rewards-versus-queues trade-off is not static but decreases over time, typically $\beta(t) = t^{-\alpha}$ for some $\alpha > 0$. As time progresses, this makes the algorithm increasingly reward-centric.

When $\alpha$ is large, CRPD effectively estimates $E^*$ (using either $\lambda$ or empirical $\hat{\lambda}$) and restricts matching exclusively to $E^*$. In effect, this approach is a filtering policy on $E^*$, as in [14, 29], with the main difference being the use of a virtual queue mechanism (VQML) instead of ML.

Interestingly, our numerical experiments revealed that using values of $\alpha$ outside the range originally proposed in [41] (typically $\alpha < 1/2$) produces a new family of policies parameterized by $\alpha$, exhibiting a nuanced delay-regret trade-off reminiscent of EGPD or $\epsilon$-filtering. This phenomenon and its implications will be discussed in the next section.

### 6.4.3 Summary

Our work main focus is the study of stable matching policies and of the space of matching rates they can achieve. It coincides with the related work on reward optimization in the important case where the GPC is satisfied, which corresponds to considering a bijective vertex. In fact, most results on bijective vertices can be translated between the two frameworks. For example, Proposition 17(i)) can be directly inferred from [29, Lemma 5.4] along with the Foster-Lyapunov theorem.

Conversely, our work explicitly handles the cases where the GPC does not hold. Specifically, when SPP has a unique, degenerate, solution (injective-only vertex), we propose a parameterized stable policy that tunes the delay-reward trade-off, while a naive application of the ML policy as in [29] would result in an unstable system. If the SPP solution is not
<figure><img src="image_43.png" /><figcaption>Figure 16 Essential matching problem $(G, \lambda)$ with a non-simple polytope $\Pi_{\ge 0}$. The arrival rate is $\lambda = (3, 3, 6, 3, 4, 4, 6, 3, 4, 4) \in \mathbb{R}^{10}$. A particular solution and the chosen base vectors for $\ker(A)$ are implicitly shown on the edges of Figure 16a.</figcaption></figure>

# 6 Matching rates in surjective-only graphs

Section 5 described the polytope $\Pi_{\ge 0}$, defined as the set of non-negative solutions of (CE). In this section, we investigate which of these solutions may, or may not, be achieved by a (stable) policy. Unless stated otherwise, in this section, we consider a stabilizable matching problem $(G, \lambda)$ with a surjective-only compatibility graph $G$, so that the set $\Pi_{\ge 0}$ of non-negative solutions of (CE) is non-trivial.

Given a policy $\Phi$ that stabilizes the matching problem $(G, \lambda)$, we let $\mu(\Phi)$ (resp. $\alpha(\Phi)$) denote the edge (resp. kernel) coordinates of the vector of matching rates in the model $(G, \lambda, \Phi)$. We consider the set of matching rates achieved by stable policies (resp. by stable greedy policies), defined as follows:

$$ \Pi_G = \{\mu(\Phi) : \Phi \text{ is a greedy policy adapted to the compatibility graph } G\}, $$

$$ \Pi_P = \{\mu(\Phi) : \Phi \text{ is a stable policy adapted to the compatibility graph } G\}. $$

Section 6.1 focuses on the set $\Pi_G$. We show in particular that $\Pi_G \subseteq \Pi_{>0}$, where $\Pi_{>0}$ is the (non-empty) set of positive solutions of (CE) (that is, solutions with positive coordinates). We also show that, in many cases, the inclusion is strict. In contrast, we observe in Section 6.2 that non-greedy policies can achieve any vector in $\Pi_{>0}$, and that filtering policies can even
unique (i.e., the maximizing set is a face of $\Pi_{\ge 0}$ rather than a point), we can look for an element of the face whose support is a surjective graph, and if none exists, choose one vertex of the face (it is injective-only) and approach it, for example using $\epsilon$-filtering.

# 7 Practical performance

Let $(G, \lambda)$ be a stabilizable problem, $r \in \mathbb{R}^m$ a vector of rewards, and $\mu$ a vertex of $\Pi_{\ge 0}$ that optimizes the average reward $r^\top \mu$. Let $E^* \subsetneq E$ denote the edges of $G$ that support $\mu$. In this section, we use simulations to quantitatively evaluate the performance of various policies in achieving $\mu$. Section 7.1 introduces the policies under consideration, while Section 7.2 outlines the simulation methodology. Sections 7.3 and 7.4 analyze the injective-only and bijective cases, respectively. Finally, Section 7.5 presents a discussion of the results.

## 7.1 Considered policies

For ease of display, we use $\Phi$ to denote all matching policies, distinguishing them by a subscript indicating a specific policy (e.g., $\epsilon$ for the $\epsilon$-filtering, $\beta$ for EGPD). More specifically, we consider the following policies:

**Filtering ML policy** The ML policy restricted to $E^*$, denoted by $\Phi_{E^*}$, is stable only if $\mu$ is bijective (see Proposition 17). In this case, it is optimal (i.e., incurs no regret), and its delay serves as a benchmark for other policies. In figures of simulations, $\Phi_{E^*}$ is represented as a dotted line marking its delay.

**$\epsilon$-filtering ML policy** The $\epsilon$-filtering ML policy with filter $E^*$, denoted by $\Phi_\epsilon$ for $\epsilon \in (0, 1)$, is stable for any $\epsilon > 0$ and converges to $\mu$ as $O(\epsilon)$, with bounded delay in $O(1/\epsilon)$ (Proposition 18).

**$k$-filtering ML policy** The $k$-filtering ML policy with filter $E^*$, denoted by $\Phi_k$ for $k \in \mathbb{N}$, applies the filter $E^*$ depending on the state: it uses $\Phi_{E^*}$ if the length of the longest queue is less than $k$; otherwise it applies the ML policy without filter.

**EGPD policy** The Extended Greedy Primal-Dual (EGPD) algorithm, denoted by $\Phi_\beta$ for $\beta \in (0, +\infty)$, is a stable policy that does not require explicit knowledge of $\lambda$ or $E^*$. It is based on the Virtual-Queue Match-the-Longest (VQML) policy.

**EGPD+$$\beta$ policy** Denoted by $\Phi'_\beta$ for $\beta \in (0, +\infty)$, EGPD+$$\beta$ is variant of EGPD with rewards are adapted to $E^*$.

**CRPD policy** The Constant-Regret Primal-Dual (CRPD) is variant of EGPD where the rewards are adapted to $E^*$ and parameter $\beta$ decreases over time. If $\beta$ goes to 0 the policy is unstable on injective-only vertices. If it decreases sufficiently fast, $\Phi_\alpha$ behaves like a filtering policy. The CRPD policy that uses $\beta(t) = 1/t^\alpha$ for $\alpha > 0$ is denoted $\Phi_\alpha$.
Table 2 summarizes the selected policies and their key features.

**Remark 6.** Two new policies are proposed for numerical evaluation, $\Phi_k$ and $\Phi'_\beta$.

The motivation for $\Phi_k$ is our expectation that it outperforms $\Phi_\epsilon$ in practical scenarios. While $\Phi_\epsilon$ consistently allows a small fraction of items to be matched outside $E^*$, $\Phi_k$ relaxes the constraint on allowed edges only when necessary — specifically when delay is significantly affected. We provide in Appendix E.1 elements to substantiate the conjecture that $\Phi_k$ offers theoretical guarantees similar to those of $\Phi_\epsilon$.

We also introduce $\Phi'_\beta$ as it is a natural intermediate between $\Phi_\beta$ and its variant $\Phi_\alpha$. The policy $\Phi_\alpha$ incorporates two new features: adapted rewards and a decreasing $\beta$ parameter. Consider the addition of only one of these features, we discard the option of using a decreasing
approach some faces of $\Pi_{\ge 0}$. More precisely, we conjecture that $\Pi_{>0} \subseteq \Pi_{\mathcal{P}}$ in general, and we prove that $\Pi_{\mathcal{P}} = \Pi_{\ge 0}$ if the support graph of each vertex of $\Pi_{\ge 0}$ is bijective. Informally, these results show that non-greedy policies are more suitable than greedy policies to navigate the set $\Pi_{\ge 0}$.

The following result will be useful throughout this section.

**Proposition 6.1.** *The sets $\Pi_G$ and $\Pi_{\mathcal{P}}$ are convex.*

*Proof.* See Appendix C.1.

## 6.1 Greedy policies

Greedy policies are appealing candidates to control matching problems. Some of them, like *match-the-longest* or *first-come-first-matched*, are easy to implement and stabilize all stabilizable matching problems. Greedy policies may also be more easily accepted socially, especially in situations involving human beings. We show in this section that, unfortunately, in general, greedy policies cannot achieve all achievable matching rates. Indeed, although we do not provide a universal tight description of $\Pi_G$ (which we believe to be a difficult task), we provide two simple examples where $\Pi_G$ is a strict subset of $\Pi_{>0}$. In contrast, Section 6.2 will introduce semi-filtering (non-greedy) policies and show that these policies can be used to achieve every vector in the set $\Pi_{>0}$ and some of the faces of the polytope $\Pi_{\ge 0}$.

Firstly, in Proposition 6.2 below, we show that greedy policies cannot reach the boundary of the convex polytope $\Pi_{\ge 0}$.

**Proposition 6.2.** *If the compatibility graph $G$ is surjective-only and the matching problem $(G, \lambda)$ is stabilizable, then the set $\Pi_G$ is non-empty and $\Pi_G \subseteq \Pi_{>0}$.*

*Proof.* The set $\Pi_G$ is non-empty because, as recalled in Section 2.4, the greedy policies *match-the-longest* and *first-come-first-matched* are stable. We now prove that $\Pi_G \subseteq \Pi_{>0}$.
Consider a stable greedy policy $\Phi$ and let $\mu = (\mu_1, \mu_2, \dots, \mu_m)$ denote the matching rate vector in the model $(G, \lambda, \Phi)$. Consider an edge $e_k = \{i, j\}$. Since the policy $\Phi$ is greedy, two items of classes $i$ and $j$ are always matched if the following sequence of events occurs: the system is in the empty state $\emptyset$, then a class-$i$ item arrives, and then a class-$j$ item arrives. Let $p_\emptyset$ denote the stationary probability that the model $(G, \lambda, \Phi)$ is in the empty state $\emptyset$. We know that $p_\emptyset > 0$ because the model is stable, and the previous remark implies that $\mu_k \ge p_\emptyset \lambda_i \lambda_j / \sum_{\ell \in V} \lambda_\ell > 0$. Since this is true for each edge $e_k \in E$ and each $\mu \in \Pi_G$, we conclude that $\Pi_G \subseteq \Pi_{>0}$. $\quad$

Proposition 6.2 has the following consequence regarding the ability of greedy policies to maximize linear reward functions.

**Corollary 6.3.** *Consider the problem of maximizing an edge-dependent reward defined by a vector $w$ as stated in Proposition 5.5. Let $r_{\max} = \max_{\mu \in \Pi_{\ge 0}} w^\top \mu$ be the optimal reward. One of the two exclusive statements below is true:*

(i) All vectors of $\Pi_{\ge 0}$ are optimal, i.e., $w^\top \mu = r_{\max}$ for each $\mu \in \Pi_{\ge 0}$.

(ii) All stable greedy policies are suboptimal, i.e., $w^\top \mu < r_{\max}$ for each $\mu \in \Pi_G$.

*Proof.* We know from Proposition 5.5 that the set of vectors $\mu \in \Pi_{\ge 0}$ that maximize the reward is a non-empty face $F$ of $\Pi_{\ge 0}$. If $F = \Pi_{\ge 0}$, we are obviously in case (i) (i.e., all $\mu \in \Pi_{\ge 0}$ are optimal). One can verify that this corresponds to situations where the vector $w$
<table><caption>Table 2 Overview of the matching policies evaluated.</caption><thead><tr><th>Policy</th><th>Base</th><th>Parameter</th><th>Principle</th></tr></thead><tbody><tr><td>Φ<sub>E*</sub></td><td rowspan="3">ML</td><td>N/A</td><td>No matching outside E<sup>*</sup>.</td></tr><tr><td>Φ<sub>ε</sub></td><td>ε</td><td>Φ<sub>E*</sub>, matchings outside E<sup>*</sup> allowed for a fraction of items.</td></tr><tr><td>Φ<sub>k</sub></td><td>k</td><td>Φ<sub>E*</sub>, matchings outside E<sup>*</sup> allowed if the queue is large.</td></tr><tr><td>Φ<sub>β</sub></td><td rowspan="3">VQML</td><td rowspan="2">β</td><td>Edge scores based on rewards and queue sizes.</td></tr><tr><td>Φ'<sub>β</sub></td><td>Φ<sub>β</sub>, with rewards adapted to E<sup>*</sup> (positive on E<sup>*</sup>, negative outside).</td></tr><tr><td>Φ<sub>α</sub></td><td>α</td><td>Φ<sub>β</sub>, with adapted rewards r' = r - UA and vanishing queue size impact.</td></tr></tbody></table>

β without reward adaptation as it usually makes the system unstable. The $Φ'_{β}$ policies considered here use simplified reward adaptation.

## 7.2 Methodology

For measuring the performance criteria presented in Section 6.1, we used the Python package *Stochastic Matching* of [35]. This package enables us to verify the stabilizability of a matching problem $(G, \lambda)$, analyze the vertices of $\Pi_{\ge 0}$, and measure the regret and delay of policies through simulations.

For policies with parameters, we selected the following ranges:

- $k \in [1, 2^{13}]$ for k-filtering;

- $\epsilon \in [10^{-3}, 1]$ for $\epsilon$-filtering;

- $\beta \in [10^{-3}, 10]$ for EGPD and EGPD+;

- $\alpha \in [0, 1]$ for CRPD.

Unless stated otherwise, our evaluation protocol is as follows: after selecting $G$ and $\lambda$, we choose a vertex $\mu$ of $\Pi_{\ge 0}$. Next we choose a reward vector $r$ such that $\mu$ is the unique optimal, using adversarial rewards: weights are adjusted to make a direct identification of $\mu$'s support $E^*$ difficult, while ensuring that $\mu$ remains the unique optimum. Note that only $Φ_β$ depends on the exact reward weights; other policies are directly driven by $E^*$. The rational for using adversarial rewards is to highlight the performance difference between $Φ_β$ and $Φ'_β$. Once parameters are fixed, all policies are evaluated by simulating $T = 10^{10}$ arrivals and measuring regret and delay.

We focus here on the diamond graph from Figure 1, but we conducted experiments on other graphs of various sizes (up to 100 nodes) with qualitatively similar results. Some of them are available in Appendix E.2 and in the package documentation<fnref n="12" />.

## 7.3 Approaching an injective-only vertex

To begin, we consider degree-proportional arrival rates, i.e., $\lambda = (2, 3, 3, 2)$. Our objective is to approach the injective-only vertex $\mu = (2, 0, 1, 0, 2)$, which effectively disables edges $\{1, 3\}$ and $\{2, 4\}$. We select the adversarial reward vector $r = (1, 2.9, 1, -1, 1)$, assigning the highest reward to edge $\{1, 3\}$. The results are presented in Figure 10.

<footnote n="12">¹²https://balouf.github.io/stochastic_matchring/companion/simulations.html#Vertices-of-simple-graphs</footnote>
is orthogonal to $ker(A)$ (for example, if all coordinates of $w$ are identical$^7$). Otherwise, because of the lattice structure of the faces of a polytope, $F$ is included into a facet of $\Pi_{\ge 0}$, which means that there is at least one edge $k \in E$ such that the $k$-th coordinate of all vectors in $F$ is zero in the edge basis. In particular, since all coordinates of the matching rate vector under a stable greedy policy are positive in the edge basis, no greedy policy is optimal. ◀

Proposition 6.2 demonstrates that stable greedy policies can only achieve vectors of matching rates with positive coordinates in the edge basis, i.e., $\Pi_G \subseteq \Pi_{>0}$. In the remainder of this section, we show that whether $\Pi_G \subseteq \Pi_{>0}$ or $\Pi_G = \Pi_{>0}$ depends on the matching problem $(G, \lambda)$ under consideration. Specifically, we investigate two examples in Sections 6.1.1 and 6.1.2 where $\Pi_G$ is a strict subset of $\Pi_{>0}$. In contract, in Section 6.1.3, we present a well-chosen example where $\Pi_G = \Pi_{>0}$, illustrating a case where greedy policies cover all positive solutions of (CE).

### 6.1.1 Complete graph

We first consider a matching problem $(K_n, \lambda)$, where $K_n$ is the complete graph with $n \ge 3$ nodes. According to Proposition 3.7, this matching problem is stabilizable if and only if $\lambda_i < \frac{1}{2} \sum_{j \in V} \lambda_j$ for each $i \in V$. Propositions 6.4 and 6.5 below state that greedy policies do not allow any degree of freedom, in the sense that the queue-size process and the vector of matching rates are the same under all stable greedy policies. Indeed, the only independent sets of a complete graph are the singletons, hence by (7) the state space of the queue-size process under greedy policies is

$$Q_G(K_n) = \{0\} \cup \left( \bigcup_{i \in V} \{\ell 1_i : \ell \in \mathbb{N}_{>0}\} \right), \quad (25)$$

where $1_i$ is the $n$-dimensional vector with one in coordinate $i$ and zero elsewhere, for each $i \in V$. This observation implies that greediness restricts the freedom in matching decisions: all unmatched items belong to the same class, and an incoming item must be matched with one of them if its class differs. This observation is formalized in Proposition 6.4. Proposition 6.5 further builds on it to conclude that the set $\Pi_G$ collapses to a single point and directly express the unique vector of matching rates achieved by (stable) greedy policies.

In contrast, the polytope $\Pi_{\ge 0}$ exhibits a dimension $d = m - n = \frac{n(n-3)}{2}$, where $n = |V|$ is the number of classes and $m = |E| = \binom{n}{2} = \frac{n(n-1)}{2}$ is the number of possible matches. In particular, for $n \ge 4$, the dimension $d = m - n$ of $\Pi_G$ is at least 2. Therefore, limiting ourselves to greedy policies dramatically narrows the range of achievable solutions on complete graphs larger than a triangle.

**► Proposition 6.4 (Equivalence of greedy policies).**

Consider the complete graph $K_n$ with $n \ge 3$ nodes.

(i) There is a unique size-based greedy policy that is adapted to the compatibility graph $K_n$. This policy, called the natural greedy policy and denoted by $\Phi_G(K_n)$, is the deterministic

<footnote>$^7$ Assume that all coordinates of $w$ are identical. Then a vector $y \in \mathbb{R}^m$ is orthogonal to $w$ if and only if $\sum_{k \in E} y_k = 0$. For each vector $y \in ker(A)$, we have $Ay = 0$, so that in particular $\sum_{k \in E} (Ay)_k = 0$. But by definition of the matrix $A$, we also know that $\sum_{k \in E} (Ay)_k = 2 \sum_{k \in E} y_k$.</footnote>
<figure><img src="image_35.png" /><figcaption>Figure 10 G: diamond graph; $\lambda = (2, 3, 3, 2)$; $\mu = (2, 0, 1, 0, 2)$; $r = (1, 2, 9, 1, -1, 1)$.</figcaption></figure>

First, we emphasize that any simulation, regardless of length, provides only a finite-horizon estimate of a policy's long-term behavior. In particular, it will always yield a finite delay, even for policies proven to be unstable here, like $\Phi_{E^*}$ and $\Phi_\alpha$ for $\alpha > 0$. This explains why $\Phi_\alpha$, when converging to $\Phi_{E^*}$, appears to achieve zero regret with constant delay. In reality, the delay is unbounded and grows like $\sqrt{T}^{13}$. Therefore, values observed in the far right portion of the figure must be interpreted with caution, as they reflect finite-horizon effects rather than the true long-term behavior.

With that in mind, one can observe that all policies clearly demonstrate the $(\epsilon, 1/\epsilon)$ trade-off between delay and regret, as predicted by Proposition 18.

Specifically, $\Phi_k$ and $\Phi'_\beta$ exhibit very similar performance, while $\Phi_\epsilon$ and $\Phi_\alpha$ perform slightly worse. Due to the adversarial reward vector, the performance of $\Phi_\beta$ degrades by more than one order of magnitude, incurring more than ten times the regret of $\Phi_k$ for the same target delay, or equivalently, requiring a delay ten times longer to achieve the same regret.

## 7.4 Approaching a bijective vertex

Still focusing on the diamond graph, we now set $\lambda = (4, 4, 4, 2)$ and examine the vertex $\mu = (1, 3, 1, 2, 0)$, which disables edge $\{3, 4\}$. We select the adversarial reward vector $r = (-1, 1, 1, 1, 2.9)$, assigning the highest reward to edge $\{3, 4\}$ and a negative reward to the positive edge $\{1, 2\}$.

Since $\mu$ is bijective, we know from Proposition 17 that $\Phi_{E^*}$ is optimal in terms of regret. However, it is interesting to assess how vertex-approaching policies perform in this case. The results are presented in Figure 11.

All policies continue to exhibit a trade-off between regret and delay. Except for $\Phi_\beta$, they all achieve delays lower than that $\Phi_{E^*}$ at the cost of a positive regret.

Specifically, $\Phi_\epsilon$ and $\Phi_k$ perform very similarly and converge precisely to $\Phi_{E^*}$, as predicted by their design. $\Phi_\alpha$ and $\Phi'_\beta$ outperform the others; notably, they achieve zero regret with

<footnote n="13">13 https://balouf.github.io/stochastic_matchring/companion/simulations.html# Drift-of-optimal-solution-for-injective-only-vertices</footnote>
size-based policy defined on $Q_G(K_n) \times V$ by

$$ \Phi_G(K_n)(q, i) = \begin{cases} j & \text{if } q_j \ge 1 \text{ with } j \ne i, \\ \perp & \text{otherwise.} \end{cases} \qquad (26) $$

(ii) Consider a greedy policy $\Phi$ adapted to the graph $K_n$, and let $(S, |\cdot|)$ denote its state space. The policy $\Phi$ makes the same decisions as the natural greedy policy $\Phi_G$ in the sense that

$$ \sum_{s' \in S} \Phi(s, i, \Phi_G(K_n)(|s|, i), s') = 1, \quad s \in S, \quad i \in V. $$

In other words, all greedy policies are equivalent in the sense that they can all be reduced to $\Phi_G(K_n)$ (see “Equivalent policies” in Section 2.3.4).

(iii) For each greedy policy $\Phi$ adapted to the graph $K_n$ and each sequence $I$ of item classes, we have $(Q_G)_t = Q_t$ for each $t \in \mathbb{N}$, where $Q_G$ and $Q$ are the queue-size processes of the models $(K_n, I, \Phi_G(K_n))$ and $(K_n, I, \Phi)$, respectively.

**Proof.** See Appendix C.2.

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

**► Proposition 6.5 (Matching rates under greedy policies).**

Consider a stabilizable matching problem $(K_n, \lambda)$, where $K_n$ is the complete graph with $n \ge 3$ nodes, and let $\Phi$ denote a greedy policy adapted to $K_n$.

(i) The model $(K_n, \lambda, \Phi)$ is stable.

(ii) The matching rate vector $\mu_G$ in this model satisfies

$$ (\mu_G)_k = \lambda_i p_j + \lambda_j p_i, \quad e_k = \{i, j\} \in E, \qquad (27) $$

where, for each $i \in V$, $p_i$ is the stationary probability that queue i is non-empty, given by

$$ p_i = \frac{\lambda_i}{\left(\sum_{j \neq i} \lambda_j\right) - \lambda_i} p_{\emptyset}, \qquad (28) $$

and $p_{\emptyset}$ is the stationary probability that the system is empty, given by

$$ p_{\emptyset} = \left( 1 + \sum_{i \in V} \frac{\lambda_i}{\left( \sum_{j \neq i} \lambda_j \right) - \lambda_i} \right)^{-1}. \qquad (29) $$

In particular, we have $\Pi_G = \{\mu_G\} \subsetneq \Pi_{>0}$ whenever $n \ge 4$.

**Proof.** See Appendix C.2.

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

Figure 17 illustrates this result on a complete graph $K_4$ in which all arrival rates are equal to 3. The particular solution $\mu^\circ$ and the basis $\{b_1, b_2\}$ of $ker(A)$ that we use are shown on Figure 17a. In the corresponding kernel basis, the polytope $\Pi_{\ge 0}$ is defined by the inequalities $\alpha_1 \le 1$, $\alpha_2 \le 1$, and $\alpha_1 + \alpha_2 \ge -1$, that is, it is the triangle with vertices $(-2, 1)$, $(1, -2)$, and $(1, 1)$. Yet, Proposition 6.5 shows that only the solution $\alpha = (0, 0)$ can be achieved by a greedy policy.
<figure><img src="image_36.png" /><figcaption>Figure 11 G: diamond graph; $\lambda = (4, 4, 4, 2)$; $\mu = (1, 3, 1, 2, 0)$; $r = (-1, 1, 1, 1, 2.9)$.</figcaption></figure>

delays lower than $\Phi_{E^*}$. We interpret this as resulting from their base policy, VQML, which may perform better than $\Phi_{E^*}$'s base policy ML in the model where edge {3, 4} is removed.

As before, $\Phi_{\beta}$ performs poorly due to the adversarial reward vector. While its regret can approach zero arbitrarily closely, as predicted by theory, this comes at the cost of a large delay that appears to grow asymptotically like $1/\beta$, effectively unbounded.

## 7.5 Discussion

The observations made in Sections 7.3 and 7.4 are not specific to the diamond graph. Other studied examples show qualitatively similar behavior. Our main conclusion is that no single policy consistently outperforms all others across all scenarios. Nevertheless, some patterns emerge:

- Pure filtering should be avoided if the vertex is injective-only. For bijective vertices, if minimizing regret is the absolute priority, pure filtering is a natural choice; otherwise, more flexible policies may perform better.

- $\epsilon$-filtering ML is a robust vertex-approaching method effective on both injective-only and bijective vertices. It offers theoretical guarantees but can often be outperformed numerically by state-dependent policies.

- EGPD does not require knowledge of the vertex $\mu$ corresponding to the arrival rate and reward vectors. However, it performs poorly when the reward vector is misaligned with the support $E^*$ of $\mu$.

- EGPD+ addresses the drawbacks of EGPD by aligning the rewards with $E^*$. Note that this requires knowledge or estimation of the arrival rate $\lambda$.

- Although theoretical guarantees for $k$-filtering ML remain conjectural, simulations suggest it strikes a favorable balance between performance and robustness. Alongside EGPD+, it is our recommended policy when arrival rates are known or stable enough.

- CRPD delivers good performance and theoretical guarantees; however, when compared with $\Phi'_{\beta}$, the practical benefit of introducing a time-decreasing parameter remains unclear.
<figure><img src="image_46.png" /><figcaption>(a) Generic solution of (CE).</figcaption></figure>

<figure><img src="image_47.png" /><figcaption>(b) The polytope $\Pi_{\ge 0}$ in kernel basis. The set $\Pi_G$ is reduced to the origin vector $\alpha = (0, 0)$.</figcaption></figure>

■ Figure 17 Matching problem ($K_4$, $\lambda$) with $\lambda = (3, 3, 3, 3)$.

## 6.1.2 Diamond graph

We now consider the diamond (double fan) graph introduced in Example 3.13, for which we will show that the set $\Pi_G$ of matching rate vectors achieved by stable greedy policies is again a strict subset of the set $\Pi_{>0}$ of positive solution of (CE), without being restricted to a singleton as in Section 6.1.1 either. More specifically, we consider the diamond matching problem ($D$, $\lambda$) defined as follows:

$$ 
\begin{align} 
D &= (V, E) \text{ with } V = \{1, 2, 3, 4\} \text{ and } E = \{\{1, 2\}, \{1, 3\}, \{2, 3\}, \{2, 4\}, \{3, 4\}\}, \nonumber \\
\lambda &= (\lambda_1, \bar{\lambda}_2 + \beta, \bar{\lambda}_3 + \beta, \lambda_4) \nonumber \\
&\qquad \text{with } \lambda_1 > 0, \bar{\lambda}_2 > 0, \bar{\lambda}_3 > 0, \lambda_4 > 0, \beta > 0, \lambda_1 + \lambda_4 = \bar{\lambda}_2 + \bar{\lambda}_3 = \frac{1}{2}, \tag{30} \\
\mathcal{B} &= \{(1, -1, 0, -1, 1)\}, \nonumber \\
\mu^\circ &= (2\lambda_1\bar{\lambda}_2, 2\lambda_1\bar{\lambda}_3, \beta, 2\bar{\lambda}_2\lambda_4, 2\bar{\lambda}_3\lambda_4), \nonumber \\
\mu &= (2\lambda_1\bar{\lambda}_2 + \alpha, 2\lambda_1\bar{\lambda}_3 - \alpha, \beta, 2\bar{\lambda}_2\lambda_4 - \alpha, 2\bar{\lambda}_3\lambda_4 + \alpha), \quad \alpha \in \mathbb{R}. \nonumber
\end{align} 
$$

Parameterizing $\lambda$ by $\beta$ ($= \mu_{2,4}$ for each $\mu \in \Pi$) is a notational convenience that does not lead to any loss of generality: as already observed in Example 3.13, the stabilizability condition (ii) writes $\bar{\lambda}_2 > 0$, $\bar{\lambda}_3 > 0$, and $\beta > 0$. We leave it to the reader to verify that our choices for $\mathcal{B}$ and $\mu^\circ$ are correct. Equation (30) implies in particular that the sets $\Pi_{\ge 0}$, $\Pi_{>0}$, $\Pi_P$, and $\Pi_G$ are real intervals. We will now prove that the interval $\Pi_G$, without being reduced to a singleton as in a complete graph, is still a strict subset of the interval $\Pi_{>0}$.

### Equivalence of stable greedy policies

Following the same approach as in Section 6.1.1, we first identify a common behavior shared by all greedy policies (Proposition 6.6), and then we exploit this behavior to characterize the matching rates achievable by stable greedy policies (Propositions 6.7 and 6.8). Since $\{1, 4\}$ is the only independent set of the diamond graph $D$ that is not a singleton, the possible queue states under any greedy policy can be partitioned as follows: either all queues are empty, or exactly one class has a non-empty queue, or (only) classes 1 and 4 have non-empty queues. In other words, the state space of the queue-size process under greedy policies adapted to the graph $D$ is

$$ Q_G(D) = \{0\} \cup \left( \bigcup_{i \in V} \{\ell 1_i, \ell \in \mathbb{N}_{>0}\} \right) \cup \{\ell_1 1_1 + \ell_4 1_4 : \ell_1, \ell_4 \in \mathbb{N}_{>0}\}. \quad (31) $$
in many scenarios<fnref n="14" />.

# 8 Extensions of our results

This article focuses on the matching rates of stable policies in the context of two-way matching, emphasizing linear optimization. However, our approach extends beyond this setting. In this section, we present several extensions: Section 8.1 addresses the case of non-linear reward functions; Section 8.2 explores the (im)possibility of achieving a vertex using only stable greedy policies; and Section 8.3 briefly outlines the adaptation of our work to hypergraphs, enabling the possibility of discarding items and multi-way matching.

## 8.1 Non-linear optimization

Proposition 17 introduced $\Pi_P$, the set of matching rates achievable by a stable policy, and compared it to the vertices of $\Pi_{\ge 0}$, which contain the optimal solutions for linear reward optimization.

However, when considering a non-linear reward function $r(\mu)$, an optimal solution can lie anywhere within $\Pi_{\ge 0}$. For example, one might want a stable policy to be as close as possible to a target matching rate vector $\mu_0$ and use the reward function $r(\mu) = -||\mu - \mu_0||_1$. Ideally, we would like $\Pi_P$ to be as close to $\Pi_{\ge 0}$ as possible. The following proposition demonstrates that this is indeed the case.

**Proposition 20.** Let $\Pi_P$ be the set of matching rate vectors achievable by a stable policy adapted to a given stabilizable matching problem $(G, \lambda)$. Then, $\Pi_P$ is convex. Furthermore, any positive solution to the conservation equation (CE) can be obtained by a stable policy, that is,

$$ \Pi_{>0} \subseteq \Pi_P \subseteq \Pi_{\ge 0}, \text{ where } \Pi_{>0} = \{\mu \in \mathbb{R}_{>0}^m : A\mu = \lambda\}. $$

In the particular case where all vertices of $\Pi_{\ge 0}$ are bijective, we have $\Pi_P = \Pi_{\ge 0}$.

**Proof.** Convexity of $\Pi_P$ is shown in Appendix F.1. The inclusion $\Pi_P \subseteq \Pi_{\ge 0}$ follows from the discussion in Section 3.1: any stable policy yields a matching rate vector that satisfies (CE) with non-negative coordinates. We now prove that $\Pi_{>0} \subseteq \Pi_P$. Since $\Pi_P$ is convex, its closure is also convex. By Proposition 18 and the convexity of $\Pi_P$, the closure of $\Pi_P$ contains all vertices of $\Pi_{\ge 0}$, and, by convexity, encompasses $\Pi_{\ge 0}$ as well. As a result, by virtue of convexity, $\Pi_P$ contains the interior<fnref n="15" /> of its own closure, which includes $\Pi_{>0}$, the interior of $\Pi_{\ge 0}$. In the particular case where all vertices are bijective, they all belong to $\Pi_P$, leading to the equality $\Pi_P = \Pi_{\ge 0}$. ◀

Proposition 20 is essentially an existence result, as the policy constructed to show convexity of $\Pi_P$ in Appendix F.1 may be both hard to implement (as it requires computing the mean return time to a particular state of two Markov chains) and undesirable in practice (as the matching rate will have high variance). An interesting follow-up question is thus to explore practical methods to reach an arbitrary vector of $\Pi_P$.

<footnote n="14">¹⁴Counter-examples exist, cf https://balouf.github.io/stochastic_matchin g/companion/ simulations.html#Larger-graphs</footnote>

<footnote n="15">¹⁵Here, the notion of interior refers to the canonical $\mathbb{R}^d$ topology of the $d$-dimensional affine space of solutions to the conservation equation.</footnote>
Therefore, greediness entirely determines the decisions made by greedy policies, except if an item of class 2 or 3 enters while there are unmatched items of classes 1 and 4. Using the fact that classes 2 and 3 are both compatible with classes 1 and 4, the next proposition shows that all greedy policies adapted to the diamond graph make the same matching decisions as the natural greedy policy adapted to the complete graph $K_3$ obtained by “merging” classes 1 and 4 in the diamond graph.

**► Proposition 6.6 (Equivalence of greedy policies).**

Given the diamond graph $D$, we introduce the following notation:

- Queue-size projection: For each $q = (q_1, q_2, q_3, q_4) \in Q_G(D)$, we let $\langle q \rangle = (q_1 + q_4, q_2, q_3)$.

- Class projection: We let $\langle i \rangle = i$ for each $i \in \{1, 2, 3, \perp\}$ and $\langle 4 \rangle = 1$.

Every greedy policy $\Phi$ adapted to the diamond graph $D$ satisfies the following properties:

(i) If $\Phi$ is a deterministic size-based policy, then

$$ \langle \Phi(q, i) \rangle = \Phi_G(K_3)(\langle q \rangle, \langle i \rangle), \quad (q, i) \in Q_G(D) \times V. $$

where $\Phi_G(K_3)$ is the natural greedy policy (26) adapted to the complete graph $K_3$.

(ii) In general, if $\Phi$ is a policy with state space $(S, |\cdot|)$, then

$$ \sum_{s' \in S} \sum_{j \in V \cup \{\perp\}: \langle j \rangle = \Phi_G(K_3)(\langle |s| \rangle, \langle i \rangle)} \Phi(s, i, j, s') = 1, \quad s \in S, \quad i \in V. $$

(iii) For each sequence $I$ of item classes, we have $\langle Q_t \rangle = (Q_G)_t$ for each $t \in \mathbb{N}$, where $Q$ and $Q_G$ are the queue-size processes of the models $(D, I, \Phi)$ and $(K_3, \langle I \rangle, \Phi_G)$, respectively, with $\langle I \rangle = (\langle I_t \rangle, t \in \mathbb{N})$.

**Proof.** See Appendix C.3. ▼

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

Loosely speaking, the main take-away of Proposition 6.6(iii) is that, in the matching model $(D, I, \Phi)$, the process $((Q_{t,1} + Q_{t,4}, Q_{t,2}, Q_{t,3}), t \in \mathbb{N})$ does not depend on the specific greedy policy $\Phi$ that is applied, and it is in fact equal to the queue size process built by applying the natural greedy policy $\Phi_G(K_3)$ in the complete graph $K_3$ obtained by merging classes 1 and 4 in the diamond graph $D$.

**Matching rates under stable greedy policies**

Propositions 6.7 and 6.8 use the equivalence result of Proposition 6.6 to characterize the matching rate vector under stable greedy policies. These propositions illustrate the complementarity of edge and kernel coordinates: the results of Proposition 6.7 are easier to state using edge coordinates, while those of Proposition 6.8 are easier to state using kernel coordinates. The lower bound (32) on the matching rates in the diamond matching problem are obtained by following a similar approach as in Proposition 6.5(ii).

**► Proposition 6.7 (Matching rates under greedy policies – Edge coordinates).**

Consider the matching model $(D, \lambda, \Phi)$, where $(D, \lambda)$ is the diamond problem (30) and $\Phi$ is a greedy policy adapted to the graph $D$.

(i) This matching model is stable.

(ii) The matching rate vector $\mu = \mu(D, \lambda, \Phi)$ satisfies $\mu_{2,3} = \beta = \frac{1}{2}(\lambda_2 + \lambda_3 - \lambda_1 - \lambda_4)$, and

$$ \mu_{1,2} \ge \lambda_1 p_2 + \lambda_2 p_1, \quad \mu_{1,3} \ge \lambda_1 p_3 + \lambda_3 p_1, \\ \mu_{2,4} \ge \lambda_2 p_4 + \lambda_4 p_2, \quad \mu_{3,4} \ge \lambda_3 p_4 + \lambda_4 p_3, \tag{32} $$

where $p_i$ is the stationary probability that the system contains unmatched items that all belong to class $i$, for each $i \in V$.
## 8.2 Greedy policies

Greedy policies are appealing candidates for controlling matching problems, and they have been extensively studied in the literature. Some, such as ML and FCFM, are direct to implement and stabilize all stabilizable matching problems. Moreover, greedy policies may be more socially acceptable, particularly in scenarios involving human participants. However, as we will demonstrate in this section, greedy policies are generally not well-suited for optimizing matching rate vectors. They can never achieve a vertex, and examples suggest that in most cases, they are unable to even approach one.

In what follows, consider a stabilizable problem $(G, \lambda)$ with a surjective-only graph $G$, and let $\Pi_G$ denote the set of matching rate vectors achieved by stable greedy policies adapted to the problem $(G, \lambda)$. As in Proposition 20, let $\Pi_{>0} = \{\mu \in \mathbb{R}_{>0}^m : A\mu = \lambda\}$ denote the set of the positive solutions to the conservation equation (CE), i.e., those with positive coordinates, which form the interior of $\Pi_{>0}$.

### 8.2.1 Convexity and impossibility result

We first demonstrate that, unlike stable policies in general, stable greedy policies can never reach the boundary of the convex polytope $\Pi_{\ge 0}$, irrespective of whether the vertices of $\Pi_{\ge 0}$ are bijective or injective-only.

**Proposition 21.** Let $\Pi_G$ denote the set of matching rate vectors achievable by a stable greedy policy for a given stabilizable matching problem $(G, \lambda)$, where $G$ is surjective-only. Then, $\Pi_G$ forms a non-empty convex subset of $\Pi_{>0}$.

**Proof.** The set $\Pi_G$ is non-empty because, as recalled in Section 2.4, the greedy ML and FCFM policies are stable. Its convexity is shown in Appendix F.1. We now prove that $\Pi_G \subseteq \Pi_{>0}$. Consider a stable greedy policy $\Phi$ and let $\mu$ denote the matching-rate vector in the model $(G, \lambda, \Phi)$. Consider an edge $e_k = \{i, j\}$. Since the policy $\Phi$ is greedy, two items of classes $i$ and $j$ are always matched if the following sequence of events occurs: the system is in the empty state $\emptyset$, then a class-$i$ item arrives, and then a class-$j$ item arrives. Let $p_\emptyset$ denote the stationary probability that the model $(G, \lambda, \Phi)$ is in the empty state<fnref n="16" /> $\emptyset$. We know that $p_\emptyset > 0$ because the model is stable, and the previous remark implies that $\mu_k \ge p_\emptyset \lambda_i \lambda_j / (\sum_{\ell \in V} \lambda_\ell)^2 > 0$. Since this is true for each edge $e_k \in E$ and each $\mu \in \Pi_G$, we conclude that $\Pi_G \subseteq \Pi_{>0}$. ◀

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

Proposition 21 has the following consequence regarding greedy policies and linear optimization.

**Corollary 22.** Let $r_{\max} = \max_{\mu \in \Pi_{\ge 0}} r^\top \mu$ be the optimal reward in the linear optimization problem defined by the reward vector $r$ in Proposition 15. One of the following must hold:

(i) All stable policies (greedy or not) are optimal, i.e., $r^\top \mu = r_{\max}$ for each $\mu \in \Pi_P$.

(ii) All stable greedy policies are suboptimal, i.e., $r^\top \mu < r_{\max}$ for each $\mu \in \Pi_G$.

**Proof.** We know from Proposition 15 that the set of vectors $\mu \in \Pi_{\ge 0}$ maximizing the reward forms a non-empty face $F$ of $\Pi_{\ge 0}$. If $F = \Pi_{\ge 0}$, then we are in case (i), meaning

<footnote n="16">¹⁶ As mentioned in Appendix A, 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 is captured by the positive recurrence of the Markov chain describing the evolution of the system state. If the policy is queue-based (so that $S = Q$), this empty state is simply the $n$-dimensional zero vector.</footnote>
(iii) Let $p_{1,4}$ denote the stationary probability that the system contains unmatched items that belong to class 1 or 4 (or both). We have

$$ 
\begin{aligned}
p_2 &= \frac{\lambda_2}{\lambda_1 + \lambda_3 + \lambda_4 - \lambda_2} p_\emptyset, & p_3 &= \frac{\lambda_3}{\lambda_1 + \lambda_2 + \lambda_4 - \lambda_3} p_\emptyset, \\
p_{1,4} &= \frac{\lambda_1 + \lambda_4}{\lambda_2 + \lambda_3 - \lambda_1 - \lambda_4} p_\emptyset,
\end{aligned} 
\quad (33) $$

where $p_\emptyset$ is the stationary probability that the system is empty, whose value follows from the normalization equation $p_\emptyset + p_{1,4} + p_2 + p_3 = 1$. We also have

$$ p_1 > \frac{\lambda_1}{\lambda_2 + \lambda_3 + \lambda_4} p_\emptyset, \quad p_4 > \frac{\lambda_4}{\lambda_1 + \lambda_2 + \lambda_3} p_\emptyset. \quad (34) $$

**Proof.** See Appendix C.3. ◀

Intuitively, the kernel coordinate $\alpha$ given in (30) (also visible in Figure 6) acts like a slider that determines how much edges $\{1, 2\}$ and $\{3, 4\}$ are (dis)favored compared to edges $\{1, 3\}$ and $\{2, 4\}$ in the long run. Remarkably, Proposition 6.8 below shows that the greedy policy that favors edges $\{1, 2\}$ and $\{3, 4\}$ (resp. $\{1, 3\}$ and $\{2, 4\}$) the most in the long run is also the policy that favors these two edges the most in the short run. This result is proved by a coupling argument. In addition, Proposition 6.8 uses the lower bound (32) in Proposition 6.7 to prove that, in the limit as $\beta \to +\infty$, all greedy policies yield the same matching rate vector.

**► Proposition 6.8 (Matching rates under greedy policies – Kernel coordinates).**

Consider the diamond matching problem $(D, \lambda)$ described in (30).

(i) The intervals $\Pi_{\ge 0}$, $\Pi_{> 0}$, and $\Pi_G$ are defined as follows in the kernel basis:

$$ 
\begin{aligned}
\Pi_{\ge 0} &= [-2 \min(\lambda_1 \bar{\lambda}_2, \bar{\lambda}_3 \lambda_4), 2 \min(\lambda_1 \bar{\lambda}_3, \bar{\lambda}_2 \lambda_4)], \\
\Pi_{> 0} &= (-2 \min(\lambda_1 \bar{\lambda}_2, \bar{\lambda}_3 \lambda_4), 2 \min(\lambda_1 \bar{\lambda}_3, \bar{\lambda}_2 \lambda_4)), \\
\Pi_G &= [\alpha_-, \alpha_+],
\end{aligned} 
$$

with $-2 \min(\lambda_1 \bar{\lambda}_2, \bar{\lambda}_3 \lambda_4) < \alpha_- \le \alpha_+ < 2 \min(\lambda_1 \bar{\lambda}_3, \bar{\lambda}_2 \lambda_4)$. Hence, $\Pi_G \subsetneq \Pi_{> 0} \subsetneq \Pi_{\ge 0}$.

(ii) The coordinates $\alpha_+$ and $\alpha_-$ satisfy the following properties:

a. $\alpha_+ = \alpha(\Phi_+)$, where $\Phi_+$ is the edge-priority policy adapted to the graph $D$ whereby edges $\{1, 2\}$ and $\{3, 4\}$ have the highest priority.

b. $\alpha_- = \alpha(\Phi_-)$, where $\Phi_-$ is the edges-priority policy adapted to the graph $D$ whereby edges $\{1, 3\}$ and $\{2, 4\}$ have the highest priority.

c. If $\beta \to +\infty$ while $\lambda_1, \bar{\lambda}_2, \bar{\lambda}_3$, and $\lambda_4$ remain fixed, we have $\alpha_+ \to 0$ and $\alpha_- \to 0$.

**Proof.** See Appendix C.3. ◀

Taken together, Statements (i) and (iic) in Proposition 6.8 show that, as $\beta \to +\infty$, the interval $\Pi_G$ becomes reduced to a single point $\alpha = 0$, meaning that all greedy policies yield the same vector of matching rates, with edge coordinates $\mu = (2\lambda_1\bar{\lambda}_2, 2\lambda_1\bar{\lambda}_3, \beta, 2\bar{\lambda}_2\lambda_4, 2\bar{\lambda}_3\lambda_4)$. The rationale behind this result is the following. In the regime where $\beta = \mu_{2,3} \to +\infty$, we see in (30) that the arrival rates of classes 2 and 3 become large compared to those of classes 1 and 4. As a result, items of classes 1 and 4 are matched (almost) always immediately, and unmatched items belong to either class 2 or class 3 (but not both at the same time). In the proof of Proposition 6.8(iic), this intuition is formalized by taking the limit of (33) as $\beta \to +\infty$, which yields

$$ p_{\emptyset} \to 0, \quad p_2 \to 2\bar{\lambda}_2, \quad p_3 \to 2\bar{\lambda}_3, \quad p_{1,4} \to 0. $$
all $\mu \in \Pi_P \subset \Pi_{\ge 0}$ are optimal. This occurs when the vector $r$ is orthogonal to $ker(A)^{17}$. Otherwise, by the lattice structure of polytope faces, $F$ is contained in a facet of $\Pi_{\ge 0}$, implying there is at least one edge $k \in E$ where the $k$-th coordinate of all vectors in $F$ is zero. As stable greedy policies produce matching rate vectors with all positive coordinates, no greedy policy can be optimal in this case.

◀

## 8.2.2 Achievability results

We now explore the relationship $\Pi_G \subseteq \Pi_{>0}$ through several examples. In particular, Propositions 23 and 24 illustrate situations where $\Pi_G$ is a strict subset of $\Pi_{>0}$, suggesting that the greedy constraint imposes significant limitations on the set of achievable matching rates. However, this is not universally true, as Conjecture 25 provides a (carefully chosen) example where $\Pi_G = \Pi_{>0}$.

**Proposition 23.** Let $(K_n, \lambda)$ be a stabilizable matching problem, where $K_n$ is the complete graph with $n \ge 3$ nodes. All greedy policies adapted to $K_n$ are stable and yield the same matching-rate vector, denoted $\mu_G$. In particular, we have $\Pi_G = \{\mu_G\} \subseteq \Pi_{>0}$ whenever $n \ge 4$.

*Proof.* See Appendix F.2.1 for proof and discussion.

◀

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

**Proposition 24.** Let $(D, \lambda)$ be a stabilizable matching problem, where $D$ is the diamond graph from Figure 3d. All greedy policies adapted to $D$ are stable. In kernel coordinates, there exist $\alpha_- < \alpha_+$ such that $\Pi_G = [\alpha_-, \alpha_+] \subseteq \Pi_{>0}$.

*Proof.* See Appendix F.2.2 for proof, discussion, and numerical results.

◀

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

**Conjecture 25.** Let $(G, \lambda)$ be the stabilizable matching problem depicted in Figure 12 (the Fish matching problem). For this problem, we have $\Pi_G = (-1/2, 1/2) = \Pi_{>0}$.

*Proof.* See Appendix F.2.3 for sketch of proof, discussion, and numerical results.

◀

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

<figure><img src="image_41.png" /><figcaption>Figure 12 Generic solution to (CE) in the Fish matching ($\lambda = (4, 4, 3, 2, 3, 2)$).</figcaption></figure>

## 8.3 Hypergraphs

A hypergraph $G = (V, E)$ consists of a set of nodes $V$ and a set of hyperedges $E$, where each hyperedge is a multi-subset (i.e. potentially allowing multiplicities) of $V$ of arbitrary size, starting from one. This contrasts with simple graphs, where each edge is a pair of distinct nodes. Stochastic matching models extend naturally to hypergraphs as follows: when a

<footnote n="17">¹⁷An example of this is shown in Figure 9, or when all coordinates of $r$ are equal, making all edges equivalent.</footnote>
In this regime, the greediness of the policy allows no degree of flexibility in choosing the class of the item to which an incoming item is matched, so the matching rates are unique.

► **Remark 6.9.** Some quantities in Proposition 6.8 are functions of the matching rate $\beta = \mu_{2,3}$, but this dependency is kept implicit to simplify notation. In particular, the intervals $\Pi_{\ge 0}$ and $\Pi_{>0}$ do not depend on $\beta$, but the interval $\Pi_G$ and the coordinates $\alpha_+$ and $\alpha_-$ do.

## Numerical results

<figure><img src="image_49.png" /><figcaption>■ **Figure 18** Evolution of $\Pi_G$ as a function of $\beta$ in the diamond problem (30) with $\lambda_1 = \bar{\lambda}_2 = \bar{\lambda}_3 = \lambda_4 = \frac{1}{4}$. For each $\beta$, $\Pi_G$ is estimated by simulating the model ($D, \lambda, \Phi_+$) and leveraging the symmetry of the problem. $\Pi_{\ge 0}$ and other bounds are displayed for comparison. All results are expressed in kernel coordinates.</figcaption></figure>

To illustrate Proposition 6.8, Figure 18 shows a symmetric example with $\lambda_1 = \bar{\lambda}_2 = \bar{\lambda}_3 = \lambda_4 = \frac{1}{4}$. The figure compares $\Pi_{\ge 0}$ and $\Pi_G$ with the bounds (32)–(34) (converted in the kernel coordinates) and the limit $\alpha = 0$. Each point forming the shape of $\Pi_G = [\alpha_-, \alpha_+]$ is obtained by running a simulation consisting of $10^{10}$ steps (as specified in Section 2.5). As announced by Proposition 6.8, $\Pi_G$ becomes reduced to a single point $\alpha = 0$ when $\beta \to +\infty$. We also notice that the bounds provided by (32)–(34) are not tight when $\beta$ is small (in the sense that the difference between $\alpha_+$ and the upper-bound is no longer negligible compared to the difference between $\alpha_+$ and the boundary $2\min(\lambda_1\bar{\lambda}_3, \bar{\lambda}_2, \lambda_4)$ of $\Pi_{\ge 0}$), while at the same time $\alpha_+$ and $\alpha_-$ become arbitrarily close to the borders of $\Pi_{\ge 0}$ when $\beta$ tends to zero (which does not contradict the fact that $\Pi_G$ is a strict subset of $\Pi_{\ge 0}$ as long as $\beta > 0$). The gap between $\Pi_G$ and the bounds (32)–(34) comes from the fact that, to obtain the lower bounds for $p_1$ and $p_4$ in (34), we neglected the case where there are both class-1 and class-4 unmatched items, and this case is not negligible when $\beta$ is small.

### 6.1.3 Fish graph

Sections 6.1.1 and 6.1.2 exhibited two stabilizable matching problems in which the matching rates achievable by stable greedy policies were bounded away from the faces of the polytope $\Pi_{\ge 0}$. These two examples may suggest that, in most stabilisable matching problems, the restrictions imposed by greediness are so strong that we will also obtain $\Pi_G \subsetneq \Pi_{>0}$. We
<figure><img src="image_42.png" /><figcaption>■ **Figure 13** Hypergraph example studied in [37]. The rewards associated with each hyperedge are indicated.</figcaption></figure>

matching decision is made, items corresponding to the selected hyperedge are removed from
the system.

A complete, formal, extension of our results to hypergraphs is beyond the scope of this
paper, but our approach adapts with limited changes. The key elements are:

- The incidence matrix $A$ for hypergraphs is defined analogously to simple graphs but can be any matrix in $\mathbb{N}^{n \times m}$, with $a_{i,k}$ indicating whether node $i$ belongs to hyperedge $k$, counting multiplicities in case of repeated nodes. The connection between properties of $A$ and stability remains, particularly Proposition 7. However, some graph-specific results, such as the connection between instability and bipartite structures or the description of $ker(A)$ in terms of cycles and kayak paddles, do not easily generalize to hypergraphs.

- Proposition 8 remains valid. In particular, the stability condition iii can still be verified by computing $A^{-1}\lambda$ for bijective hypergraphs, or solving (10) for surjective-only hypergraphs.

- Some policies from Sections 6 and 7 that optimize the matching-rate vector, specifically $\Phi_{E^*}$, $\Phi_e$, and $\Phi_k$, rely on the maximal stability property of the ML policy in simple graphs. This property does not extend to hypergraphs$^{18}$, necessitating alternative maximally stable policies. We chose VQML, the rewardless version of EGPD, although other choices are possible.

We illustrate these adaptations through numerical results on example cases. We apply the policies from Table 2, adapted to hypergraphs by always using VQML as the base policy, following the simulation methodology described in Section 7.2. These examples highlight the performance of the proposed policies in the hypergraph context.

8.3.1 Original example from [37]

[37] considered the hypergraph shown in Figure 13 for the numerical evaluation of their policy $\Phi_{\beta}$. This hypergraph consists of four nodes, each with a mono-edge (i.e., a 1-edge), two regular 2-edges, and one 3-edge. It can be verified that this hypergraph is surjective-only, and the solution space to (CE) has dimension 3.

The authors consider a single reward vector (shown in Figure 13) and two distinct arrival-rate vectors: $\lambda = (1.2, 1.5, 2, 0.8)$ and $\lambda = (1.8, 0.8, 1.4, 1)$. Both vectors are stabilizable. The first generates a polytope $\Pi_{\ge 0}$ with 8 vertices, while the second generates a polytope with 4 vertices. All vertices are bijective, indicating that the reward can always be optimized using the filtering policy $\Phi_{E^*}$. The performance of the considered policies under these conditions is shown in Figure 14. The key observations are:

- All parameterized policies can minimize the regret when their parameter is aggressive enough.

<footnote n="18"><sup>18</sup> In hypergraphs, stabilizable matching problems exist where no greedy policy is stable.</footnote>
now consider another matching problem, called the Fish problem, where we conjecture on the contrary that $\Pi_G = \Pi_{>0}$. The Fish matching problem is defined as follows:

$$
\begin{align}
V &= \{1, 2, 3, 4, 5, 6\}, \nonumber \\
E &= \{\{1, 2\}, \{1, 3\}, \{2, 3\}, \{3, 4\}, \{4, 5\}, \{5, 6\}\}, \nonumber \\
\lambda &= (4, 4, 3, 2, 3, 2), \nonumber \\
B &= \{(0, 0, 0, 1, -1, -1, 1)\}, \nonumber \\
\mu^{\circ} &= (3, 1, 1, \frac{1}{2}, \frac{1}{2}, \frac{3}{2}, \frac{3}{2}), \nonumber \\
\mu &= (3, 1, 1, \frac{1}{2} + \alpha, \frac{1}{2} - \alpha, \frac{3}{2} - \alpha, \frac{3}{2} + \alpha), \quad \alpha \in \mathbb{R}. \tag{35}
\end{align}
$$

The general solution $\mu$ given in (35) is shown in Figure 19. We can verify by a direct inspection that this matching problem is stabilizable and that $\Pi_{\ge 0} = [-\frac{1}{2}, \frac{1}{2}]$ in kernel coordinates. As in Section 6.1.2, the kernel coordinate $\alpha$ acts like a slider that is positive (resp. negative) if matches along edges $\{3, 4\}$ and $\{5, 6\}$ are more (resp. less) frequent than matches along edges $\{3, 6\}$ and $\{4, 5\}$. Conjecture 6.10 below is supported by an intuition of proof and by extensive simulations discussed later in this section.

<figure><img src="image_50.png" /><figcaption>■ Figure 19 Generic solution of (CE) in the Fish matching problem of (35) with $\lambda = (4, 4, 3, 2, 3, 2)$.</figcaption></figure>

► **Conjecture 6.10.** In the Fish matching problem of (35), we have $\Pi_G =] -\frac{1}{2}, \frac{1}{2}[=\Pi_{>0}$.

Intuition of the proof

We build two families of stable greedy policies, denoted by $(\Phi_k^+)$$_{k \in \mathbb{N}}$ and $(\Phi_k^-)$$_{k \in \mathbb{N}}$, such that $\lim_{k \to +\infty} \alpha(\Phi_k^+) = \frac{1}{2}$ and $\lim_{k \to +\infty} \alpha(\Phi_k^-) = -\frac{1}{2}$. The conclusion then follows from the convexity of the set $\Pi_G$ (Proposition 6.1). We focus on the family $(\Phi_k^+)$$_{k \in \mathbb{N}}$, as the family $(\Phi_k^-)$$_{k \in \mathbb{N}}$ is symmetrical (in the sense that it suffices to exchange classes 4 and 6).

The family $(\Phi_k^+)$$_{k \in \mathbb{N}}$ is defined as follows. Let $\Phi_\infty^+$ denote the edge-priority policy where edges have the following descending priority order: $\{1, 3\}, \{2, 3\}, \{3, 4\}, \{5, 6\}$, followed by all other edges in an arbitrary order. Let $\Phi_0^+$ denote the edge-priority policy where edges have the following descending priority order: $\{3, 4\}, \{2, 3\}, \{1, 3\}, \{5, 6\}$, followed by all other edges in an arbitrary order. The important point is that both policies prioritize edges $\{3, 4\}$ and $\{5, 6\}$ over edges $\{3, 6\}$ and $\{4, 5\}$ (with the hope that this lead to a high $\alpha$), but that $\Phi_\infty^+$ gives higher priority to the “tail” while $\Phi_0^+$ gives higher priority to the “trunk”. Now, for each $k \in \mathbb{N}$, $\Phi_k^+$ is the deterministic size-based policy that follows $\Phi_\infty^+$ when the queue size of class 4 is at most $k-1$ and $\Phi_0^+$ when the queue size of class 4 is at least $k$ (that is, $\Phi_k^+(q, i) = \Phi_\infty^+(q, i)$ if $q_4 \le k-1$ and $\Phi_k^+(q, i) = \Phi_0^+(q, i)$ if $q_4 \ge k$).

The rationale behind this definition is as follows. According to (35), $\alpha$ is maximal (i.e., equal to $\frac{1}{2}$) when $\mu_{3,4}$ is equal to 1 and $\mu_{3,6}$ is equal to 0. If we allow non-greedy policies, $\alpha = \frac{1}{2}$ can be achieved by merely applying the edge-filtering variant of match-the-longest (or any maximally-stable policy) on the bijective subgraph of $G$ obtained by eliminating edge $\{3, 6\}$, that is, by never performing a match between classes 3 and 6. As we will see, the
<figure><img src="image_43.png" /></figure>

(a) $\lambda = (1.2, 1.5, 2, 0.8)$, $\mu = (0, 0, 1.7, 0.5, 1.2, 0, 0.3)$

(b) $\lambda = (1.8, 0.8, 1.4, 1)$, $\mu = (1, 0, 1.4, 1, 0.8, 0, 0)$

<caption>**Figure 14** Reaching the vertex corresponding to $r = (-1, -1, 1, 2, 5, 4, 7)$ in the hypergraph from Figure 13.</caption>

- As noted in [37], the delay experienced by $\Phi_{\beta}$ continues to grow as $1/\beta$, even after the regret reaches zero.

- $\Phi'_{\beta}$ only keeps a bounded delay in the second setting.

- The delay experienced by $\Phi_{\epsilon}$ appears bounded but remains higher than that of $\Phi_{E^{*}}$. This contrasts with the expected convergence to $\Phi_{E^{*}}$, as observed in Section 7.4. We attribute this to unforeseen interactions between the expanded graph, on which $\Phi_{\epsilon}$ dispatches arrivals unevenly, and the virtual queue reservation mechanism.

- For both $\Phi_k$ and $\Phi_{\alpha}$, the delay converges to that of $\Phi_{E^{*}}$, which is with Section 7.4. Adjusting the parameters allow to control the delay/regret trade-off.

### 8.3.2 Augmenting stability

Figure 9 in Section 6 presented a toy example illustrating that the optimal stable policy does not always achieve the optimal achievable reward. This demonstrates that imposing stability can limit performance, as the optimal matching-rate may require discarding a fraction of arrivals and thus be outside of $\Pi_{\ge 0}$. Following [23], this issue can be addressed by augmenting each under-demanded node with a zero-reward mono-edge, thereby allowing the discard of excess items.

In the toy example of Figure 9, adding a mono-edge to class 4 creates a third vertex in the polytope, which zeros the edges $\{2, 4\}$ and $\{3, 4\}$. This vertex is bijective, making $\Phi_{E^{*}}$ both optimal and stable.

The performance of the considered policies under this setting is shown in Figure 15. The most noteworthy findings are:

- $\Phi_{\beta}$ and $\Phi_{\epsilon}$ can have a low regret, but at the cost of high delay.

- All other parameterized policies rapidly converge to $\Phi_{E^{*}}$, with negligible regret/delay trade-off. We believe this is because the target vertex (a perfectly balanced triangle plus one discarded node) already yields low delay, so relaxing the constraints on edges $\{2, 4\}$ and $\{3, 4\}$ has minimal impact.

The case analyzed above is illustrative, but the role of mono-edges extends beyond this specific example. In general, adding mono-edges to a graph increases the dimensionality of the polytope, so that the original feasible region becomes a face of the enlarged polytope.
<figure><img src="image_51.png" /><figcaption>(a) Policy $\Phi_{\infty}^{+}$, followed by policy $\Phi_{k}^{+}$ when the size of queue 4 is at most $k-1$</figcaption></figure>

<figure><img src="image_52.png" /><figcaption>(b) Policy $\Phi_{0}^{+}$, followed by policy $\Phi_{k}^{+}$ when the size of queue 4 is at least $k$</figcaption></figure>

<caption>■ Figure 20 Edge-priority (greedy) policies in the Fish matching problem of (35).</caption>

family $(\Phi_{k}^{+})_{k \in \mathbb{N}}$ of (stable greedy) policies emulates this (non-greedy) edge-filtering policy by favoring edge $\{3, 4\}$ over edge $\{3, 6\}$ while making the probability that $q_4 = 0$ arbitrary small as $k$ increases. Roughly speaking, mixing the policies $\Phi_{\infty}^{+}$ and $\Phi_{0}^{+}$ allows us to control $q_4$: $\Phi_{\infty}^{+}$ is not stable and makes $q_4$ go to infinity, while $\Phi_{0}^{+}$ is stable and reduces $q_4$ when it is large. All in all, $\Phi_{k}^{+}$ keeps the value of $q_4$ around $k$, so that the probability that $q_4 = 0$ is low when $k$ is large. In the limit, $q_4$ is always positive, so that the class-3 items that are not matched with classes 1 or 2 are drained by class 4 (while class 6 is matched only with class 5), so that $\mu_{3,4}(\Phi_{k}^{+})$ tends to 1 and $\mu_{3,6}(\Phi_{k}^{+})$ tends to 0 as $k \to \infty$.

We expect that a rigorous proof that $\mu_{3,6}(\Phi_{k}^{+})$ tends to 0 as $k \to +\infty$ will involve the following steps, some of which may require further investigation or analysis:

1. For each $k \in \mathbb{N}$, the matching model $(G, \lambda, \Phi_{k}^{+})$ is stable. We believe that stability can be proved by applying a fluid-limit argument that generalizes the framework of [18] $^8$. Therefore, for each $k \in \mathbb{N}$, we can consider a random vector $Q_k = (Q_{k,1}, Q_{k,2}, \dots, Q_{k,n})$ distributed like the vector of queue sizes in the matching model $(G, \lambda, \Phi_{k}^{+})$ in stationary regime, and we know that the vector $\mu(\Phi_{k}^{+})$ is well-defined.

2. For each $k \in \mathbb{N}$, by definition of the policy $\Phi_{k}^{+}$, we have

$$ \mu(\Phi_{k}^{+})_{3,6} = \lambda_{3}P(Q_{k,4} = 0, Q_{k,6} > 0) + \lambda_{6}P(Q_{k,3} > 0, Q_{k,5} = 0), \\ \leq (\lambda_{3} + \lambda_{6})P(Q_{k,4} = 0), $$

where the inequality arises because the events $(Q_{k,4} = 0, Q_{k,6} > 0)$ and $(Q_{k,3} > 0, Q_{k,5} = 0)$ are both included into the event $(Q_{k,4} = 0)$ (in the latter case, this is because the greediness of the policy prevents the system from containing unmatched items of classes 3 and 4 at the same time). Consequently, to prove that $\mu(\Phi_{k}^{+})_{3,6} \to 0$, it suffices to prove that $P(Q_{k,4} = 0) \to 0$ as $k \to +\infty$. This argument rigorously supports the intuition that, if class 4 becomes “unstable”, then this class “drains” all class-3 items that are not matched with classes 1 and 2.

3. To prove that $P(Q_{k,4} = 0) \to 0$ as $k \to +\infty$, we believe that we can reason as follows:

- We can prove that, for each $k \in \mathbb{N}$, the conditional average rate at which class 3 is matched with either class 4 or class 6, given that $Q_{k,4} \leq k-1$, is upperbounded by $\lambda_{3}(1 + \frac{\lambda_{1}}{\lambda_{2}+\lambda_{3}-\lambda_{1}} + \frac{\lambda_{2}}{\lambda_{1}+\lambda_{3}-\lambda_{2}})^{-1} = \frac{9}{11}$. This upperbound follows by coupling the fish problem with a “worst-case” matching problem in which there is an infinite backlog of items of classes 4 and 6 to be matched with class 3. Roughly speaking, this worst-case matching problem can be obtained by taking $\lambda_{4} = \lambda_{6} = +\infty$ in the fish problem; then, focusing on nodes 1, 2, and 3, the system behaves like a paw graph with an unstable pendant node obtained by merging classes 4 and 6.

<footnote>$^8$ Formalizing this generalization is outside the scope of this paper and could be the topic of a future work.</footnote>
<figure><img src="image_44.png" /><figcaption>■ **Figure 15** *G*: diamond augmented with {4}; $\lambda = (4, 4, 4, 2)$; $\mu = (2, 2, 2, 0, 0, 2)$; $r = (-1, 1, 1, 1, 3, 2)$ (adversarial).</figcaption></figure>

For instance, augmenting the toy example transforms a segment into a triangle, with one side representing the original feasible set.

Providing one mono-edge per node guarantees that any problem $(G, \lambda)$ is trivially stabilizable, for example by discarding all incoming items. This stabilization mechanism, however, only remedies instability that results from an imbalance leading to systemic over-demanded nodes; vertices that are injective-only remain injective-only after the addition of mono-edges.

It is crucial that mono-edges carry non-negative rewards to ensure that $\Pi_{\ge 0}$ contains the optimal solution. If mono-edges have negative rewards, the discrepancy between stability and optimality may persist. For example, in Figure 14b, the best stable solutions are actually suboptimal due to the discarding of class 1 items with negative reward. In that case, absolute optimality requires the queue for class 1 to grow without bound.

**Remark 7.** If *G* is a simple graph augmented with mono-edges, *Definitions 2–5* remain entirely valid, under the assumption that one mono-edge is an odd cycle. In particular, if each connected component of *G* contains at least one mono-edge, *G* is surjective.

Other definitions and formulas can be likewise adapted. For example, Equation (22), which defines $\delta(G, \lambda)$, works with the convention that a node with a mono-edge does not belong to any independent set. As illustration, one can check that the problem studied in Figure 15 verifies $\delta(G, \lambda) = \delta(G^*, \lambda) = 2$. A graph with mono-edges everywhere translates to $\delta(G, \lambda) = +\infty$ (all incoming items can be processed instantly).
- Using this upperbound, we prove that at least one class among classes 4 and 6 becomes unstable, in the sense that $\lim_{k \to +\infty} P(Q_{k,4} = 0) = 0$ or $\lim_{k \to +\infty} P(Q_{k,6} = 0) = 0$. Since we can verify otherwise that class 6 does not become unstable, it follows that $\lim_{k \to +\infty} P(Q_{k,4} = 0) = 0$.

The complete proof is left as an open question for future works.

## Numerical results

Figure 21 shows the values of the matching rates of $\Phi_k^+$ and $\Phi_k^-$ obtained by simulation, using the setting described in Section 2.5, as functions of the threshold $k \in \mathbb{N}$. The main take-away is that $\alpha(\Phi_k^+)$ and $\alpha(\Phi_k^-)$ seem to converge to $\frac{1}{2}$ and $-\frac{1}{2}$, respectively, thus supporting Conjecture 6.10. Figure 21b, which displays $\mu(\Phi_k^+)^{3,6} = \frac{1}{2} - \alpha(\Phi_k^+)$, suggests that the convergence is linear (with a logarithmic scale on the y-axis), meaning that the rate $\mu(\Phi_k^+)^{3,6}$ decreases like $\gamma^k$ for some $0 < \gamma < 1$. Each curve is obtained by running a simulation consisting of $10^{10}$ steps (as specified in Section 2.5).

<figure><img src="image_53.png" /><figcaption>(a) Evolution of $\alpha(\Phi_k^+)$ and $\alpha(\Phi_k^-)$. (b) Evolution of $\mu(\Phi_k^+)^{3,6} = \frac{1}{2} - \alpha(\Phi_k^+)$. 

**Figure 21** Evolution of the matching rates under $\Phi_k^+$ and $\Phi_k^-$ as functions of the threshold $k$, as defined in the intuition of proof of Conjecture 6.10. Figure 21a is in kernel coordinates, while Figure 21b zooms on $\mu(\Phi_k^+)^{3,6} = \frac{1}{2} - \alpha(\Phi_k^+)$. ■</figcaption></figure>

Figure 22 shows the empirical distribution of the queue sizes under $\Phi_{100}^+$. One can observe in particular that:

- The distribution of $Q_{k,4}$ is centered around $k$. This illustrates the design of $\Phi_k^+$, which aims at “stabilizing” the number of class-4 items in the system around the value $k$. As a consequence, the probability that there is no class-4 item is low.

- Typically, the system does not contain items of classes 3 and 5, which is a consequence of the low probability of having no class-4 items. The presence of class-4 items precludes the presence of items of classes 3 and 5 because the policy is greedy.

- Because of the symmetric roles of classes 1 and 2, the distributions of $Q_{k,1}$ and $Q_{k,2}$ are identical, even though the presence of class-1 and class-2 items is mutually exclusive.

## 6.2 Arbitrary policies

We now focus on $\Pi_P \subseteq \Pi_{\ge 0}$, the set of matching rate vectors that can be achieved by an arbitrary stable policy. A simple necessary and sufficient condition for a vertex of $\Pi_{\ge 0}$ to
References

1 Ivo Adan, Ana Bušić, Jean Mairesse, and Gideon Weiss. Reversibility and Further Properties of FCFS Infinite Bipartite Matching. Mathematics of Operations Research, 43(2):598–621, December 2017. Publisher: INFORMS. doi:10.1287/moor.2017.0874.

2 Ivo Adan and Gideon Weiss. Exact FCFS matching rates for two infinite multitype sequences. Operations Research, 60(2):475–489, 04 2012. Publisher: INFORMS. doi:10.1287/opre.1110.1027.

3 Angelos Aveklouris, Levi DeValve, Maximiliano Stock, and Amy Ward. Matching impatient and heterogeneous demand and supply. Operations Research, 73(3):1637–1658, may 2025. Publisher: INFORMS. doi:10.1287/opre.2022.0005.

4 Egon Balas and William R. Pulleyblank. The perfectly matchable subgraph polytope of a bipartite graph. Networks, 13(4):495–516, 1983. doi:10.1002/net.3230130405.

5 Jocelyn Begeot, Irène Marcovici, and Pascal Moyal. Stability regions of systems with compatibilities and ubiquitous measures on graphs. Queueing Systems, 103(3):275–312, 2023. doi:10.1007/s11134-023-09872-0.

6 Jocelyn Begeot, Irène Marcovici, Pascal Moyal, and Youssef Rahme. A general stochastic matching model on multigraphs. arXiv:2011.05169 [math], November 2020. arXiv: 2011.05169. URL: http://arxiv.org/abs/2011.05169.

7 Péter Biró, Joris van de Klundert, David Manlove, William Pettersson, Tommy Andersson, Lisa Burnapp, Pavel Chromy, Pablo Delgado, Piotr Dworczak, Bernadette Haase, Aline Hemke, Rachel Johnson, Xenia Klimentova, Dirk Kuypers, Alessandro Nanni Costa, Bart Smeulders, Frits Spieksma, María O. Valentín, and Ana Viana. Modelling and optimisation in european kidney exchange programmes. European Journal of Operational Research, 291(2):447–456, 2021. doi:10.1016/j.ejor.2019.09.006.

8 Pierre Bremaud. Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues. Texts in Applied Mathematics. Springer-Verlag, New York, 1999. URL: https://www.springer.com/gp/book/9780387985091, doi:10.1007/978-1-4757-3124-8.

9 Ana Bušić, Varun Gupta, and Jean Mairesse. Stability of the Bipartite Matching Model. Advances in Applied Probability, 45(2):351–378, June 2013. Publisher: Cambridge University Press. doi:10.1239/aap/1370870122.

10 Ana Bušić and Sean Meyn. Approximate optimality with bounded regret in dynamic matching models. arXiv:1411.1044 [cs, math], June 2016. arXiv: 1411.1044. URL: http://arxiv.org/abs/1411.1044.

11 Arnaud Cadas, Ana Bušić, and Josu Doncel. Optimal control of dynamic bipartite matching models. In Proceedings of the 12th EAI International Conference on Performance Evaluation Methodologies and Tools, VALUETOOLS 2019, Universitat de les Illes Balears, Palma de Mallorca, Spain, March 12-15, 2019, pages 39–46. ACM, 2019. doi:10.1145/3306309.3306317.

12 Arnaud Cadas, Josu Doncel, Jean-Michel Fourneau, and Ana Bušić. Flexibility can hurt dynamic matching system performance. arXiv:2009.10009 [cs, math], September 2020. arXiv: 2009.10009. URL: http://arxiv.org/abs/2009.10009.

13 René Caldentey, Edward H. Kaplan, and Gideon Weiss. FCFS infinite bipartite matching of servers and customers. Advances in Applied Probability, 41(3):695–730, 09 2009. Publisher: Cambridge University Press. doi:10.1239/aap/1253281061.

14 Céline Comte, Fabien Mathieu, and Ana Bušić. Stochastic dynamic matching: A mixed graph-theory and linear-algebra approach. working paper or preprint, December 2021. URL: https://hal.science/hal-03502084v1.

15 Céline Comte and Jaap Storm. Global and local stability in parallel service systems with redundancy, 2022. Unpublished.

16 Céline Comte. Stochastic non-bipartite matching models and order-independent loss queues. Stochastic Models, 38(1):1–36, January 2022. doi:10.1080/15326349.2021.1962352.

17 Céline Comte and Jan-Pieter Dorsman. Performance Evaluation of Stochastic Bipartite Matching Models. In Performance Engineering and Stochastic Modeling, Lecture Notes in
<figure><img src="image_54.png" /><figcaption>Figure 22 Empirical complementary cumulative distribution function (CCDF) of the queue sizes under policy $\Phi_k^+$ for $k = 100$.</figcaption></figure>

belong to $\Pi_P$ was already derived in Proposition 5.7: if $\mu$ is a vertex of $\Pi_{\ge 0}$, then $\mu \in \Pi_P$ if and only if the vertex $\mu$ is bijective (in the sense that its support graph is bijective). Proposition 6.11 uses this result to characterize which faces of the polytope $\Pi_{\ge 0}$ can be entirely covered by stable policies.

**Proposition 6.11.** For each face $F$ of the polytope $\Pi_{\ge 0}$, we have $F \subseteq \Pi_P$ if and only if all vertices of $F$ are bijective. In particular, $\Pi_P = \Pi_{\ge 0}$ if and only if the polytope $\Pi_{\ge 0}$ is simple and the matching problem $(G, \lambda)$ is essential.

**Proof.** The first statement is a consequence of the convexity result of Proposition 6.1 and the characterization of the vertices of the polytope $\Pi_{\ge 0}$ in Proposition 5.7. The second statement is a consequence of Proposition 5.13. ▶

Achieving injective-only vertices

Although Proposition 5.7 shows that injective-only vertices cannot be achieved by stable policies, we now introduce a sequence of stable policies that we conjecture yield a sequence of matching rate vectors that are arbitrarily close a vertex of the polytope $\Pi_{\ge 0}$, even if this vertex is injective-only. This conjecture is supported by numerical results shown later in this section.

**Conjecture 6.12.** Consider a vertex $\mu$ of $\Pi_{\ge 0}$ and let $G = (V, E)$ denote its support graph. For each $k \in \mathbb{N}$, consider the following semi-filtering policy, denoted by $\Phi_k(\mu)$:

- If the size of the longest queue is less than $k$, apply the filtering match-the-longest policy adapted to $G$ with filter $E$;

- Otherwise, apply the greedy match-the-longest policy adapted to $G$.

$\Phi_k(\mu)$ is stable for each $k \in \mathbb{N}$ and $\lim_{k \to \infty} \mu(\Phi_k(\mu)) = \mu$.

**Intuition of the proof.** In essence, the approach is similar to the one that supports Conjecture 6.10: we take a possibly unstable policy that achieves the desired goal (a matching rate vector equal to $\mu$), and we make it stable by reverting to a stable policy when the queue sizes become too large. If the threshold is large enough, most matches will be made under the unstable policy that achieves the desired goal.

We present here a sketch of proof for the case where $G$ is a bipartite graph, more precisely a tree (like the support graphs of the vertices in Example 3.13 when $\lambda_1 = \bar{\lambda}_2 = \bar{\lambda}_3 = \lambda_4$).
Computer Science, pages 425–440. Springer International Publishing, 2021. doi:10.1007/978-3-030-91825-5_26.

18 Dragoš Cvetkovic, Peter Rowlinson, and Slobodan Simic. *Spectral Generalizations of Line Graphs: On Graphs with Least Eigenvalue -2*. London Mathematical Society Lecture Note Series. Cambridge University Press, 2004. doi:10.1017/CB09780511751752.

19 J. G. Dai. On positive harris recurrence of multiclass queueing networks: A unified approach via fluid limit models. *The Annals of Applied Probability*, 5(1):49-77, 1995. Publisher: Institute of Mathematical Statistics. doi:10.1214/aoap/1177004828.

20 Reinhard Diestel. *Graph Theory*. Springer Publishing Company, Incorporated, 5th edition, August 2017.

21 Michael Doob. An interrelation between line graphs, eigenvalues, and matroids. *Journal of Combinatorial Theory, Series B*, 15(1):40–50, 08 1973. doi:10.1016/0095-8956(73)90030-0.

22 David Gregory. Hall conditions for edge-weighted bipartite graphs. Technical report, Queen's University, 2010.

23 Varun Gupta. Greedy algorithm for multiway matching with bounded regret. *Operations Research*, 72(3):1139–1155, 2024.

24 Itai Gurvich and Amy Ward. On the Dynamic Control of Matching Queues. *Stochastic Systems*, 4(2):479–523, October 2014. Publisher: INFORMS. doi:10.1287/13-SSY097.

25 B. Hajek. *Random Processes for Engineers*. Cambridge university press, 2015.

26 Matthieu Jonckheere, Pascal Moyal, Claudia Ramírez, and Nahuel Soprano-Loto. Generalized max-weight policies in stochastic matching. *arXiv:2011.04535 [math]*, November 2020. arXiv: 2011.04535. URL: http://arxiv.org/abs/2011.04535.

27 N. Karmarkar. A new polynomial-time algorithm for linear programming. In *Proceedings of the sixteenth annual ACM symposium on Theory of computing*, STOC '84, pages 302–311, New York, NY, USA, December 1984. Association for Computing Machinery. doi: 10.1145/800057.808695.

28 F. P. Kelly. *Reversibility and Stochastic Networks*. Cambridge University Press, 2011.

29 Süleyman Kerimov, Itai Ashlagi, and Itai Gurvich. On the optimality of greedy policies in dynamic matching. *Operations Research*, 2023.

30 Süleyman Kerimov, Itai Ashlagi, and Itai Gurvich. Dynamic matching: Characterizing and achieving constant regret. *Management Science*, 70(5):2799–2822, 2024.

31 John D. C. Little. A proof for the queuing formula: $l = \lambda w$. *Operations Research*, 9(3):383–387, 1961. doi:10.1287/opre.9.3.383.

32 John D. C. Little. Little's law as viewed on its 50th anniversary. *Operations Research*, 59(3):536–549, 2011. doi:10.1287/opre.1110.0940.

33 László Lovász and M. D. Plummer. *Matching Theory*. American Mathematical Soc., 2009.

34 Jean Mairesse and Pascal Moyal. Stability of the stochastic matching model. *Journal of Applied Probability*, 53(4):1064–1077, 12 2016. Publisher: Cambridge University Press. doi:10.1017/jpr.2016.65.

35 Fabien Mathieu. Stochastic Matching, 2022. URL: https://balouf.github.io/stochasticMatching/index.html.

36 Pascal Moyal, Ana Bušić, and Jean Mairesse. A product form for the general stochastic matching model. *Journal of Applied Probability*, 58(2):449–468, 06 2021. doi:10.1017/jpr.2020.100.

37 Mohammadreza Nazari and Alexander L. Stolyar. Reward maximization in general dynamic matching systems. *Queueing Systems*, 91(1):143–170, February 2019. doi:10.1007/s11134-018-9593-y.

38 J. R. Norris. *Markov Chains*. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 1997. doi:10.1017/CB09780511810633.

39 Youssef Rahme and Pascal Moyal. A stochastic matching model on hypergraphs. *Advances in Applied Probability*, 53(4):951–980, December 2021. doi:10.1017/apr.2021.8.
The tree case is the most difficult to handle. If $\underline{G}$ is a unicyclic graph with an odd cycle, the problem is simplified by the stabilizability of $(\underline{G}, \lambda)$. If $\underline{G}$ is made of multiple connected components, the proof needs to compare the model to a virtual model where each component acts independently and accounts for the interactions between the components. For example, when one the queue is longer than $k$, all components may interact when decisions follow the match-the-longest policy on the graph $G$.

The stability of the model $(G, \lambda, \Phi_k(\mu))$ for each $k \in \mathbb{N}$ can be proved using the Lyapunov-Foster theorem [8, Theorem 1.1 in Chapter 5], using the fact that, outside a finite set of states (those where all queues are shorter than $k$), the policy $\Phi_k(\mu)$ behaves like the stable match-the-longest policy on the graph $G$. Consider a random vector $Q = (Q_1, Q_2, \dots, Q_n)$ distributed like the vector of queue sizes in the matching model $(G, \lambda, \Phi_k(\mu))$ in stationary regime, and let $Q_+ = \sum_{i \in V_+} Q_i$ and $Q_- = \sum_{i \in V_-} Q_i$ denote the total queue sizes in the parts $V_+$ and $V_-$ of the (bipartite) graph $\underline{G}$. Also let $L_+ = \max(Q_i, i \in V_+)$, $L_- = \max(Q_i, i \in V_-)$, and $L = L_+$ if $L_+ \ge L_-$ and $L = -L_-$ if $L_+ < L_-$, so that $|L|$ is the size of the longest queue and the sign of $L$ indicates the part $(V_+ \text{ or } V_-)$ to which this queue belongs. The random variable $L$ will play a crucial role in the proof. Lastly, we let $p_\ell = \mathbb{P}(L = \ell)$, $\ell \in \{\dots, -2, -1, 0, 1, 2, \dots\}$, denote its distribution. The dependency of these random variables on $k$ (via the policy $\Phi_k(\mu)$) is left implicit to simplify notation.

To show that $\lim_{k \to \infty} \mu(\Phi_k(\mu)) = \mu$, we need to upperbound the probability that a match is performed along an edge that does not belong to the support of the vertex $\mu$. To do this, we upperbound the probability of applying the greedy match-the-longest policy on the whole graph $G$, i.e., the probability $\sum_{|\ell| \ge k} p_\ell$ that the size of the longest queue is $k$ or more.

Intuitively, we expect that the stability of the match-the-longest policy implies a uniform drift of the size of the longest queue towards the origin whenever this size is larger than $k$, provided that $k$ is large enough. Formally, we conjecture that there exist $K \in \mathbb{N}$ and $0 < \rho < 1$ such that, for each $k \ge K$, we have under $\Phi_k$ that $p_{\ell+1} \le \rho p_\ell$ for each $\ell \ge k$ and $p_{\ell-1} \le \rho p_\ell$ for each $\ell \le -k$. In particular, $\sum_{\ell \ge k} p_\ell \le \frac{1}{1-\rho} p_k$ and $\sum_{\ell \le -k} p_\ell \le \frac{1}{1-\rho} p_{-k}$. This implies that, if $p_k$ and $p_{-k}$ go to 0 as $k$ goes to infinity, the probability that the filter on $\underline{E}$ is disabled goes to 0 as well.

To control $p_k$ and $p_{-k}$, we now need to consider the cases where the size of the longest queue is at most $k$. We argue that, as long as $|L| \le k$, the dynamics of $L$ is mainly controlled by an unbiased random walk between the two parts of the bipartite graph. More precisely, as long as $|L| \le k$, the difference $Q_+ - Q_-$ behaves like an unbiased random walk because any arrival of a class in $V_+$ increases the difference by one, any arrival of a class in $V_-$ decreases the difference by one, and the arrival rates of $V_+$ and $V_-$ are equal (see Equation (24)). We conjecture that, when $|Q_+ - Q_-|$ is large enough (while still satisfying $|L| \le k$), a distinctive structure emerges due to the filtered match-the-longest policy: the queues in one part of the graph have approximately equal sizes, while the queues in the other part are empty. In particular, we conjecture that the typical states of the system (when $|L| \le k$) verify (in some sense) $L \approx \frac{Q_+-Q_-}{|V_+|}$ if $Q_+ > Q_-$ and $L \approx \frac{Q_+-Q_-}{|V_-|}$ if $Q_+ < Q_-$. In a true unbiased random walk over a bounded range of integers, all states have equal probabilities. By comparing the evolutions of $L$ and $Q_+-Q_-$ and taking into account the border cases ($|L| = k$), we conjecture that there exist $K' \in \mathbb{N}$ and $c > 0$ such that, if $k \ge K'$, then $p_\ell \ge c \max(p_k, p_{-k})$ for all $\ell \in \{-k, \dots, -1, 0, 1, \dots, k\}$. In particular, both $p_k$ and $p_{-k}$ should be upperbounded by $(c(2k+1))^{-1}$ when $k$ is large enough.

By combining the two cases $|L| \ge k$ and $|L| \le k$, we get $\sum_{|\ell| \ge k} p_\ell = O(1/k)$. In other words, the probability that the size of the longest queue is greater than $k$ tends to 0 as $k$ goes to infinity. As matchings outside $\underline{E}$ occur only when the size of the longest queue is greater
40 R. Srikant and Lei Ying. *Communication Networks: An Optimization, Control and Stochastic Networks Perspective*. Cambridge University Press, New York, NY, USA, 2014.
41 Yehua Wei, Jiaming Xu, and Sophie H Yu. Constant regret primal-dual policy for multi-way dynamic matching. In *Abstract Proceedings of the 2023 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems*, pages 79–80, 2023.
42 Günter M. Ziegler. *Lectures on polytopes*. Springer-Verlag, New York, 1995. URL: http://www.worldcat.org/search?qt=worldcat_org_all&q=9780387943657.
than $k$, we conclude that the matching rate of an edge outside $\underline{E}$ goes to 0, which by continuity of the conservation principle and injectivity of $\underline{G}$ implies that $\lim_{k \to \infty} \mu(\Phi_k(\mu)) = \mu$. ◀

One drawback of the semi-filtering policies introduced in Conjecture 6.12 is that, as $k \to +\infty$ and we approach an injective-only vertex, the average size of the longest queue tends to grow. Therefore, there is a trade-off between approaching an injective-only vertex and minimizing the waiting time. This issue is similar to the threshold-based greedy policies introduced in Conjecture 6.10, where the vertices of $\Pi_{\ge 0}$ could be reached asymptotically by increasing the average size of a queue.

**Remark 6.13.** In [29], a family of policies is introduced to optimize a reward function on edges. The goal is similar to ours, with two main differences: first, the aim is to optimize a reward function on matching rates without providing a description of the limit rate vector, while we show that the limit rate vector is a vertex of $\Pi_{\ge 0}$; second, each policy of the family makes decisions based on a utility function that is a convex combination of the edge-dependent reward and the queue size, and matching decisions are based on virtual queues that can become negative. The policies are indexed by the coefficient $\beta$ of the convex combination, which determines the trade-off between maximizing the reward and minimizing the queue size, and which is the counterpart of the threshold $k$. Yet, the authors also notice in their simulations that the queue sizes grow as $1/\beta$, which is the counterpart of our $k$.

If Conjecture 6.12 holds, which we strongly believe and will support with numerical results, we obtain a simple characterization of the matching rates that can be achieved by a stable policy.

**Corollary 6.14.** Any positive solution of the conservation equation (CE-2) can be obtained by a stable policy. In other words,

$$ \Pi_{>0} \subseteq \Pi_{\mathcal{P}} \subseteq \Pi_{\ge 0}. $$

**Proof.** We establish that $\Pi_{\mathcal{P}} \subseteq \Pi_{\ge 0}$ by recalling that any stable policy yields a matching rate vector that satisfies (CE) and has non-negative coordinates.

We now prove that $\Pi_{>0} \subseteq \Pi_{\mathcal{P}}$. The closure of $\Pi_{\mathcal{P}}$ is convex, as $\Pi_{\mathcal{P}}$ itself is convex. According to Conjecture 6.12, the closure of $\Pi_{\mathcal{P}}$ contains all the vertices of $\Pi_{\ge 0}$, thereby encompassing $\Pi_{\ge 0}$ as well by convexity. Consequently, still by virtue of convexity, $\Pi_{\mathcal{P}}$ contains the interior<fnref n="9" /> of its closure, which includes the interior of $\Pi_{\ge 0}$, denoted as $\Pi_{>0}$. ◀

## Numerical results

To provide a numerical support for Conjecture 6.12, we evaluated $\Phi_k(\mu)$ for some injective-only vertices. We first considered the diamond problem (30) with $\lambda_1 = \bar{\lambda}_2 = \bar{\lambda}_3 = \lambda_4 = \frac{1}{4}$ and $\beta = \frac{1}{8}$. The two vertices of $\Pi_{\ge 0}$ have injective-only support graphs that are identical up to permutation of nodes 2 and 3. We choose to focus on the vertex $\mu = (\frac{1}{8}, 0, \frac{1}{8}, 0, \frac{1}{8})$: its support consists of the line $\{1, 2\}, \{2, 3\}, \{3, 4\}$ (a simple example of a tree), so that the edges $\{1, 3\}$ and $\{2, 4\}$ should be avoided. Each curve is obtained by running a simulation consisting of $10^{10}$ steps (as specified in Section 2.5).

Figure 23 shows the convergence of $\mu(\Phi_k(\mu))$ to $\mu$ by measuring as a function of $k$ the leaking rate $\mu_{1,3}(\Phi_k(\mu)) + \mu_{2,4}(\Phi_k(\mu))$, i.e., the total matching rates observed along the

<footnote n="9">⁹ Here the notion of interior is relative to the canonic topology of the $d$-dimensional affine space of the solutions of the conservation equation.</footnote>
A Supplementary material of Section 2.3.4 (Other policies).

Our results are not limited to deterministic size-based policies but apply to a broader family of policies that are either random or require a more complex state descriptor, or both. We now introduce this family of policies, with the goal of being as general as possible.

A.1 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 [28, 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="19" />.

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}, \ 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. FCFM (e.g., see [16, 36]) is a classical example of a deterministic policy that is not size-based: its state space is

<footnote n="19">¹⁹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 20 and 26. 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>
forbidden edges {1,3} and {2,4}. The convergence seems to be logarithmic, i.e., like $1/k$. This is in line with the intuition of the proof of Conjecture 6.12, which states that the probability to enable forbidden edges should behave like $O(1/k)$. The leaking rate achievable by $\Phi_+$, the greedy edge-priority policy defined in Proposition 6.8, is displayed for comparison purposes. $\Phi_+$ minimizes the leaking rate among all greedy policies. As expected, $\Phi_k(\mu)$ yields a lower leaking rate than $\Phi_+$ for large values of $k$. However, it can be observed that $\Phi_0(\mu)$ exhibits a higher leaking rate. This is actually expected: when $k=0$, filtering is completely disabled, and thus $\Phi_0(\mu)$ represents the match-the-longest (greedy) policy, which does not attempt to reduce matchings along the forbidden edges.

<figure><img src="image_55.png" /><figcaption>Figure 23 Total matching rate along the forbidden edges under policy $\Phi_k(\mu)$ in the diamond problem of (30), with $\lambda_1 = \bar{\lambda}_2 = \bar{\lambda}_3 = \lambda_4 = \frac{1}{4}$ and $\beta = \frac{1}{8}$. The vertex $\mu$ has support $\{1, 2\}, \{2, 3\}, \{3, 4\}$, so that the edges to avoid are $\{1, 3\}$ and $\{2, 4\}$. The performance of the greedy edge-priority policy $\Phi_+$ is displayed for comparison.</figcaption></figure>

As mentioned previously, approaching an injective-only vertex should cause the queues to become arbitrarily large. To support this assertion, we studied by simulation the empirical distributions of the queue sizes. Although we do not believe that the sizes of all four classes of the model ($D, \lambda, \Phi_k(\mu)$) follow the same distribution, the difference was not visible in our observations because it is only of second order compared to the overall increase of queue size as $k$ increases. Figure 24a presents, for various values of $k$, the unique observed distribution. For a given class $i$, the following comments can be made:

- The queue is empty half of time. Referring to the intuition of the proof of Conjecture 6.12, this is related to our observation that, as long as the maximum queue size is below $k$, there is always one part of the bipartite subgraph whose queues are empty, and the difference $Q_+ - Q_-$ in total queue size between the two parts behaves like an unbiased random walk. This is due to the fact that the total arrival rates within each part are equal to each other. See Example 3.12 and Remark 5.8 for more insights.

- Otherwise, the size of queue $i$ appears to follow a uniform distribution on $\{1, 2, \dots, k\}$.

- The probability that the size of queue $i$ exceeds $k$ seems to be negligible (as observed in Figure 23, we conjecture a decrease in $O(1/k)$).

These observations align with the intuition of proof that supports Conjecture 6.12. In particular, most of the time, the queue sizes are short (i.e., below $k$) and we apply a filtering policy, so that the evolution of the queue sizes resembles an unbiased random walk truncated by $k$. The difficulty in distinguishing between the distributions of different queue sizes can be attributed to the fact that all distributions are primarily influenced by this unbiased random
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 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 20.

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 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).

**Remark 8 (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 9 (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 [34, 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 [16, 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.

## A.2 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 34 and 36.

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 (27) $$

We say that policy $\Phi_1$ can be reduced to policy $\Phi_2$ and that $\langle\cdot\rangle$ is a reduction function. If $((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 $(\langle S_{2,t} \rangle, I_t, J_{2,t})$ have the same distribution. Conclusion (ii) follows from an
walk. In comparison, Figure 24b presents the empirical CCDF of the queue sizes under $\Phi_+$, yielding the following insights:

■ The queue sizes are smaller under $\Phi_+$ compared to $\Phi_k(\mu)$.

■ Due to symmetry in the matching model, $Q_1$ and $Q_4$ follow the same distribution, as do $Q_2$ and $Q_3$. These two distributions are clearly distinguished by the simulations.

<figure><img src="image_56.png" /><figcaption>(a) Empirical queue size distribution under $\Phi_k(\mu)$.</figcaption></figure>

<caption>(b) Empirical queue size distributions under $\Phi_+$.</caption>

■ **Figure 24** Queue distributions of $\Phi_k(\mu)$ and $\Phi_+$ for the diamond problem (30).

We made the same experiments on the codomino matching problem of Example 5.11. We choose the injective-only vertex $\mu$ depicted in Figure 15f: its support consists of three non-adjacent edges {1, 6}, {2, 3}, {4, 5}, that is, three connected components that are all bipartite. Edges {1, 2}, {2, 6}, {3, 4}, {3, 5}, and {5, 6} should be avoided.

Figure 25 measures the *leaking rate* of $\Phi_k(\mu)$ along the five forbidden edges as $k$ increases. As before, the convergence seems to be logarithmic, i.e., of order $1/k$. We also designed for comparison a greedy policy similar to $\Phi_+$ but adapted to the codomino. This policy, which we also call $\Phi_+$ by convenience, is the edge-priority policy adapted to the codomino graph whereby: edges {1, 6}, {2, 3}, {4, 5} have the highest priority; edges {2, 6} and {3, 5} have the lowest priority. We leave it to the reader to verify that this policy is properly defined in the sense that all possible matching decisions are unambiguous. As for the diamond problem, we observe that $\Phi_k(\mu)$ yields a lower leaking rate than $\Phi_+$ except for $k = 0$, where it behaves like the *match-the-longest* policy and does not take the vertex $\mu$ into account at all.

Figure 26 presents the empirical distribution of the queue sizes. Like for the diamond problem, the simulations do not show visible differences between the distributions of different classes. Figure 26a shows the (unique) empirical distribution for various values of $k$. We observe again that the queues are empty half of time, and that otherwise they follow a (relatively) uniform distribution on {0, 1, 2, ..., $k$}. In comparison, the queues under policy $\Phi_+$, displayed in Figure 26b, are more compact. That $Q_1$, $Q_2$, and $Q_5$ have the same distribution as $Q_4$, $Q_3$, and $Q_6$, respectively, is a consequence of the model symmetry.

References

1. Ivo Adan, Ana Bušić, Jean Mairesse, and Gideon Weiss. Reversibility and Further Properties of FCFS Infinite Bipartite Matching. Mathematics of Operations Research, 43(2):598–621, December 2017. Publisher: INFORMS. doi:10.1287/moor.2017.0874.
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 34 and 36. In this case, (27) says that, for each $s_2 \in S_2$ and $i \in V$, there exist $j \in V \cup \{\perp\}$ and $s'_2 \in S_2$ such that $\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) = 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 follows 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}$.
<figure><img src="image_57.png" /><figcaption>Figure 25 Total matching rate along the forbidden edges under policy $\Phi_k(\mu)$ for the codomino problem defined from Example 5.11. $\mu$ is the vertex depicted in Figure 15f. The performance of $\Phi_+$, an edge-priority policy that prioritizes the support of $\mu$, is displayed for comparison.</figcaption></figure>

<figure><img src="image_58.png" /><figcaption>(a) Empirical queue size distribution under $\Phi_k(\mu)$.</figcaption></figure>

<caption>(b) Empirical queue size distributions under $\Phi_+$.</caption>

<caption>Figure 26 Queue distributions of $\Phi_k(\mu)$ and $\Phi_+$ for the codomino problem described in Example 5.11.</caption>

2 Ivo Adan and Gideon Weiss. Exact FCFS matching rates for two infinite multitype sequences. *Operations Research*, 60(2):475–489, 04 2012. Publisher: INFORMS. doi:10.1287/opre.1110.1027.

3 Angelos Aveklouris, Levi DeValve, and Amy R. Ward. Matching Impatient and Heterogeneous Demand and Supply. *arXiv:2102.02710 [cs, eess, math]*, December 2021. arXiv: 2102.02710. URL: http://arxiv.org/abs/2102.02710.

4 Egon Balas and William R. Pulleyblank. The perfectly matchable subgraph polytope of a bipartite graph. *Networks*, 13(4):495–516, 1983. doi:10.1002/net.3230130405.

5 Jocelyn Begeot, Irène Marcovici, and Pascal Moyal. Stability regions of systems with compatibilities and ubiquitous measures on graphs. *Queueing Systems*, 103(3):275–312, 2023. doi:10.1007/s11134-023-09872-0.

6 Jocelyn Begeot, Irène Marcovici, Pascal Moyal, and Youssef Rahme. A general stochastic matching model on multigraphs. *arXiv:2011.05169 [math]*, November 2020. arXiv: 2011.05169. URL: http://arxiv.org/abs/2011.05169.
**B Supplementary material of Section 3 (Graph theory and linear algebra).**

**B.1 Proofs of Section 3.2 (Surjectivity, injectivity, and bijectivity)**

**Proof of Definition 2.** 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 [18, 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. ◀

**Proof of Definition 3.** 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 we distinguish the following two cases:

- If $G$ is non-bipartite, according to Definition 2, 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 2. 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 $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. ◀

**Proof of Definition 4.** 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 2 and 3. ◀
7 Péter Biró, Joris van de Klundert, David Manlove, William Pettersson, Tommy Andersson, Lisa Burnapp, Pavel Chromy, Pablo Delgado, Piotr Dworczak, Bernadette Haase, Aline Hemke, Rachel Johnson, Xenia Klimentova, Dirk Kuypers, Alessandro Nanni Costa, Bart Smeulders, Frits Spieksma, María O. Valentín, and Ana Viana. Modelling and optimisation in european kidney exchange programmes. *European Journal of Operational Research*, 291(2):447–456, 2021. doi:10.1016/j.ejor.2019.09.006.

8 Pierre Bremaud. *Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues*. Texts in Applied Mathematics. Springer-Verlag, New York, 1999. URL: https://www.springer.com/gp/book/9780387985091, doi:10.1007/978-1-4757-3124-8.

9 Ana Bušić, Varun Gupta, and Jean Mairesse. Stability of the Bipartite Matching Model. *Advances in Applied Probability*, 45(2):351–378, June 2013. Publisher: Cambridge University Press. doi:10.1239/aap/1370870122.

10 Ana Bušić and Sean Meyn. Approximate optimality with bounded regret in dynamic matching models. *arXiv:1411.1044 [cs, math]*, June 2016. arXiv: 1411.1044. URL: http://arxiv.org/abs/1411.1044.

11 Arnaud Cadas, Ana Bušić, and Josu Doncel. Optimal control of dynamic bipartite matching models. In *Proceedings of the 12th EAI International Conference on Performance Evaluation Methodologies and Tools, VALUETOOLS 2019, Universitat de les Illes Balears, Palma de Mallorca, Spain, March 12-15, 2019*, pages 39–46. ACM, 2019. doi:10.1145/3306309.3306317.

12 Arnaud Cadas, Josu Doncel, Jean-Michel Fourneau, and Ana Bušić. Flexibility can hurt dynamic matching system performance. *arXiv:2009.10009 [cs, math]*, September 2020. arXiv: 2009.10009. URL: http://arxiv.org/abs/2009.10009.

13 René Caldentey, Edward H. Kaplan, and Gideon Weiss. FCFS infinite bipartite matching of servers and customers. *Advances in Applied Probability*, 41(3):695–730, 09 2009. Publisher: Cambridge University Press. doi:10.1239/aap/1253281061.

14 Céline Comte and Jaap Storm. Global and local stability in parallel service systems with redundancy. Unpublished.

15 Céline Comte. Stochastic non-bipartite matching models and order-independent loss queues. *Stochastic Models*, 38(1):1–36, January 2022. doi:10.1080/15326349.2021.1962352.

16 Céline Comte and Jan-Pieter Dorsman. Performance Evaluation of Stochastic Bipartite Matching Models. In *Performance Engineering and Stochastic Modeling*, Lecture Notes in Computer Science, pages 425–440. Springer International Publishing, 2021. doi:10.1007/978-3-030-91825-5_26.

17 Dragoš Cvetkovic, Peter Rowlinson, and Slobodan Simic. *Spectral Generalizations of Line Graphs: On Graphs with Least Eigenvalue* -2. London Mathematical Society Lecture Note Series. Cambridge University Press, 2004. doi:10.1017/CBO9780511751752.

18 J. G. Dai. On positive harris recurrence of multiclass queueing networks: A unified approach via fluid limit models. *The Annals of Applied Probability*, 5(1):49–77, 1995. Publisher: Institute of Mathematical Statistics. doi:10.1214/aoap/1177004828.

19 Reinhard Diestel. *Graph Theory*. Springer Publishing Company, Incorporated, 5th edition, August 2017.

20 Michael Doob. An interrelation between line graphs, eigenvalues, and matroids. *Journal of Combinatorial Theory, Series B*, 15(1):40–50, 08 1973. doi:10.1016/0095-8956(73)90030-0.

21 Itai Gurvich and Amy Ward. On the Dynamic Control of Matching Queues. *Stochastic Systems*, 4(2):479–523, October 2014. Publisher: INFORMS. doi:10.1287/13-SSY097.

22 Matthieu Jonckheere, Pascal Moyal, Claudia Ramírez, and Nahuel Soprano-Loto. Generalized max-weight policies in stochastic matching. *arXiv:2011.04535 [math]*, November 2020. arXiv: 2011.04535. URL: http://arxiv.org/abs/2011.04535.

23 N. Karmarkar. A new polynomial-time algorithm for linear programming. In *Proceedings of the sixteenth annual ACM symposium on Theory of computing*, STOC '84, pages 302–311, New York, NY, USA, December 1984. Association for Computing Machinery. doi: 10.1145/800057.808695.
**Proof of Proposition 6.** These statements (transposed to A) are again well-known in linear algebra. ◀

## B.2 Proof of Proposition 8 in Section 3.3.2 (Stabilizable matching problem)

Equivalence of i and ii follows from [34, Proposition 2 and Theorem 2]. For completeness, we observe that [34, 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 [34], under condition ii, $(G, \lambda, \Phi)$ is stable when $\Phi$ is the ML policy, and (b) the associated vector $\mu$ of matching rates satisfies condition iii by ergodicity. That condition iii implies condition ii was proved by [16, Lemma 12]. ◀

## B.3 Minimal stability region for greedy matching policies (Section 3.4.3 and Appendices F.2.1 and F.2.2).

The following result gives a sufficient stability condition for greedy matching policies. The proof relies on a linear Lyapunov function. This result can be seen as the counterpart of [9, Proposition 5.1] for non-bipartite matching models.

**Proposition 26.** Consider a matching problem $(G, \lambda)$ with a connected graph $G$. If

$$ \sum_{i \in V(\mathcal{I})} \lambda_i > \frac{1}{2} \sum_{i \in V} \lambda_i, \quad \mathcal{I} \in \mathbb{I}, \qquad (28) $$

then the matching model $(G, \lambda, \Phi)$ is stable for every greedy matching policy $\Phi$.

**Proof.** Consider a matching problem $(G, \lambda)$ that satisfies (28) and a greedy matching policy $\Phi$ adapted to the graph $G$. Since the Markov chain $(S_t, t \in \mathbb{N})$ associated with the matching model $(G, \lambda, \Phi)$ depends on the vector $\lambda$ only up to a positive multiplicative constant, we can assume without loss of generality that $\sum_{i \in V} \lambda_i = 1$. Let $S$ denote the state space of this Markov chain and $|\cdot|$ the corresponding queue-size function (as defined in Appendix A). We consider the Lyapunov function $F: S \to \mathbb{R}$ defined by $F(s) = \sum_{i \in V} |s_i|$ (that is, $F(s)$ is the number of unmatched items in state $s$) for each $s \in S$. For each $t \in \mathbb{N}$ and $s \in S$, we have

$$ \mathbb{E}(F(S_{t+1}) | S_t = s) - F(s) = \sum_{i \in V \setminus V(\mathcal{I})} \lambda_i - \sum_{i \in V(\mathcal{I})} \lambda_i = - \left( \sum_{i \in V(\mathcal{I})} \lambda_i - \sum_{i \in V \setminus V(\mathcal{I})} \lambda_i \right), $$

where $\mathcal{I} = \{i \in V: |s_i| \ge 1\}$ is the set of classes of unmatched items in state $s$. Importantly, if $F(s) > 0$ (that is, $s \ne \emptyset$), then $\mathcal{I}$ is an independent set of the compatibility graph $G$ because it is non-empty and the policy $\Phi$ is greedy. It follows that, for each $s \in S \setminus \{\emptyset\}$,

$$ \mathbb{E}(F(S_{t+1}) | S_t = s) - F(s) \le -\epsilon, \quad \text{with } \epsilon = \min_{\mathcal{I} \in \mathbb{I}} \left( \sum_{i \in V(\mathcal{I})} \lambda_i - \sum_{i \in V \setminus V(\mathcal{I})} \lambda_i \right). $$

Equation (28) implies that $\epsilon > 0$. Using the Lyapunov-Foster theorem, see [8, Theorem 1.1 in Chapter 5], we conclude that the matching model $(G, \lambda, \Phi)$ is stable. ◀
24 F. P. Kelly. *Reversibility and Stochastic Networks*. Cambridge University Press, 2011.

25 László Lovász and M. D. Plummer. *Matching Theory*. American Mathematical Soc., 2009.

26 Jean Mairesse and Pascal Moyal. Stability of the stochastic matching model. *Journal of Applied Probability*, 53(4):1064–1077, 12 2016. Publisher: Cambridge University Press. doi:10.1017/jpr.2016.65.

27 Fabien Mathieu. Stochastic Matching, 2022. URL: https://balouf.github.io/stochastic_matchring/index.html.

28 Pascal Moyal, Ana Bušić, and Jean Mairesse. A product form for the general stochastic matching model. *Journal of Applied Probability*, 58(2):449–468, 06 2021. doi:10.1017/jpr.2020.100.

29 Mohammadreza Nazari and Alexander L. Stolyar. Reward maximization in general dynamic matching systems. *Queueing Systems*, 91(1):143–170, February 2019. doi:10.1007/s11134-018-9593-y.

30 J. R. Norris. *Markov Chains*. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 1997. doi:10.1017/CBO9780511810633.

31 Youssef Rahme and Pascal Moyal. A stochastic matching model on hypergraphs. *Advances in Applied Probability*, 53(4):951–980, December 2021. doi:10.1017/apr.2021.8.

32 Thirupathaiah Vasantam and Don Towsley. A throughput optimal scheduling policy for a quantum switch. In *Quantum Computing, Communication, and Simulation II*, volume 12015, pages 14–23. SPIE, 2022. doi:10.1117/12.2616950.

33 Günter M. Ziegler. *Lectures on polytopes*. Springer-Verlag, New York, 1995. URL: http://www.worldcat.org/search?qt=worldcat_org_all&q=9780387943657.

34 Martin Zubeldia, Prakirt R. Jhunjhunwala, and Siva Theja Maguluri. Matching queues with abandonments in quantum switches: Stability and throughput analysis, 2022. URL: http://arxiv.org/abs/2209.12324, arXiv:2209.12324[cs], doi:10.48550/arXiv.2209.12324.

A Minimal stability region for greedy matching policies

The following result gives a sufficient stability condition for greedy matching policies. The proof relies on a linear Lyapunov function. This result can be seen as the counterpart of [9, Proposition 5.1] for non-bipartite matching models.

► **Proposition A.1.** Consider a matching problem $(G, \lambda)$ with a connected graph $G$. If

$$ \sum_{i \in V(I)} \lambda_i > \frac{1}{2} \sum_{i \in V} \lambda_i, \quad I \in \mathbb{I}, \qquad (36) $$

then the matching model $(G, \lambda, \Phi)$ is stable for every greedy matching policy $\Phi$.

**Proof.** Consider a matching problem $(G, \lambda)$ that satisfies (36) and a greedy matching policy $\Phi$ adapted to the graph $G$. Since the Markov chain $(S_t, t \in \mathbb{N})$ associated with the matching model $(G, \lambda, \Phi)$ depends on the vector $\lambda$ only up to a positive multiplicative constant, we can assume without loss of generality that $\sum_{i \in V} \lambda_i = 1$. Let $S$ denote the state space of this Markov chain and $| \cdot |$ the corresponding queue-size function. We consider the Lyapunov function $F: S \to \mathbb{R}$ defined by $F(s) = \sum_{i \in V} |s_i|$ (that is, $F(s)$ is the number of unmatched items in state $s$) for each $s \in S$. For each $t \in \mathbb{N}$ and $s \in S$, we have

$$ \mathbb{E}(F(S_{t+1}) | S_t = s) - F(s) = \sum_{i \in V \setminus V(I)} \lambda_i - \sum_{i \in V(I)} \lambda_i = - \left( \sum_{i \in V(I)} \lambda_i - \sum_{i \in V \setminus V(I)} \lambda_i \right), $$
As one would expect, any matching problem $(G, \lambda)$ that satisfies (28) is stabilizable in the sense of Definition 1. Indeed, (28) implies Proposition 8ii because $\mathcal{I} \subseteq V \setminus V(\mathcal{I})$ for each $\mathcal{I} \in \mathcal{I}$. Corollary 27 below shows that, conversely, whether a stabilizable matching problem satisfies (28) depends on the structure of the graph $G$: conditions i and ii exhibit compatibility graphs $G$ such that (28) is satisfied whenever the matching problem $(G, \lambda)$ is stabilizable, while conditions iii and iv exhibit stabilizable compatibility graphs $G$ for which (28) is never satisfied.

**Corollary 27.** Consider a matching problem $(G, \lambda)$.

Under the following two conditions, the stabilizability of the matching model $(G, \lambda)$ implies that (28) is satisfied, and therefore that the matching model $(G, \lambda, \Phi)$ is stable under every greedy policy $\Phi$ adapted to $G$:

(i) $G$ is a complete graph with $n \ge 3$ nodes.

(ii) $G$ is the diamond graph of Example 4.

Under the following conditions, (28) is never satisfied:

(iii) The graph $G$ has diameter greater than or equal to 3.

(iv) The graph $G$ contains a leaf (that is, a node with degree 1).

**Proof.** We first need to prove that, under either condition i or condition ii, the matching model $(G, \lambda)$ is stabilizable if and only if (28) is satisfied. We proceed by verifying that, under either of these two conditions, Proposition 8ii and (28) are equivalent:

(i) First assume that condition i is satisfied. The independent sets of a complete graph $K_n$ are the singletons. Using this observation, we can verify that Proposition 8ii and (28) are both equivalent to $\lambda_i < \frac{1}{2} \sum_{i \in V} \lambda_i$ for each $i \in V$.

(ii) Now assume that condition ii is satisfied, that is, $G$ is the diamond graph. The conclusion follows by recalling that Proposition 8ii simplifies to (12), and then by observing that (12) and (28) are equivalent.

To prove that (28) cannot be satisfied under either condition iii or iv, we proceed by contradiction:

(iii) First assume that condition iii is satisfied, and let $i$ and $j$ denote two nodes that are at distance 3 or more. In particular, the sets $V_i$ and $V_j$ are disjoint. If (28) is satisfied, then applying this equation to both $\{i\}$ and $\{j\}$ and summing the inequalities yields $\sum_{i' \in V_i \cup V_j} \lambda_{i'} > \sum_{i' \in V} \lambda_{i'}$, which is a contradiction since $V_i \cup V_j \subseteq V$. Hence, (28) cannot be satisfied by both $\{i\}$ and $\{j\}$.

(iv) Now assume that condition iv is satisfied. Let $i$ denote a leaf node of $G$ and $j$ the (only) neighbor of $i$. Then again, applying (28) to both $\{i\}$ and $\{j\}$ and summing the inequalities yields $\sum_{i \in V_j \cup \{j\}} \lambda_i' > \sum_{i' \in V} \lambda_{i'}$, which is again a contradiction. $\blacksquare$

<figure><img src="image_45.png" /></figure>
where $\mathcal{I} = \{i \in V : |s_i| \ge 1\}$ is the set of classes of unmatched items in state $s$. Importantly, if $F(s) > 0$ (that is, $s \ne \emptyset$), then $\mathcal{I}$ is an independent set of the compatibility graph $G$ because it is non-empty and the policy $\Phi$ is greedy. It follows that, for each $s \in S \setminus \{\emptyset\}$,

$$ \mathbb{E}(F(S_{t+1}) | S_t = s) - F^*(s) \le -\epsilon, \quad \text{with } \epsilon = \min_{\mathcal{I} \in \mathcal{I}} \left( \sum_{i \in V(\mathcal{I})} \lambda_i - \sum_{i \in V \setminus V(\mathcal{I})} \lambda_i \right). $$

Equation (36) implies that $\epsilon > 0$. Using the Lyapunov-Foster theorem [8, Theorem 1.1 in Chapter 5], we conclude that the matching model $(G, \lambda, \Phi)$ is stable. ◀

As one would expect, any matching problem $(G, \lambda)$ that satisfies (36) is stabilizable in the sense of Definition 2.4. Indeed, (36) implies Proposition 3.7(ii) because $\mathcal{I} \subseteq V \setminus V(\mathcal{I})$ for each $\mathcal{I} \in \mathcal{I}$. Corollary A.2 below shows that, conversely, whether a stabilizable matching problem satisfies (36) depends on the structure of the graph $G$: conditions (i) and (ii) exhibit compatibility graphs $G$ such that (36) is satisfied whenever the matching problem $(G, \lambda)$ is stabilizable, while conditions (iii) and (iv) exhibit stabilizable compatibility graphs $G$ for which (36) is never satisfied.

**Corollary A.2.** Consider a matching problem $(G, \lambda)$.

Under the following two conditions, the stabilizability of the matching model $(G, \lambda)$ implies that (36) is satisfied, and therefore that the matching model $(G, \lambda, \Phi)$ is stable under every greedy policy $\Phi$ adapted to $G$:

(i) $G$ is a complete graph with $n \ge 3$ nodes.

(ii) $G$ is the diamond graph of Example 3.13.

Under the following conditions, (36) is never satisfied:

(iii) The graph $G$ has diameter greater than or equal to 3.

(iv) The graph $G$ contains a leaf (that is, a node with degree 1).

**Proof.** We first need to prove that, under either condition (i) or condition (ii), the matching model $(G, \lambda)$ is stabilizable if and only if (36) is satisfied. We proceed by verifying that, under either of these two conditions, Proposition 3.7(ii) and (36) are equivalent:

(i) First assume that condition (i) is satisfied. The independent sets of a complete graph $K_n$ are the singletons. Using this observation, we can verify that Proposition 3.7(ii) and (36) are both equivalent to $\lambda_i < \frac{1}{2} \sum_{i' \in V} \lambda_{i'}$ for each $i \in V$.

(ii) Now assume that condition (ii) is satisfied, that is, $G$ is the diamond graph. The conclusion follows by recalling that Proposition 3.7(ii) simplifies to (13), and then by observing that (13) and (36) are equivalent.

To prove that (36) cannot be satisfied under either condition (iii) or (iv), we proceed by contradiction:

(iii) First assume that condition (iii) is satisfied, and let $i$ and $j$ denote two nodes that are at distance 3 or more. In particular, the sets $V_i$ and $V_j$ are disjoint. If (36) is satisfied, then applying this equation to both $\{i\}$ and $\{j\}$ and summing the inequalities yields $\sum_{i' \in V_i \cup V_j} \lambda_{i'} > \sum_{i' \in V} \lambda_{i'}$, which is a contradiction since $V_i \cup V_j \subseteq V$. Hence, (36) cannot be satisfied by both $\{i\}$ and $\{j\}$.

(iv) Now assume that condition (iv) is satisfied. Let $i$ denote a leaf node of $G$ and $j$ the (only) neighbor of $i$. Then again, applying (36) to both $\{i\}$ and $\{j\}$ and summing the inequalities yields $\sum_{i \in V_j \cup \{j\}} \lambda_{i'} > \sum_{i' \in V} \lambda_{i'}$, which is again a contradiction.

◀
**C Supplementary material of Section 5 (Polytope of solutions in surjective-only graphs).**

**C.1 Algorithm of Section 5.1.3 (Basis of the kernel of the incidence matrix).**

Given a surjective-only graph $G$ with an incidence matrix denoted by $A$, Algorithm 1 builds a basis of the kernel of $A$ as follows. The algorithm first identifies a spanning tree $\mathcal{T}$ of $G$ (Line 1) and an edge $a \in E \setminus \mathcal{T}$ such that the set $E \setminus (\mathcal{T} \cup \{a\})$ (of cardinality $d = m = n$) contains an odd cycle (Line 2). Then, for each edge $s \in E \setminus (\mathcal{T} \cup \{a\})$, the algorithm builds (Lines 5–26) a base vector $b$ whose support (i) is either an even cycle or a kayak paddle and (ii) contains $s$ and is included into $\mathcal{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.

We now verify that Algorithm 1 terminates and yields the desired result.

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

**Proof.** The proof is based mainly on the notion of *cycle space* in a graph. We briefly summarize the concepts that are useful to understand the proof (see [20, Section 1.9] for details).

A *spanning subgraph* of a graph $G = (V, E)$ is a subgraph $G^\circ = (V, E^\circ)$ with $E^\circ \subseteq E$. Importantly, $G$ and $G^\circ$ have the same set of nodes. A subgraph is *Eulerian* if every vertex has an even degree (possibly zero). In particular, if $E^\circ$ is a set of edges that form a cycle in $G$, then the graph $(V, E^\circ)$ is Eulerian. The *cycle space* of $G$ is the vector space made of all Eulerian spanning subgraphs of $G$, using the symmetric difference of the edge sets for addition and the two-element field for scalar multiplication. Equivalently, the cycle space can be described as a vector space of the finite field $\mathbb{Z}/2\mathbb{Z}$: each vector $g = (g_1, g_2, \dots, g_m)$ in this vector space satisfies $\sum_{k \in E_i} g_k = 0$ (modulo 2) for each $i \in V$, and the addition and multiplication are the usual operations in $\mathbb{Z}/2\mathbb{Z}$. For example, if $G$ is the codomino graph of Figure 17, the spanning subgraphs $G_1, G_2$, and $G_3$ of $G$ with edge sets $E_1 = \{{\{1, 2\}, \{1, 6\}, \{2, 3\}, \{3, 4\}, \{4, 5\}, \{5, 6\}\}, E_2 = \{{\{2, 3\}, \{2, 6\}, \{3, 5\}, \{5, 6\}\}, \text{ and } E_3 = \{{\{1, 2\}, \{1, 6\}, \{2, 6\}\}, \text{ respectively, belong to the cycle space of } G. The edge set of the addition } G_1+G_2 \text{ is the set } \{{\{1, 2\}, \{1, 6\}, \{2, 6\}, \{3, 4\}, \{3, 5\}, \{4, 5\}\} \text{ of edges that are either in } E_1 \text{ or in } E_2, \text{ but not in both. Similarly, the edge set of } G_1+G_3 \text{ is } \{{\{2, 3\}, \{2, 6\}, \{3, 4\}, \{4, 5\}, \{5, 6\}\}, \text{ and the edge set of } G_2+G_3 \text{ is } \{{\{1, 2\}, \{1, 6\}, \{2, 3\}, \{3, 5\}, \{5, 6\}\}. One can verify that } \{G_1, G_2, G_3\} \text{ forms a basis of the cycle space of } G. Importantly, in general, the dimension of the cycle space is } m-n+1$.

**Algorithm 1 terminates.** We first prove the existence of edge $a$ defined on Line 2 of Algorithm 1. By definition of a spanning tree, $\mathcal{T}$ contains $n-1$ edges and, for each edge $a \in E \setminus \mathcal{T}$, $\mathcal{T} \cup \{a\}$ contains a unique cycle. The $m-n+1 = |E \setminus \mathcal{T}|$ cycles thus obtained are independent in the sense that each cycle contains at least one edge ($a$) that is not contained in the other cycles. Therefore, these $m-n+1$ cycles form a basis of the cycle space of $G$. Since a linear combination of even cycles cannot produce a subgraph consisting of a single odd cycle$^{20}$, and since $G$ contains an odd cycle (as it is non-bipartite), then at least one of the $m-n+1$ basis cycles is odd.

<footnote>$^{20}$ A linear combination of even cycles may produce a subgraph consisting of an even number of disjoint</footnote>
**B Proof of Proposition 5.3**

The proof is based mainly on the notion of *cycle space* in a graph. We briefly summarize the concepts that are useful to understand the proof (see [19, Section 1.9] for details).

A *spanning subgraph* of a graph $G = (V, E)$ is a subgraph $G' = (V, E')$ with $E' \subseteq E$. Importantly, $G$ and $G'$ have the same set of nodes. A subgraph is *Eulerian* if every vertex has an even degree (possibly zero). In particular, if $E'$ is a set of edges that form a cycle in $G$, then the graph $(V, E')$ is Eulerian. The *cycle space* of $G$ is the vector space made of all Eulerian spanning subgraphs of $G$, using the symmetric difference of the edge sets for addition and the two-element field for scalar multiplication. Equivalently, the cycle space can be described as a vector space of the finite field $Z/2Z$: each vector $g = (g_1, g_2, \dots, g_m)$ in this vector space satisfies $\sum_{k \in E_i} g_k = 0$ (modulo 2) for each $i \in V$, and the addition and multiplication are the usual operations in $Z/2Z$. For example, if $G$ is the codomino graph of Figure 13, the spanning subgraphs $G_1, G_2$, and $G_3$ of $G$ with edge sets $E_1 = \{\{1, 2\}, \{1, 6\}, \{2, 3\}, \{3, 4\}, \{4, 5\}, \{5, 6\}\}, E_2 = \{\{2, 3\}, \{2, 6\}, \{3, 5\}, \{5, 6\}\}$, and $E_3 = \{\{1, 2\}, \{1, 6\}, \{2, 6\}\}$, respectively, belong to the cycle space of $G$. The edge set of the addition $G_1+G_2$ is the set $\{\{1, 2\}, \{1, 6\}, \{2, 6\}, \{3, 4\}, \{3, 5\}, \{4, 5\}\}$ of edges that are either in $E_1$ or in $E_2$, but not in both. Similarly, the edge set of $G_1+G_3$ is $\{\{2, 3\}, \{2, 6\}, \{3, 4\}, \{4, 5\}, \{5, 6\}\}$, and the edge set of $G_2+G_3$ is $\{\{1, 2\}, \{1, 6\}, \{2, 3\}, \{3, 5\}, \{5, 6\}\}$. One can verify that $\{G_1, G_2, G_3\}$ forms a basis of the cycle space of $G$. Importantly, in general, the dimension of the cycle space is $m-n+1$.

**Proof that Algorithm 1 terminates.** We first prove the existence of edge $a$ defined on line 3 of Algorithm 1. By definition of a spanning tree, $\mathcal{T}$ contains $n-1$ edges and, for each edge $a \in E \setminus \mathcal{T}$, $\mathcal{T} \cup \{a\}$ contains a unique cycle. The $m-n+1 = |E \setminus \mathcal{T}|$ cycles thus obtained are independent in the sense that each cycle contains at least one edge ($a$) that is not contained in the other cycles. Therefore, these $m-n+1$ cycles form a basis of the cycle space of $G$. Since a linear combination of even cycles cannot produce a subgraph consisting of a single odd cycle<fnref n="10" />, and since $G$ contains an odd cycle (as it is non-bipartite), then at least one of the $m-n+1$ basis cycles is odd.

We now verify that, for each $s \in E \setminus (\mathcal{T} \cup \{a\})$, $\mathcal{T} \cup \{a, s\}$ contains either (i) an even cycle $C_\ell$ or (ii) a kayak paddle $KP_{\ell,r,p}$ with two odd cycles. By construction, $\mathcal{T} \cup \{a\}$ contains a unique cycle $C_r$, which is odd, and $\mathcal{T} \cup \{s\}$ contains a unique cycle $C_\ell$. $\mathcal{T} \cup \{a, s\}$ contains both $C_r$ and $C_\ell$. We now proceed by elimination:

- If $C_\ell$ is even, then $C_\ell$ is an even cycle included into $\mathcal{T} \cup \{a, s\}$, and we are in case (i).

- If $C_\ell$ is odd and shares at least one edge with $C_r$, then the symmetric difference of $C_r$ and $C_\ell$ is an even cycle, and it is again included into $\mathcal{T} \cup \{a, s\}$, so we are again in case (i).

- If $C_\ell$ is odd and $C_r$ and $C_\ell$ have no edge in common, then we are in case (ii). ◀

**Proof that Algorithm 1 returns the correct result.** We finally prove that the family $\mathcal{B}$ returned by Algorithm 1: (i) has cardinality $m-n$, (ii) is linearly independent, and (iii) is included into the kernel of $A$. We prove each item one after another:

(i) The family $\mathcal{B}$ has cardinality $m-n$: It suffices to observe that $\mathcal{B}$ has same cardinality as $E \setminus (\mathcal{T} \cup \{a\})$, which we already mentioned has cardinality $m-n$.

<footnote n="10">¹⁰ A linear combination of even cycles may produce a subgraph consisting of an even number of disjoint odd cycles, as illustrated by $G_1 + G_2$ in the example above, but not a subgraph consisting of one odd cycle. Indeed, the symmetric difference of two edge sets contains an even number of edges if both edge sets contain an even number of edges.</footnote>
**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}$ ← the set of 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. $b \leftarrow (0, 0, \dots, 0) \in \mathbb{R}^m$

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

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

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

9. $k \leftarrow$ index of $c_d$ in $E$

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

11. **else**

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

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

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

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

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

17. $k \leftarrow$ index of $c_d$ in $E$

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

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

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

21. $k \leftarrow$ index of $c_d$ in $E$

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

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

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

25. $k \leftarrow$ index of $c_d$ in $E$

26. $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 by [21, 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).

We now verify that, for each $s \in E \setminus (\mathcal{T} \cup \{a\})$, $\mathcal{T} \cup \{a, s\}$ contains either (i) an even cycle $C_\ell$ or (ii) a kayak paddle $KP_{\ell,r,p}$ with two odd cycles. By construction, $\mathcal{T} \cup \{a\}$ contains a unique cycle $C_r$, which is odd, and $\mathcal{T} \cup \{s\}$ contains a unique cycle $C_\ell$. $\mathcal{T} \cup \{a, s\}$ contains both $C_r$ and $C_\ell$. We now proceed by elimination:

■ If $C_\ell$ is even, then $C_\ell$ is an even cycle included into $\mathcal{T} \cup \{a, s\}$, and we are in case (i).

■ If $C_\ell$ is odd and shares at least one edge with $C_r$, then the symmetric difference of $C_r$ and $C_\ell$ is an even cycle, and it is again included into $\mathcal{T} \cup \{a, s\}$, so we are again in case (i).

■ If $C_\ell$ is odd and $C_r$ and $C_\ell$ have no edge in common, then we are in case (ii).

<footnote>odd cycles, as illustrated by $G_1 + G_2$ in the example above, but not a subgraph consisting of one odd cycle. Indeed, the symmetric difference of two edge sets contains an even number of edges if both edge sets contain an even number of edges.</footnote>
(ii) The family $\mathcal{B}$ is linearly independent: For each $s \in E \setminus (T \cup \{a\})$, the basis vector constructed from edge $s$ is the only vector in $\mathcal{B}$ whose support contains this edge.

(iii) The family $\mathcal{B}$ is included into the kernel of $A$: Let $b \in \mathcal{B}$. Our goal is to prove that $b$ belongs to the kernel of $A$, i.e., that $\sum_{k \in E_i} b_k = 0$ for each $i \in V$. First observe that, for each $i \in V$, we have $\sum_{k \in E_i} b_k = \sum_{k \in E_i \cap S} b_k$, where $S$ is the support of the vector $b$. In particular, we have immediately $\sum_{k \in E_i} b_k = 0$ for each $i \in V$ such that $E_i \cap S = \emptyset$. Now consider a node $i \in V$ such that $E_i \cap S \neq \emptyset$. We make a case disjunction depending on the support $S$ of $b$:

- If $S$ is an even cycle $C_\ell$, then $E_i \cap S = \{k_1, k_2\}$, where $k_1$ and $k_2$ are two consecutive edges of the cycle $C_\ell$. Line 10 in the algorithm implies that $b_{k_1} = -b_{k_2} \in \{1, -1\}$. It follows that $\sum_{k \in E_i} b_k = b_{k_1} + b_{k_2} = 0$.

- If $S$ is a kayak paddle $KP_{\ell,r,p}$ with odd cycles $C_\ell$ and $C_r$ and central path $P_p$, $p \in \mathbb{N}$, we again distinguish several cases:

**Node i does not belong to the central path:** If $E_i \cap S \subseteq C_\ell$ or $E_i \cap S \subseteq C_r$, we conclude as before.

**Node i does not belong to a cycle:** If $E_i \cap S \subseteq P_p$, then $E_i \cap S = \{k_1, k_2\}$ where $k_1$ and $k_2$ are two consecutive edges of the path $P_p$. Line 22 of the algorithm implies that $b_{k_1} = -b_{k_2} \in \{2, -2\}$. It follows that $\sum_{k \in E_i} b_k = b_{k_1} + b_{k_2} = 0$.

**Node i belongs to a cycle and the central path:** The only remaining case is when $E_i \cap S$ intersects several sets among $C_\ell$, $C_r$, and $P_p$. If $p=0$, that is, if the central path is the node $i$, then $E_i \cap S = \{k_1, k_2, k_3, k_4\}$, where $k_1$ and $k_2$ (resp. $k_3$ and $k_4$) are two consecutive edges in $C_\ell$ (resp. $C_r$). Lines 18 and 26 yield $b_{k_1} = b_{k_2} = -1$ and $b_{k_3} = b_{k_4} = 1$, which implies that $\sum_{k \in E_i} b_k = b_{k_1} + b_{k_2} + b_{k_3} + b_{k_4} = 0$. If $p \ge 1$, then $E_i \cap S = \{k_1, k_2, k_3\}$, where $k_1$ and $k_2$ are two consecutive edges of either $C_\ell$ or $C_r$, and $k_3$ is an edge in $P_p$. Lines 18, 22, and 26 of the algorithm imply that $b_{k_1} = b_{k_2} \in \{1, -1\}$ and that $b_{k_3} = -2b_{k_1}$, so that we conclude again that the desired sum is zero. ◀

# C Proofs of the results of Section 6.1

## C.1 Proof of Proposition 6.1

Consider a stabilizable matching problem $(G, \lambda)$ and let $\Pi_P$ (resp. $\Pi_G$) denote the set of vectors of matching rates achievable by stable policies (resp. by stable greedy policies) adapted to the compatibility graph $G$.

### Convexity of $\Pi_P$

Consider two (extended) policies $\Phi_1$ and $\Phi_2$ that stabilize the matching problem $(G, \lambda)$. The state-space, queue-size function, and empty state of $\Phi_1$ (resp. $\Phi_2$) are denoted by $S_1, |\cdot|_1$, and $\emptyset_1$ (resp. $S_2, |\cdot|_2$, and $\emptyset_2$). Given $0 < \beta < 1$, our goal is to build a matching policy $\Phi_\beta$ that also stabilizes the matching problem $(G, \lambda)$ and satisfies $\mu(\Phi_\beta) = \beta\mu(\Phi_1) + (1-\beta)\mu(\Phi_2)$.

Intuitively, the policy $\Phi_\beta$ will consistently follow the decisions of either $\Phi_1$ or $\Phi_2$ as long as the system is non-empty, and switch between these two policies each time the system becomes empty (therefore, at renewal times). The probability of choosing either policy after visiting the empty state will be chosen to achieve the desired matching rate vector on the long run. More formally, the policy $\Phi_\beta$ will have the following characteristics:

- State space $S_\beta = (S_1 \times \{\emptyset_2\}) \cup (\{\emptyset_1\} \times S_2)$.

- Queue-size function $|\cdot|_\beta$ defined by $|(s_1, s_2)|_\beta = |s_1|_1 + |s_2|_2$ for each $(s_1, s_2) \in S_\beta$.