**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 (T \cup \{a\})$, which we already mentioned has cardinality $m-n$.

(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 \supseteq 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 hat $b_{k_3} = -2b_{k_1}$, so that we conclude again that the desired sum is zero.

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

Figures 16 and 17 shows possible runs of Algorithm 1 on the tri diamond and codomino graphs, which both have a two-dimensional kernel. Note that the basis is not unique and depends on our choice of the spanning tree $T$ and the augmenting edge $a$ (see Lines 1 and 2 in Algorithm 1).

## C.2 Proof of Proposition 13 in Section 5.2.1 (Vertex characterization) (borrowed from [15]).

We prove that the negations of $i$ and $ii$ are equivalent. Let $A^*$ denote the incidence matrix of $G^*$.

By Definition 12, 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 $E^*$ of the vector $\mu$. In particular, if $\tilde{\mu}$ and $\tilde{z}_1$ denote the restrictions of $\mu$ and $z_1$ to coordinates in $E^*$, respectively,
Empty state: $\emptyset_{\beta} = (\emptyset_1, \emptyset_2)$.

For some $0 < \gamma_{\beta} < 1$ that will be specified later, the matching policy $\Phi_{\beta}$ is defined as follows:

$$ \Phi_{\beta}((\emptyset_1, \emptyset_2), i, j, (s_1, \emptyset_2)) = \gamma_{\beta}\Phi_1(\emptyset_1, i, j, s_1), \quad s_1 \in S_1, \quad i \in V, \quad j \in V \cup \{\perp\}, $$

$$ \Phi_{\beta}((\emptyset_1, \emptyset_2), i, j, (\emptyset_1, s_2)) = (1 - \gamma_{\beta})\Phi_2(\emptyset_2, i, j, s_2), \quad s_2 \in S_2, \quad i \in V, \quad j \in V \cup \{\perp\}, $$

$$ \Phi_{\beta}((s_1, \emptyset_2), i, j, (s'_1, \emptyset_2)) = \Phi_1(s_1, i, j, s'_1), \quad s_1 \in S_1 \setminus \{\emptyset_1\}, \quad s'_1 \in S_1, $$

$$ \Phi_{\beta}((\emptyset_1, s_2), i, j, (\emptyset_1, s'_2)) = \Phi_2(s_2, i, j, s'_2), \quad s_2 \in S_2 \setminus \{\emptyset_2\}, \quad s'_2 \in S_2. $$

The first two equations say that, when the system is empty, we next apply $\Phi_1$ with probability $\gamma_{\beta}$ and $\Phi_2$ with probability $1 - \gamma_{\beta}$. The third (resp. fourth) equation says that, once we start applying policy $\Phi_1$ (resp. $\Phi_2$), we keep applying this policy until we re-visit the empty state.

The stability of the policies $\Phi_1$ and $\Phi_2$ implies that of the policy $\Phi_{\beta}$. According to the elementary renewal theorem for renewal reward processes, the vector giving the long-run average matching rates under the policy $\Phi_{\beta}$ is given by

$$ \mu(\Phi_{\beta}) = \frac{\gamma_{\beta}T_1\mu(\Phi_1) + (1 - \gamma_{\beta})T_2\mu(\Phi_2)}{\gamma_{\beta}T_1 + (1 - \gamma_{\beta})T_2}, \\ = \frac{\gamma_{\beta}T_1}{\gamma_{\beta}T_1 + (1 - \gamma_{\beta})T_2}\mu(\Phi_1) + \frac{(1 - \gamma_{\beta})T_2}{\gamma_{\beta}T_1 + (1 - \gamma_{\beta})T_2}\mu(\Phi_2). $$

where $T_1$ (resp. $T_2$) denotes the mean number of matches between two successive visits to the empty state $\emptyset_1$ (resp. $\emptyset_2$) in the matching model $(G, \lambda, \Phi_1)$ (resp. $(G, \lambda, \Phi_2)$). We let the reader verify that the following value of $\gamma_{\beta}$ yields $\mu(\Phi_{\beta}) = \beta\mu(\Phi_1) + (1 - \beta)\mu(\Phi_2)$:

$$ \gamma_{\beta} = \frac{\beta T_2}{(1 - \beta)T_1 + \beta T_2}. $$

### Convexity of $\Pi_G$

It suffices to observe that, if the policies $\Phi_1$ and $\Phi_2$ are greedy, so is the policy $\Phi_{\beta}$.

## C.2 Proof of the results of Section 6.1.1 for the complete graph

### Proposition 6.4(i)

Consider a (possibly random) size-based greedy policy $\Phi: Q_G(K_n) \times V \times (V \cup \{\perp\}) \to [0, 1]$, as defined in Remark 2.1, where $Q_G(K_n)$ is given in (25). Given $(q, i) \in Q_G(K_n) \times V$, the definition of $Q_G(K_n)$ implies that $\{j \in V_i : |q_j| \ge 1\}$ is either a singleton or the emptyset. In the former case, letting $j$ denote the unique element of the singleton, we have $\Phi(q, i, \perp) = 1$ if $i = j$, while the greediness of $\Phi$ implies that $\Phi(q, i, j) = 1$ if $i \ne j$. In the latter case, we have directly $\Phi(q, i, \perp) = 1$. In all cases, the matching decision is deterministic and makes the same decisions as in (26).

### Proposition 6.4(ii)

The same argument can be repeated for an arbitrary greedy policy $\Phi$ with state space $(S, |\cdot|)$. Given $(s, i) \in S \times V$, we know that $|s| \in Q_G(K_n)$, so that $\{j \in V_i : |s_j| \ge 1\}$ is either a singleton or the emptyset. In the former case, letting $j$ denote the unique element of the singleton, we have $\sum_{s' \in S} \Phi(s, i, \perp, s') = 1$ if $i = j$, while the greediness of $\Phi$ implies that $\sum_{s' \in S} \Phi(s, i, j, s') = 1$ if $i \ne j$. In the latter case, we have directly $\sum_{s' \in S} \Phi(s, i, \perp, s') = 1$. In all cases, we have $\sum_{s' \in S} \Phi(s, i, \Phi_G(|s|, i), s') = 1$.
<figure><img src="image_47.png" /></figure>

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

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

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

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

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

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

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

then $A^*\tilde{\mu} = A\mu = \lambda = Az_1 = A^*\tilde{z}_1$ with $\tilde{\mu} \neq \tilde{z}_1$, which means that $G^* = (V, E^*)$ is not injective.

Conversely, if $G^*$ is not injective, there exists a non-zero vector $\tilde{z}$ in $\mathbb{R}^{|E^*|}$ such that $A^*\tilde{z} = 0$. If we embed $\tilde{z}$ into $\mathbb{R}^{|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}$.

The last part directly derives from Statements ii and v in Proposition 6.

### C.3 Additional examples and results for Section 5.2.1 (Vertex characterization).

Following Proposition 13, 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 29 below. For example, by looking more closely at the general solution obtained for the diamond graph in Figure 3d, 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}$.
**Proposition 6.4(iii)**

This statement follows directly from Proposition 6.4(ii) and from the fact that, under any matching policy, the dynamics of the queue-size process is fully specified by the sequence of incoming item classes and the matching decisions via (2).

**Proposition 6.5(i)**

Proposition 6.5(i) is a consequence of Corollary A.2(i).

**Proposition 6.5(ii)**

We can focus without loss of generality on the first-come-first-matched policy, as Proposition 6.4(iii) implies that all greedy matching policies yield the same vector of matching rates. Equation (27) follows by observing that, for each edge $e_k = \{i, j\} \in E$, a match between classes $i$ and $j$ happens in one of the following two cases:

- a class-$i$ item arrives while queue $j$ is non-empty, which happens at rate $\lambda_i p_j$;

- a class-$j$ item arrives while queue $i$ is non-empty, which happens at rate $\lambda_j p_i$.

Equations (28) and (29) follow from [15, Proposition 5]. Indeed, for each $i \in V$, applying [15, Equation (10)] to the independent set $\{i\}$ yields (28), and the value of $p_\emptyset$ given in (29) follows from the normalizing equation. This result may also be obtained more directly by observing that, for each $i \in V$, the restriction of the transition diagram of the Markov chain $(K_n, \lambda, \Phi_G)$ to the states where all queues but queue $i$ are empty is similar to a (discrete-time) birth-and-death process with birth probability $\lambda_i$ and death probability $\sum_{j \neq i} \lambda_j$.

## C.3 Proof of the results of Section 6.1.2 for the diamond graph

**Proposition 6.6(i)**

We leave it to the reader to verify that $Q_G(K_3)$ is the image of $Q_G(D)$ by the application $q = (q_1, q_2, q_3, q_4) \mapsto \langle q \rangle = (q_1 + q_4, q_2, q_3)$. This means in particular that $q_1 + q_4, q_2$, and $q_3$ cannot be positive simultaneously if $q \in Q_G(D)$. Since the diamond graph $D$ has only four nodes, we can then conclude by enumerating all relevant cases, depending on the support of $\langle q \rangle = (q_1 + q_4, q_2, q_3)$. For example, if $q_1 + q_4 \ge 1$ and $q_2 = q_3 = 0$, then we have immediately $\Phi(q, i) = \perp$ if $i \in \{1, 4\}$, and the greediness of the policy $\Phi$ implies that $\Phi(q, i) \in \{1, 4\}$ if $i \in \{2, 3\}$; in other words, we have $\langle \Phi(q, i) \rangle = \perp$ if $\langle i \rangle = 1$ and $\langle \Phi(q, i) \rangle = 1$ if $\langle i \rangle \in \{2, 3\}$. Similarly, if $q_1 + q_4 = q_3 = 0$ and $q_2 \ge 1$, then $\Phi(q, i) = \perp$ if $i = 2$ and $\Phi(q, i) = 2$ if $i \in \{1, 3, 4\}$, that is, $\langle \Phi(q, i) \rangle = \perp$ if $\langle i \rangle = 2$ and $\langle \Phi(q, i) \rangle = 2$ if $\langle i \rangle \in \{1, 3\}$. In all cases, we can verify that $\langle \Phi(q, i) \rangle$ is equal to $\Phi_G(K_3)(\langle q \rangle, \langle i \rangle)$.

Alternatively, by taking a step back, we can prove Proposition 6.6(i) more directly by observing that, for each $(q, i) \in Q_G(D) \times V$, (i) the support of $\langle q \rangle$ is a singleton $\{j\}$ whenever $q \neq 0$, and (ii) whether or not $j \in V_i$ depends on $i$ only via $\langle i \rangle$.

**Proposition 6.6(ii)**

The same argument can be repeated for an arbitrary greedy policy $\Phi$ with state space $(S, |\cdot|)$. As in the proof of Proposition 6.4(ii), the key argument consists of observing that we still have $q = |s| \in Q_G(D)$ for each $(s, i) \in S \times V$, so that $q_1 + q_4, q_2$, and $q_3$ cannot be positive simultaneously.
<figure><img src="image_54.png" /><figcaption>(a) Construction A.</figcaption></figure>

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

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

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

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

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

■ **Figure 17** 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)$.

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

■ **Figure 3d (repeated)** Matching rates in the diamond graph with the normalization $\lambda_1 + \lambda_4 = \frac{1}{2}$. $2\beta = \lambda_2 + \lambda_3 - \frac{1}{2}$ is the difference between the arrival rates of $\{2, 3\}$ and $\{1, 4\}$. $\bar{\lambda}_2 = \lambda_2 - \beta$ and $\bar{\lambda}_3 = \lambda_3 - \beta$ represent the residual rates that classes 2 and 3 can provide to classes 1 and 4.

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

► **Definition 29** (Adapted from [4, 42]). 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_\ell \ge 0 \text{ for each } \ell \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 17) is the number of inequalities that are not tight for this vertex. More generally, Definition 29 has the following intuitive interpretation. An inequality is tight if the convex polytope $\Pi_{\ge 0}$
**Proposition 6.6(iii)**

The conclusion follows in much the same way as in the proof of Proposition 6.4(iii), by injecting statements (i) and (ii) from Proposition 6.6 into (2).

**Proposition 6.7(i)**

This is a consequence of Corollary A.2(ii).

**Proposition 6.7(ii)**

The equation $\mu_{2,3} = \beta = \frac{1}{2}(\lambda_2 + \lambda_3 - \lambda_1 - \lambda_4)$ is a direct consequence of (CE). The inequalities (32) for $\mu_{1,2}$, $\mu_{1,3}$, $\mu_{2,4}$, and $\mu_{3,4}$ follow by observing that, for each edge $\{i, j\} \in \{\{1, 2\}, \{1, 4\}, \{2, 3\}, \{3, 4\}\}$, a match between classes i and j happens at least in one of the following cases:

- a class-i item arrives while the system contains unmatched items that all belong to class j,

- a class-j item arrives while the system contains unmatched items that all belong to class i, These events occur at rates $\lambda_i p_j$ and $\lambda_j p_i$, respectively. Equations (32) are not equalities in general because the above list is not exhaustive. For example, depending on the greedy policy, a match between classes 1 and 2 may happen if a class-2 item arrives while the system contains unmatched items of class 1 and unmatched items of class 4.

**Proposition 6.7(iii)**

The expressions for $p_\emptyset$, $p_2$, $p_3$, and $p_{1,4}$ follow directly by combining Proposition 6.6(iii) with Equations (28) and (29) in Proposition 6.5. We now derive the lower bound (34) for $p_1$. The one for $p_4$ follows by symmetry.

First assume that the greedy policy $\Phi$ is deterministic and size-based, so that it satisfies Proposition 6.6(i). For each $q \in Q_G(D)$, let $\pi_q$ denote the probability that the Markov chain $(D, \lambda, \Phi)$ is in state $q$ in stationary regime. The probability that we want to lower-bound is

$$p_1 = \sum_{\ell=1}^{+\infty} \pi_{\ell 1_1}. \qquad (37)$$

Now let $\ell \in \mathbb{N}_{>0}$ and consider the balance equation for state $\ell 1_1$, given by

$$(\lambda_1 + \lambda_2 + \lambda_3 + \lambda_4)\pi_{\ell 1_1} = \lambda_1\pi_{(\ell-1)1_1} + (\lambda_2 + \lambda_3)\pi_{(\ell+1)1_1} + C, \qquad (38)$$

where $C$ is a non-negative real that depends on the model parameters, the integer $\ell$, and the policy $\Phi$, and that accouts for the flow to state $\ell 1_1$ from state $\ell 1_1 + 1_4$, if any. It follows that $(\lambda_1 + \lambda_2 + \lambda_3 + \lambda_4)\pi_{\ell 1_1} > \lambda_1\pi_{(\ell-1)1_1}$. An inductive argument allows us to conclude that

$$\pi_{\ell 1_1} > \left( \frac{\lambda_1}{\lambda_1 + \lambda_2 + \lambda_3 + \lambda_4} \right)^{\ell} p_{\emptyset}, \quad \ell \in \mathbb{N}_{>0}. \qquad (39)$$

Injecting this inequality into (37) allows us to conclude:

$$p_1 > \sum_{\ell=1}^{+\infty} \left( \frac{\lambda_1}{\lambda_1 + \lambda_2 + \lambda_3 + \lambda_4} \right)^{\ell} p_{\emptyset} = \frac{\lambda_1}{\lambda_2 + \lambda_3 + \lambda_4} p_{\emptyset}. \qquad (40)$$

If $\Phi$ is an extended policy with state space $(S, |\cdot|)$, we can still write (37)–(40) and reach the same conclusion. The only difference is that $\pi$ can no longer be defined as the stationary distribution of a Markov chain: instead, we define $\pi_q = \sum_{s \in S: |s| = q} \pi_s$ for each $q \in Q_G(D)$, where $\pi_s$ is the probability that the Markov chain $(D, \lambda, \Phi)$ is in state $s$ in stationary regime, for each $s \in S$.
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 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 30, 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 8–10 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 the discussion above on Figure 3d, these examples use a kernel basis to verify effortlessly whether an inequality is tight and/or irredundant.

**► Example 8 (Essential matching problem).** Figure 18 considers a codomino graph with the vector of arrival rates $\lambda = (4, 5, 3, 2, 3, 5)$. A particular solution to (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 17. The generic solution to (CE) is shown in Figure 18b.

The inequalities are listed in Figure 18a. The 2-dimensional polytope $\Pi_{\ge 0}$, shown in Figure 18c 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 18c 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 18d–18h.

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

The inequalities are listed in Figure 19a. The 2-dimensional convex polytope $\Pi_{\ge 0}$ is shown in kernel basis in Figure 19c. 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, 0, 2, 0)$ in edge basis (Figure 19f). This vertex has 5 zero coordinates in edge coordinates (and only 3 positive coordinates) even if it belongs to only 2 facets.

**► Example 10 (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 20a. 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
**Proposition 6.8(i)-(iia)-(iib)**

The diamond graph $D$ has $n = 4$ nodes and $m = 5$ edges. Therefore, according to Propositions 5.1 and 6.1, the sets $\Pi_{\ge 0}$, $\Pi_{> 0}$, and $\Pi_G$ have dimension $d = m - n = 1$, meaning that they are intervals in $\mathbb{R}$. The equations for the intervals $\Pi_{\ge 0}$ and $\Pi_{> 0}$ follow directly from the change-of-basis equation $\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)$ from (30). That $\Pi_G$ is also an interval is a consequence of Proposition 6.1. The (non-strict) inequality $-2\min(\lambda_1\bar{\lambda}_2, \bar{\lambda}_3\lambda_4) \le \alpha_+ \le \alpha_- \le 2\min(\lambda_1\bar{\lambda}_3, \bar{\lambda}_2\lambda_4)$ is a consequence of Proposition 6.2, which states that $\Pi_G \subseteq \Pi_{> 0}$. The first and third inequalities are also strict because $\alpha_+$ and $\alpha_-$ belong to $\Pi_G$ (see below), while $2\min(\lambda_1\bar{\lambda}_3, \bar{\lambda}_2\lambda_4)$ and $-2\min(\lambda_1\bar{\lambda}_2, \bar{\lambda}_3\lambda_4)$ do not belong to $\Pi_{> 0}$. That $\Pi_G$ is a closed interval of the form $\Pi_G = [\alpha_-, \alpha_+]$ and that $\alpha_+$ and $\alpha_-$ are as given in Proposition 6.8(iia) –(iib) are consequences of Lemma C.1 below, which will be proved by a coupling argument later in this appendix.

**► Lemma C.1.** Consider the edge-priority policy $\Phi_+$ adapted to the diamond graph $D$ whereby edges $\{1, 2\}$ and $\{3, 4\}$ have the highest priority. For each greedy policy $\Phi$ adapted to the compatibility graph $D$, we have

$$ \mu_{1,2}(\Phi) \le \mu_{1,2}(\Phi_+), \quad \mu_{3,4}(\Phi) \le \mu_{3,4}(\Phi_+), \\ \mu_{1,3}(\Phi) \ge \mu_{1,3}(\Phi_+), \quad \mu_{2,4}(\Phi) \ge \mu_{2,4}(\Phi_+), \tag{41} $$

Equivalently, in kernel coordinates, we have $\alpha(\Phi) \le \alpha(\Phi_+)$.

**Proof.** See later in this appendix.

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

**Proposition 6.8(iic)**

Most of the quantities we consider in this proof are functions of $\beta$, but this dependency is left implicit to simplify notation. In particular, we let $\mu$ denote (the edge coordinates of) the matching rate vector in the matching model $(D, \lambda, \Phi_+)$, where $\lambda = (\lambda_1, \bar{\lambda}_2 + \beta, \bar{\lambda}_3 + \beta, \lambda_4)$, with $\lambda_1 + \lambda_4 = \bar{\lambda}_2 + \bar{\lambda}_3 = \frac{1}{2}$, and $\Phi_+$ is the greedy edge-priority policy defined in Lemma C.1. By combining (32) with the conservation equation $\mu_{1,2} + \mu_{1,3} = \lambda_1$, we obtain the following lower and upper bounds for $\mu_{1,2}$:

$$ \lambda_1 p_2 + \lambda_2 p_1 \le \mu_{1,2} \le \lambda_1 - (\lambda_1 p_3 + \lambda_3 p_1). \tag{42} $$

In addition, injecting the definition (30) of $\lambda$ into (33) and (34) shows that, in the model $(D, \lambda, \Phi_+)$, we have

$$ \begin{array}{lll} p_2 = p_{\varnothing} \frac{\bar{\lambda}_2 + \beta}{2\bar{\lambda}_3}, & p_3 = p_{\varnothing} \frac{\bar{\lambda}_3 + \beta}{2\bar{\lambda}_2}, & p_{1,4} = p_{\varnothing} \frac{1}{3\beta}, \\ p_1 > p_{\varnothing} \frac{\lambda_1}{\frac{1}{2} + \lambda_4 + 2\beta}, & p_4 > p_{\varnothing} \frac{\lambda_4}{\frac{1}{2} + \lambda_1 + 2\beta}, & \end{array} \tag{43} $$

with, by the normalization equation $p_{\varnothing} + p_2 + p_3 + p_{1,4} = 1$,

$$ p_{\varnothing} = \left( 1 + \frac{1}{3\beta} + \frac{\bar{\lambda}_2 + \beta}{2\bar{\lambda}_3} + \frac{\bar{\lambda}_3 + \beta}{2\bar{\lambda}_2} \right)^{-1}. \tag{44} $$

Taking the limit of (43) and (44) as $\beta \to +\infty$, we conclude that both the lower-bound and the upper-bound in (42) tend to $2\lambda_1\bar{\lambda}_2$ as $\beta \to +\infty$. Then combining (42) with the squeeze theorem allows us to conclude that $\mu_{1,2}$ also tends to $2\lambda_1\bar{\lambda}_2$ as $\beta \to +\infty$. By symmetry, we obtain directly $\mu_{1,3} \to 2\lambda_1\bar{\lambda}_3$, $\mu_{2,4} \to 2\bar{\lambda}_2\lambda_4$, and $\mu_{3,4} \to 2\bar{\lambda}_3\lambda_4$ as $\beta \to +\infty$. According to the change-of-basis equation $\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)$ from (30), this means that $\alpha_+ \to 0$ as $\beta \to +\infty$.
<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_61.png" /><figcaption>■ **Figure 18** 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 to (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)$.</figcaption></figure>

on the edges. The set $\Pi_{\ge 0}$, shown in Figure 20b 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 20c–20g. 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 20g that this vertex has 4 zero coordinates
**Lemma C.1**

Consider a greedy policy $\Phi$ adapted to the graph $D$. We will prove the inequality relations in (41) using a coupling argument. More specifically, we will compare the matching models $(D, I, \Phi)$ and $(D, I, \Phi_+)$, where $I = (I_t, t \in \mathbb{N})$ is a sequence of i.i.d. classes, such that $I_t = i$ with probability $\lambda_i/(\lambda_1 + \lambda_2 + \lambda_4 + \lambda_3)$ for each $t \in \mathbb{N}$ and $i \in V$.

Considering the model $(D, I, \Phi)$, we let $Q_t$ denote the vector of queue sizes at time $t$, $L_{t,i}$ the number of class-i items among the first $t$ arrivals, and $M_{t,\{i,j\}}$ (or $M_{t,i,j}$ for short) the number of times that classes $i$ and $j$ are matched over the first $t$ arrivals, for each $t \in \mathbb{N}$ and $i, j \in V$, as defined in (2)–(5). We introduce similar notation for the model $(D, I, \Phi^+)$, the only difference being that all quantities have superscript $+$. Since both models have the same sequence of incoming items, we have $L_{t,i} = L_{t,i}^+$ for each $t \in \mathbb{N}$ and $i \in V$. As usual, we also assume that $Q_0 = Q_0^+ = 0$. Neither $(Q_t, t \in \mathbb{N})$ nor $(Q_t^+, t \in \mathbb{N})$ need be Markov chains for our argument to hold.

Our end goal is to prove that the following inequalities are satisfied at each time $t \in \mathbb{N}$:

$$M_{t,1,2} \leq M_{t,1,2}^{+}, \qquad (45-1,2)$$

$$M_{t,3,4} \leq M_{t,3,4}^{+}, \qquad (45-3,4)$$

$$M_{t,1,3} \geq M_{t,1,3}^{+}, \qquad (45-1,3)$$

$$M_{t,2,4} \geq M_{t,2,4}^{+}, \qquad (45-2,4)$$

Injecting these inequalities into the definition (9) of the matching rates yields the inequalities (41). We will prove (45) by induction over time $t \in \mathbb{N}$. The following equations will be instrumental to prove the induction step:

$$Q_{t,1} + Q_{t,4} = Q_{t,1}^{+} + Q_{t,4}^{+}, \quad Q_{t,2} = Q_{t,2}^{+}, \quad Q_{t,3} = Q_{t,3}^{+}, \qquad (46)$$

$$L_{t,1} = Q_{t,1} + M_{t,1,2} + M_{t,1,3} = Q_{t,1}^{+} + M_{t,1,2}^{+} + M_{t,1,3}^{+}, \qquad (47)$$

$$L_{4,t} = Q_{t,4} + M_{t,2,4} + M_{t,3,4} = Q_{t,4}^{+} + M_{t,2,4}^{+} + M_{t,3,4}^{+}, \qquad (48)$$

Equation (46) follows from Proposition 6.6(iii), while (47) and (48) follow from our assumption that the arrivals in both models are coupled. Furthermore, given the definition of $Q_G(D)$ in (31), we know that only one integer among $Q_{t,1} + Q_{t,4}$, $Q_{t,2}$, and $Q_{t,3}$ can be positive, for each $t \in \mathbb{N}$.

We now proceed to the induction step. Let $t \in \mathbb{N}$. We now prove that, assuming that the inequalities (45) are satisfied at time $t$, these inequalities are also satisfied at time $t + 1$. We distinguish several cases depending on the value of $I_t$:

**Case $I_t = 1$:** We have directly $M_{t+1,i,j} = M_{t,i,j}$ and $M_{t+1,i,j}^+ = M_{t,i,j}^+$ for $(i, j) \in \{(2, 4), (3, 4)\}$, hence the induction assumption implies that (45–2,4) and (45–3,4) hold at time $t + 1$. Since the policy $\Phi$ is greedy, we only have three mutually-exclusive cases:

**Case $Q_{t,2} \geq 1$:** The class-1 item is matched with a class-2 item already present, and we obtain $M_{t+1,1,2} = M_{t,1,2} + 1$ and $M_{t+1,1,3} = M_{t,1,3}$.

**Case $Q_{t,3} \geq 1$:** The class-1 item is matched with a class-3 item already present, and we obtain $M_{t+1,1,2} = M_{t,1,2}$ and $M_{t+1,1,3} = M_{t,1,3} + 1$.

**Case $Q_{t,2} = Q_{t,3} = 0$:** The class-1 item is left unmatched, and we obtain $M_{t+1,1,2} = M_{t,1,2}$ and $M_{t+1,1,3} = M_{t,1,3}$.

Since the policy $\Phi^+$ is also greedy, we can repeat the same argument for the quantities associated with $\Phi^+$. Combining this observation with (46) yields $M_{t+1,1,2} - M_{t+1,1,2}^+ = M_{t,1,2} - M_{t,1,2}^+$ and $M_{t+1,1,3} - M_{t+1,1,3}^+ = M_{t,1,3} - M_{t,1,3}^+$. Hence, the induction assumption implies directly that (45–1,2) and (45–1,3) are satisfied at time $t + 1$.
<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_62.png" /><figcaption>(b) Generic solution to (CE).</figcaption></figure>

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

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

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

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

■ **Figure 19** 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) \in \mathbb{R}^6$, a particular solution to (CE) is $\mu^* = (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)$ and $b_2 = (0, 0, -1, 1, 0, 1, 0, -1)$.

and only 9 positive coordinates in edge basis; the subgraph defined by the support of this vertex is injective-only.

In light of these examples, we can give the following characterization of the bijective vertices of $\Pi_{\ge 0}$.

► **Proposition 30.** 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.
Case $I_t = 2$: We have directly $M_{t+1,i,j} = M_{t,i,j}$ and $M_{t+1,i,j}^+ = M_{t,i,j}^+$ for $(i,j) \in \{(1,3), (3,4)\}$, hence the induction assumption implies that (45-1,3) and (45-3,4) hold at time $t+1$. Proving that (45-1,2) and (45-2,4) also hold at time $t+1$ is more intricate, and we will distinguish three mutually-exclusive cases depending on the values of $Q_{t,1}$, $Q_{t,4}$, $Q_{t,1}^+$, and $Q_{t,4}^+$:

Case $Q_{t,1}^+ + Q_{t,4}^+ = 0$: Under both policies, the class-2 item is either matched with a class-3 item or added to the queue. In particular, we obtain $M_{t+1,i,j} = M_{t,i,j}$ and $M_{t+1,i,j} = M_{t,i,j}$ for $(i,j) \in \{(1,2), (2,4)\}$, so that (45-1,2) and (45-2,4) are again satisfied at time $t+1$ thanks to the induction assumption.

Case $Q_{t,1}^+ + Q_{t,4}^+ \ge 1$: We again subdivide this case into three mutually-exclusive cases:

Case $Q_{t,1}^+ \ge 1$ and $Q_{t,4}^+ \ge 1$: We have $M_{t+1,1,2}^+ = M_{t,1,2}^+ + 1$ and $M_{t+1,2,4}^+ = M_{t,2,4}^+$ by definition of the policy $\Phi^+$, while for the policy $\Phi$ we only know that $M_{t+1,1,2} \in \{M_{t,1,2}, M_{t,1,2} + 1\}$ and $M_{t+1,2,4} \in \{M_{t,2,4}, M_{t,2,4} + 1\}$. We can verify that (45-1,2) and (45-2,4) hold at time $t+1$ thanks to the induction assumption.

Case $Q_{t,1}^+ = 0$ and $Q_{t,4}^+ \ge 1$: By greediness, the policy $\Phi^+$ matches the incoming class-2 item with a class-4 item, and we obtain $M_{t+1,1,2}^+ = M_{t,1,2}^+$ and $M_{t+1,2,4}^+ = M_{t,2,4}^+ + 1$. If the policy $\Phi$ makes the same decision, then we also have $M_{t+1,1,2} = M_{t,1,2}$ and $M_{t+1,2,4} = M_{t,2,4} + 1$, hence (45-1,2) and (45-2,4) hold at time $t+1$ thanks to the induction assumption. Otherwise, the policy $\Phi$ matches the class-2 item with a class-1 item, meaning that $M_{t+1,1,2} = M_{t,1,2} + 1$ and $M_{t+1,2,4} = M_{t,2,4}$. Importantly, this is only possible if $Q_{t,1} \ge 1$. We now prove (45-1,2) and (45-2,4) as follows:

- Proving (45-1,2) boils down to proving $M_{t,1,2}^+ \ge M_{t,1,2} + 1$. We have successively:

$$M_{t,1,2}^+ - M_{t,1,2} = (Q_{t,1} - Q_{t,1}^+) + (M_{t,1,3} - M_{t,1,3}^+) \ge 1 + 0 = 1,$$

where the equality follows from (47) and the inequality follows from the induction assumption and the fact that $Q_{t,1} \ge 1$ and $Q_{t,1}^+ = 0$.

- Proving (45-2,4) boils down to proving $M_{t,2,4}^+ + 1 \le M_{t,2,4}$. We have successively:

$$M_{t,2,4} - M_{t,2,4}^+ = (Q_{t,4}^+ - Q_{t,4}) + (M_{t,3,4}^+ - M_{t,3,4}) \ge 1 + 0 = 1,$$

where the equality follows from (48) and the inequality follows from the induction assumption and the observation that $Q_{t,4}^+ - Q_{t,4} = Q_{t,1} - Q_{t,1}^+ \ge 1$.

Intuitively, the only way that an incoming class-2 item is matched at time $t$ with a class-1 item under the policy $\Phi$ and with a class-4 item under the policy $\Phi^+$ is if, in the past, the policy $\Phi^+$ had made one more match along edge $\{1,2\}$ and one less match along edge $\{2,4\}$ compared to the policy $\Phi$.

Case $Q_{t,1}^+ \ge 1$ and $Q_{t,4}^+ = 0$: This case is symmetrical to the previous case.

Case $I_t = 3$: This case is symmetrical to the case $I_t = 2$.

Case $I_t = 4$: This case is symmetrical to the case $I_t = 1$.
<figure><img src="image_67.png" /><figcaption>■ **Figure 20** 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 20a.</figcaption></figure>

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 directly from Definition 29.

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

► **Remark 10.** We can further explore the relationship between vertices and their support graph. Again consider a vertex $\mu$ of $\Pi_{\ge 0}$, and let $G^*$ denote the support graph of $\mu$ and $A^*$ its incidence matrix. According to Definitions 2, 3, and 5, the subgraph $G^*$ is injective if and only if each connected component of $G^*$ is either a tree or a unicyclic graph with an odd cycle. For each connected component of $G^*$ that is a tree, and therefore a bipartite graph with parts $V_+$ and $V_-$, the existence of vertex $\mu$ implies that

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

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 $A^*$ if and only if $\lambda$ satisfies (29) for each connected component of $G^*$ that is a tree. Note that
this condition is void if $G^*$ is bijective because, in this case, none of the connected components of $G^*$ is a tree.

Conversely, one can wonder which injective subgraph $G^*$ of $G$ defines a vertex of $\Pi_{\ge 0}$. Satisfying (29) for each tree connected component of $G^*$ only guarantees the existence of a (unique) solution $z \in \mathbb{R}^p$ to the conservation equation $A^*z = \lambda$. If each coordinate 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, $G^*$ does not define a vertex of $\Pi_{\ge 0}$.

### C.4 Proof of Proposition 14 in Section 5.2.2 (Probability of bijectivity).

Let $C$ denote the set of normalized arrival rate vectors $\lambda$ such that $(G, \lambda)$ is stabilizable:

$$C = \{\lambda \in \Delta^{n-1} : (G, \lambda) \text{ stabilizable}\}.$$

To prove Proposition 14, we proceed as follows:

- We prove that $C$ is non-empty and convex, hence measurable.

- We prove that $C$ is an open set (for the Lesbegue measure), so its probability is positive and the conditional probability given $C$ is well-defined.

- We prove that if a vertex is injective-only, the vector $\lambda$ must respect a constraint that reduces the dimension of the possible solutions, meaning that the measure of the event is null.

We first prove the different properties of $C$.

*C is not empty.* We use Remark 1: consider $\lambda = A\mu$, with $\mu = (\frac{1}{2m}, \dots, \frac{1}{2m})$. The matching problem $(G, \lambda)$ is stabilizable as all coordinates of $\mu$ are positive. Moreover, one can check that $\lambda = (\frac{d_1}{2m}, \dots, \frac{d_n}{2m})$, where $d_i$ is the degree of node $i$, so $\lambda \in \Delta^{n-1} (\sum_i d_i = 2m)$. Hence, $\lambda \in C$.

*C is convex.* Let $\lambda_a$ and $\lambda_b$ be two vectors of $C$. Let $\mu_a \in \mathbb{R}_{>0}^m$ and $\mu_b \in \mathbb{R}_{>0}^m$ be positive solutions to $A\mu_a = \lambda_a$ and $A\mu_b = \lambda_b$ respectively (such solutions exist as stated in Proposition 8). For $0 < x < 1$, consider $\lambda = x\lambda_a + (1-x)\lambda_b$. $\lambda \in \Delta^{n-1}$ because $\Delta^{n-1}$ is convex. Moreover, we have $A\mu = \lambda$, with $\mu = x\mu_a + (1-x)\mu_b$. As $\mathbb{R}_{>0}^m$ is convex, $\mu \in \mathbb{R}_{>0}^m$, so $(G, \lambda)$ is stabilizable (Proposition 8), hence $\lambda \in C$.

*C is open in $\Delta^{n-1}$.* Let $\lambda \in C$. For some $\epsilon > 0$, let $\lambda_\epsilon$ be an element of $\Delta^{n-1}$ such that $||\lambda - \lambda_\epsilon||_1 < \epsilon$. To prove that $C$ is open, we just need to show that $\lambda_\epsilon \in C$ if $\epsilon$ is small enough. Let $\mu \in \mathbb{R}_{>0}^m$ be a positive solution to $A\mu = \lambda$. Using Equations (18) and (19), we can write $\mu = A^+\lambda + \mu_\alpha$, with $\mu_\alpha = \mu - A^+\lambda = (\mathrm{Id}_{m \times m} - A^+A)\mu \in \ker(A)$. Consider now $\mu_\epsilon = A^+\lambda_\epsilon + \mu_\alpha$. We have $A\mu_\epsilon = AA^+\lambda_\epsilon + A\mu_\alpha = \lambda_\epsilon$ so $(\lambda_\epsilon, \mu_\epsilon)$ checks (CE). Moreover, $||\mu - \mu_\epsilon||_1 = ||A^+(\lambda - \lambda_\epsilon)||_1 < ||A^+||_1\epsilon$, where $||A^+||_1 < +\infty$ is the operator norm of $A^+$ associated to the 1-norm. All coordinates of $\mu$ are positive, so if $\epsilon$ is small enough, it also the case for $\mu_\epsilon$, meaning that $(G, \lambda_\epsilon)$ is stabilizable (Proposition 8). In other words, $\lambda_\epsilon \in C$.

This establishes that $C$ (i.e., the stabilizability of $(G, \lambda)$) defines a proper conditional probability. We now examine the conditions under which the polytope $\Pi_{\ge 0}$ of a stabilizable problem $(G, \lambda)$ possesses an injective-only vertex.

Consider $\lambda \in \Delta^{n-1}$. Let $\mu$ be a solution to $A\mu = \lambda$. Using Definition 11 and the pseudoinverse approach from Section 5.1.2, the kernel coordinates of $\mu$ are $\alpha = B^+(\mathrm{Id}_{m \times m} - A^+A)\mu$, so we can write

$$\mu = B\alpha + A^+\lambda = D\gamma,$$

where $D = (B|A^+)$ is the $m \times m$ horizontal concatenation of $B$ and $A^+$, and $\gamma = (\alpha_1, \dots, \alpha_d, \lambda_1, \dots, \lambda_n)$ is the concatenation of $\alpha$ and $\lambda$.
Notice that $D$ depends solely on $G$ and is invertible. Its inverse can be verified as the
vertical concatenation of $B^+(\mathrm{Id}_{m \times m} - A^+A)$ and $A$: any matching rate vector $\mu$ uniquely
defines $\lambda$ and $\alpha$.

We now assume that one vertex of the polytope is injective-only and look for the
implications for $\lambda$.

The existence of an injective-only vertex implies that there exists a subset of edges
$K \subset E$, with $|K| > d$, such that $\mu$ is null on $K$ (remind that $d = m - n$ is the dimension
of $\ker(A)$). Let $D|_K$ denote the $|K| \times m$ submatrix of $D$ formed by the rows corresponding
to $K$, and let $B|_K$ denote the $d$ first columns of $D|_K$, that is the part of $D|_K$ that handles
$\alpha$. As $|K| > d$, we have $\ker((B|_K)^\top) \neq \{0\}$, meaning that there exists a non-trivial linear
combination $v \in \mathbb{R}^{|K|} \setminus \{0\}$ of the rows of $B|_K$ such that $vB|_K = 0$.

Let $A^+|_K$ denotes the $n$ last columns of $D|_K$, that is the part of $D|_K$ that handles $\lambda$.
We know that $vD|_K \neq 0$ because $D$ is invertible, so its row are linearly independent. As
$vB|_K = 0$, this means that $vA^+|_K \neq 0$. The vector $u = vA^+|_K$ can be seen as a non-trivial
linear combination of the coordinates of $\lambda$.

We can now conclude: if the polytope $\Pi_{\ge 0}$ associated to some $\lambda \in C$ admits an injective-
only vertex, we have a subset of edges $K \subset E$, with $|K| > d$ such that $D|_K \gamma = 0$. In
particular, we must have $vD|_K \gamma = 0$, which simplifies as $u\lambda = 0$. In other words, for $\mu$ to be
null over $K$, the vector $\lambda$ must belong to some hyperplane $L_u$ of dimension $n-1$ that can be
built solely from $G$ and $K$. As $\Delta^{n-1} \neq L_u$ (one is affine, the other is not), the intersection
$\Delta^{n-1} \cap L_u$, if it exists, has a dimension at most $n-2$. In particular, the Lebesgue measure of
$\Delta^{n-1} \cap L_u$ (over $\Delta^{n-1}$) is null, meaning that the probability to nullify all edges of $K$ is null.

The number of subsets $K \subset E$ such that $|K| > d$ is finite, so the probability to nullify
all edges of any of them is also null, so the probability that the polytope $\Pi_{\ge 0}$ associated to
some $\lambda \in C$ admits an injective-only vertex is null. $\quad$
D Supplementary material of Section 6 (Stable policy optimization).

D.1 Proof of Proposition 19

We consider an arbitrary Markovian, stationary matching policy that matches at most $M \in \mathbb{N}$ pairs of items in one time step. In particular, we consider a matching policy that only depends on the current state of the underlying Markov chain of the matching problem. To be more precise, consider an irreducible, aperiodic, and positive recurrent DTMC ($S_t, t \in \mathbb{N}$) defined in a similar way as in Appendix A, such that $Q_t$ and $\Phi_t$ are functions of $S_t$, where $\Phi_{t,i}$ is the number of class-i items matched at time $t$ for all $i \in V$. If $Q_t = S_t$, then the matching policy simply depends on the current queue lengths, e.g., ML policy. Now, given an injective-only vertex $\mu$, the following proposition formalizes the trade-off between closeness to $\mu$ and the queue lengths in the steady-state (denoted by $Q_\infty$) for any such matching policy. Proposition 19 is a special case of Extended Proposition 19 with $M = 1$. The proof of Extended Proposition 19 is given in the rest of the appendix.

**Extended Proposition 19.** Consider an injective-only vertex $\mu$ of $\Pi_{\ge 0}$. Then, under any Markovian, stationary matching policy $\Phi$ that matches at most $M \in \mathbb{N}$ pairs of items in one-time step, if $\|\mu(\Phi) - \mu\|_1 \le \epsilon$, then $\mathbb{E}[\|Q_\infty\|_2^2] \ge \Omega(1/\epsilon)$, where $Q_\infty$ is the queue length under the steady state of $(S_t, t \in \mathbb{N})$.

As $\mu$ is injective-only, there exists a connected component of $G^* = (V, E^*)$ that is bipartite by Definitions 3 and 4. Denote such a connected component by $G^o = (V^+ \cup V^-, E^o)$, where $V^+$ and $V^-$ are the (disjoint) parts of the connected component, and $E^o \subseteq E^*$. Now, consider the following test function:

$$W(q) = \langle 1^{(V^+,V^-)}, q \rangle^2, \quad q \in \mathcal{Q},$$

where $1_i^{(V^+,V^-)} = 1$ for $i \in V^+$, $-1$ for $i \in V^-$, and 0 otherwise. For each $t \in \mathbb{N}$, let $A_t$ denote the class of the incoming item at time $t$, so that $A_t = 1_{I_t}$, where $I_t$ is the class of $(t+1)$-th item. Thus, $\lambda_i / \sum_{j \in V} \lambda_j$ is the probability that $A_t = 1_i$. We also define $\delta M_{t,k} = M_{t,k} - M_{t-1,k}$ to be the number of items matched using edge $k \in E$ at time $t$. Thus, we have $\sum_{k \in E_i} \delta M_{t,k} = \Phi_{t,i}$ for all $i \in V$. For the rest of the proof, we consider the steady-state of the Markov chain underlying the matching problem. In particular, we consider the steady-state of the (discrete-time) Markov chain ($S_t, t \in \mathbb{N}$), of which $Q = (Q_t, t \in \mathbb{N})$ and $\Phi = (\Phi_t, t \in \mathbb{N})$ are functions.

If $\mathbb{E}[W(Q)] = \infty$, then we have $\mathbb{E}[\sum_{i \in V} Q_i^2] = \infty$ which completes the proof of the proposition. Indeed, for each $q \in \mathbb{N}^n$,

$$ 
\begin{aligned}
W(q) &= \left(\sum_{i \in V^+} q_i\right)^2 + \left(\sum_{i \in V^-} q_i\right)^2 - 2 \left(\sum_{i \in V^+} q_i\right) \left(\sum_{i \in V^-} q_i\right), \\
&\le \left(\sum_{i \in V^+} q_i\right)^2 + \left(\sum_{i \in V^-} q_i\right)^2, \\
&\le |V^+| \sum_{i \in V^+} q_i^2 + |V^-| \sum_{i \in V^-} q_i^2.
\end{aligned}
$$

Now, assume instead that $\mathbb{E}[W(Q)] < \infty$. In stationarity, we have $\mathbb{E}[W(Q_{t+1})] = \mathbb{E}[W(Q_t)]$. In particular, we take the expectation under the steady state distribution of $(S_t, t \in \mathbb{N})$.
Using this, we get

$$
\begin{align*}
0 &= \mathbb{E} \left[ \langle \mathbf{1}^{(V^+,V^-)}, Q_{t+1} \rangle^2 - \langle \mathbf{1}^{(V^+,V^-)}, Q_t \rangle^2 \right], \\
&= \mathbb{E} \left[ \langle \mathbf{1}^{(V^+,V^-)}, Q_t + A_t - \Phi_t \rangle^2 - \langle \mathbf{1}^{(V^+,V^-)}, Q_t \rangle^2 \right], \\
&= \mathbb{E} \left[ \langle \mathbf{1}^{(V^+,V^-)}, A_t - \Phi_t \rangle^2 \right] + 2\mathbb{E} \left[ \langle \mathbf{1}^{(V^+,V^-)}, Q_t \rangle \langle \mathbf{1}^{(V^+,V^-)}, A_t - \Phi_t \rangle \right], \\
&\stackrel{(a)}{=} \mathbb{E} \left[ \langle \mathbf{1}^{(V^+,V^-)}, A_t - \Phi_t \rangle^2 \right] - 2\mathbb{E} \left[ \langle \mathbf{1}^{(V^+,V^-)}, Q_t \rangle \langle \mathbf{1}^{(V^+,V^-)}, \Phi_t \rangle \right], \\
&\stackrel{(b)}{\ge} \frac{\sum_{i \in V^+ \cup V^-} \lambda_i}{\sum_{i \in V} \lambda_i} - 2\mathbb{E} \left[ \langle \mathbf{1}^{(V^+,V^-)}, Q_t \rangle \langle \mathbf{1}^{(V^+,V^-)}, \Phi_t \rangle \right], \\
&\stackrel{(c)}{\ge} \frac{\sum_{i \in V^+ \cup V^-} \lambda_i}{\sum_{i \in V} \lambda_i} - 2\sqrt{\mathbb{E} \left[ \langle \mathbf{1}^{(V^+,V^-)}, Q_t \rangle^2 \right] \mathbb{E} \left[ \langle \mathbf{1}^{(V^+,V^-)}, \Phi_t \rangle^2 \right]} \quad \text{(by Cauchy-Schwarz)}, \\
&\stackrel{(d)}{\ge} \frac{\sum_{i \in V^+ \cup V^-} \lambda_i}{\sum_{i \in V} \lambda_i} - 4\sqrt{\mathcal{M} \mathbb{E} \left[ \left( \sum_{i \in V} Q_{t,i} \right)^2 \right] \sum_{k \in E \setminus E^*} \mathbb{E} [\delta M_{t,k}]}, \\
&\stackrel{(e)}{\ge} \frac{\sum_{i \in V^+ \cup V^-} \lambda_i}{\sum_{i \in V} \lambda_i} - 4\sqrt{\mathcal{M} \epsilon \mathbb{E} \left[ \left( \sum_{i \in V} Q_{t,i} \right)^2 \right]} \quad (30)
\end{align*}
$$

Here, (a) follows by noting that $\mathbb{E}[\langle \mathbf{1}^{(V^+,V^-)}, A_t \rangle] = \mathbb{E}[\langle \mathbf{1}^{(V^+,V^-)}, \lambda \rangle] = 0$, as $\mu$ is a feasible solution to the conservation equations (CE) and $G^\circ = (V^+ \cup V^-, E^\circ)$ is a connected component of the subgraph of $G$ induced by support of $\mu$. Note that we also use the independence of $A_t$ and $Q_t$ in this step. Next, (b) follows by noting that $\langle \mathbf{1}^{(V^+,V^-)}, A_t - \Phi_t \rangle \ge 1$ whenever $\langle \mathbf{1}^{(V^+,V^-)}, A_t \rangle = \pm 1$ (because $\langle \mathbf{1}^{(V^+,V^-)}, \Phi_t \rangle$ is an even number, as each match is counted twice), and that the event $\langle \mathbf{1}^{(V^+,V^-)}, A_t \rangle = \pm 1$ happens with probability $\frac{\sum_{i \in V^+ \cup V^-} \lambda_i}{\sum_{i \in V} \lambda_i}$. Further, (c) follows by noting that

$$
\begin{align*}
| \langle \mathbf{1}^{(V^+,V^-)}, \Phi_t \rangle | &= \left| \sum_{i \in V^+} \Phi_{t,i} - \sum_{i \in V^-} \Phi_{t,i} \right| = \left| \sum_{i \in V^+} \sum_{j \in V_i} \delta M_{t,\{i,j\}} - \sum_{i \in V^-} \sum_{j \in V_i} \delta M_{t,\{i,j\}} \right|, \\
&\le \sum_{i \in V^+} \sum_{j \in V_i \setminus V^-} \delta M_{t,\{i,j\}} + \sum_{i \in V^-} \sum_{j \in V_i \setminus V^+} \delta M_{t,\{i,j\}}, \\
&\qquad + \left| \sum_{i \in V^+} \sum_{j \in V_i \cap V^-} \delta M_{t,\{i,j\}} - \sum_{i \in V^-} \sum_{j \in V_i \cap V^+} \delta M_{t,\{i,j\}} \right|, \quad \text{(Triangle Inequality)} \\
&\stackrel{(*)}{=} \sum_{i \in V^+} \sum_{j \in V_i \setminus V^-} \delta M_{t,\{i,j\}} + \sum_{i \in V^-} \sum_{j \in V_i \setminus V^+} \delta M_{t,\{i,j\}}, \\
&\stackrel{(**)}{\le} 2 \sum_{k \in E \setminus E^*} \delta M_{t,k},
\end{align*}
$$
where (*) follows by noting that $\sum_{i \in V^+} \sum_{j \in V_i \cap V^-} \delta M_{t, \{i, j\}} = \sum_{i \in V^-} \sum_{j \in V_i \cap V^+} \delta M_{t, \{i, j\}}$ as the set of edges that we are summing over are the same in the left and right hand side. In particular, we are adding over all the edges between $V^+$ and $V^-$. Next, (**) follows by noting that all edges connecting $i \in V^+$ to $j \in V \setminus V^-$ are not in $E^*$. Similarly, all edges connecting $i \in V^-$ to $j \in V \setminus V^+$ are also not in $E^*$ by the definition of $G^o$. Now, (d) follows by the assumption that at most $M$ pairs of items can be matched in a single time step. Lastly, (e) follows as $\mathbb{E}[\delta M_t] = \mu(\Phi)$ in the steady state and

$$ \|\mu(\Phi) - \mu\|_1 \le \epsilon \implies \sum_{k \in E \setminus E^*} \mu(\Phi)_k \le \epsilon. $$

Now, to complete the proof, we use (30) which implies

$$ \mathbb{E}\left[\sum_{i \in V} Q_{\infty,i}^2\right] \ge \frac{1}{|V|} \mathbb{E}\left[\left(\sum_{i \in V} Q_{\infty,i}\right)^2\right] \stackrel{(30)}{\ge} \frac{(\sum_{i \in V^+ \cup V^-} \lambda_i)^2}{16M|V| (\sum_{i \in V} \lambda_i)^2} \cdot \frac{1}{\epsilon} = \Omega\left(\frac{1}{\epsilon}\right). $$

Note that the first inequality follows as $\|q\|_2^2 \ge \|q\|_1^2/|V|$ for all $q \in \mathbb{R}^{|V|}$. This completes the proof. $\blacksquare$

## D.2 Proof of Proposition 18

We first prove two intermediary results, Lemmas 31 and 32, that will be instrumental in proving the upper bound for the mean queue length in Proposition 18.

**Lemma 31.** Consider a matching problem $(G, \lambda)$. If the CRPG $\delta(G, \lambda)$ is positive, then the ML policy stabilizes $(G, \lambda)$, and

$$ \mathbb{E}\left[\sum_{i \in V} Q_i\right] \le \frac{n}{2\delta(G, \lambda)} \sum_{i \in V} \lambda_i. $$

**Proof.** Consider the quadratic test function $W$ defined on $Q_G$ by

$$ W(q) = \sum_{i \in V} q_i^2, \quad q \in Q_G. $$

We define the drift of this test function by $\Delta W(q) = \mathbb{E}[W(Q_{t+1}) - W(Q_t)|Q_t = q]$ for each $q \in Q_G$. Lastly, we let $\mathcal{I}_q = \{i \in V : q_i > 0\}$ denote the support of $q$, for each $q \in Q_G$. Now, we simplify the drift under the ML policy using the queue evolution recursion given by (2). For all $q \in Q_G \setminus \{0\}$, we have

$$ \begin{align*} \Delta W(q) &= \mathbb{E}\left[\sum_{i \in V} (Q_{t,i} + 1\{i = I_t\})^2 1\{J_t = \perp\} + (Q_{t,i} - 1\{i = J_t\})^2 1\{J_t \neq \perp\} - Q_{t,i}^2 \middle| Q_t = q\right], \\ &= \mathbb{E}\left[\sum_{i \in V} 1\{i = I_t, J_t = \perp\} + 1\{i = J_t\} + 2(1\{i = I_t, J_t = \perp\} - 1\{i = J_t\}) Q_{t,i} \middle| Q_t = q\right], \\ &\stackrel{(a)}{=} 1 + 2 \sum_{i \in V} q_i \mathbb{E}\left[1\{i = I_t, J_t = \perp\} - 1\{i = J_t\} \middle| Q_t = q\right], \\ &\stackrel{(b)}{=} 1 + \frac{2}{\sum_{i \in V} \lambda_i} \sum_{i \in V} \lambda_i q_i - 2 \sum_{i \in V} q_i \mathbb{E}\left[1\{i = J_t\} \middle| Q_t = q\right], \end{align*} $$
$$
\begin{align}
&\stackrel{(c)}{=} 1 + \frac{2}{\sum_{i \in V} \lambda_i} \sum_{i \in V} \lambda_i q_i - \frac{2}{\sum_{i \in V} \lambda_i} \sum_{j \in V} \lambda_j \max_{i \in V_j} q_i, \nonumber \\
&\stackrel{(d)}{=} 1 + \frac{2}{\sum_{i \in V} \lambda_i} \sum_{i \in \mathcal{I}_q} \lambda_i q_i - \frac{2}{\sum_{i \in V} \lambda_i} \sum_{j \in V(\mathcal{I}_q)} \lambda_j \max_{i \in V_j} q_i, \nonumber \\
&\stackrel{(e)}{\le} 1 - \frac{2\delta(G, \lambda)}{|\mathcal{I}_q| \sum_{i \in V} \lambda_i} \sum_{i \in \mathcal{I}_q} q_i, \nonumber \\
&= 1 - \frac{2\delta(G, \lambda)}{|\mathcal{I}_q| \sum_{i \in V} \lambda_i} \sum_{i \in V} q_i, \nonumber \\
&\le 1 - \frac{2\delta(G, \lambda)}{n \sum_{i \in V} \lambda_i} \sum_{i \in V} q_i. \tag{31}
\end{align}
$$

Here, (a) follows as

$$
\sum_{i \in V} \mathbb{1}\{i = I_t, J_t = \perp\} + \sum_{i \in V} \mathbb{1}\{i = J_t\} = \mathbb{1}\{J_t = \perp\} + \mathbb{1}\{J_t \neq \perp\} = 1.
$$

Next, (b) follows as for all $i \in V$, we have

$$
\begin{align*}
q_i \mathbb{E} [1\{i = I_t, J_t = \perp\} | Q_t = Q] &= q_i \mathbb{P} \{i = I_t, J_t = \perp | Q_t = q\}, \\
&= q_i \mathbb{P} \{J_t = \perp | Q_t = q, i = I_t\} \mathbb{P} \{i = I_t | Q_t = q\}, \\
&= q_i \frac{\lambda_i}{\sum_{i \in V} \lambda_i} \mathbb{1} \left\{ \max_{j \in V_i} q_j = 0 \right\} = q_i \frac{\lambda_i}{\sum_{i \in V} \lambda_i}.
\end{align*}
$$

The last equality follows from the fact that the ML policy is greedy, which implies that, if $q_i > 0$, then $q_j = 0$ for all $j \in V_i$. Now, (c) follows by using the definition of ML policy. In particular, we have

$$
\sum_{i \in V} q_i \mathbb{E} \left[ 1\{i = J_t\} \mid Q_t = q \right] = \frac{1}{\sum_{j \in V} \lambda_j} \sum_{j \in V} \lambda_j \sum_{i \in V} q_i \mathbb{E} \left[ 1\{i = J_t\} \mid Q_t = q, j = I_t \right], \\
= \frac{1}{\sum_{j \in V} \lambda_j} \sum_{j \in V} \lambda_j \max_{i \in V_j} q_i.
$$

The equality (d) follows by noting that $\mathcal{I}_q$ is equal to the support of $q$, i.e., we have
$\mathcal{I}_q = \{i \in V : q_i > 0\}$. The rest of the paragraph is dedicated to proving (e). Consider the
bipartite graph

$$
G_q = G(\mathcal{I}_q \cup V(\mathcal{I}_q), E_q) \quad \text{with} \quad E_q = \{\{i,j\} \in E : i \in \mathcal{I}_q, j \in V(\mathcal{I}_q)\}.
$$

By definition of $\delta(G, \lambda)$, we have, for each $\mathcal{I} \subseteq \mathcal{I}_q$,

$$
\sum_{i \in \mathcal{I}} \lambda_i \le \sum_{j \in V(\mathcal{I})} \lambda_j - \delta(G, \lambda) = \sum_{\substack{j \in V(\mathcal{I}) \\ \exists i \in \mathcal{I}, \{i,j\} \in E_q}} \lambda_j - \delta(G, \lambda),
$$

where the equality follows as $V(\mathcal{I}) \subseteq V(\mathcal{I}_q)$, and so, $V(\mathcal{I}) = V(\mathcal{I}) \cap \{j : \exists i \in \mathcal{I}, \{i,j\} \in E_q\}$
by the definition of $G_q$. Now, the above inequality implies that

$$
\sum_{i \in \mathcal{I}} \left( \lambda_i + \frac{\delta(G, \lambda)}{|\mathcal{I}_q|} \right) \le \sum_{\substack{j \in V(\mathcal{I}) \\ \exists i \in \mathcal{I}, \{i,j\} \in E_q}} \lambda_j \quad \forall \mathcal{I} \subseteq \mathcal{I}_q.
$$
So, by the weighted version of Hall's marriage theorem [22, Lemma 2.5], there exists $\tilde{\mu} \in \mathbb{R}_{\ge 0}^{|E_Q|}$ such that

$$ \lambda_i + \frac{\delta(G, \lambda)}{|\mathcal{I}_q|} = \sum_{\substack{j \in V(\mathcal{I}_q): \\ \{i,j\} \in E_q}} \tilde{\mu}_{i,j}, \quad \forall i \in \mathcal{I}_q, \qquad \lambda_j \ge \sum_{\substack{i \in \mathcal{I}_q: \\ \{i,j\} \in E_q}} \tilde{\mu}_{i,j}, \quad \forall j \in V(\mathcal{I}_q). $$

Using the above, we get

$$ \sum_{i \in \mathcal{I}_q} \lambda_i q_i - \sum_{j \in V(\mathcal{I}_q)} \lambda_j \max_{i' \in V_j} q_{i'} \le \sum_{\{i,j\} \in E_q} \tilde{\mu}_{i,j} \left( q_i - \max_{i' \in V_j} q_{i'} \right) - \frac{\delta(G, \lambda)}{|\mathcal{I}_q|} \sum_{i \in \mathcal{I}_q} q_i \le -\frac{\delta(G, \lambda)}{|\mathcal{I}_q|} \sum_{i \in \mathcal{I}_q} q_i, $$

where the last inequality follows as $\max_{i' \in V_j} q_{i'} \ge q_i$ for all $\{i, j\} \in E_q$. This completes the proof of (e).

Now, by (31) we immediately conclude that

$$ \Delta W(q) \le -1 \quad \text{for each } q \in \mathcal{Q}_G \text{ such that } \sum_{i \in V} q_i \ge \frac{n \sum_{i \in V} \lambda_i}{\delta(G, \lambda)}. $$

Thus, by the Foster-Lyapunov theorem [40], we conclude from (31) that the Markov chain under the ML policy is positive recurrent. Now, by the moment bound theorem [25, Proposition 6.14], we further conclude that in steady state, we have

$$ \mathbb{E} \left[ \sum_{i \in V} Q_i \right] \le \frac{n}{2\delta(G, \lambda)} \sum_{i \in V} \lambda_i. $$

This completes the proof of the lemma.

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

Now we turn our attention to studying the CRPG of $(G', \lambda'_\epsilon)$. We start by defining additional notations for convenience. Define the set of “positive” vertices by $V^+ = \{i^+ : i \in V\}$ and the set of “negative” vertices by $V^- = \{i^- : i \in V\}$. Let $\mathbb{I}_{G'}$ be the set of all independent sets in $G'$. Note that, each independent set $\mathcal{I} \in \mathbb{I}_{G'}$ can be uniquely written as $\mathcal{I} = J^- \cup K^+$ where $J^- = \mathcal{I} \cap V^-$ and $K^+ = \mathcal{I} \cap V^+$ (with at least one of them nonempty). Observe we have $J \in \{\emptyset\} \cup \mathbb{I}_G$ and $K \in \{\emptyset\} \cup \mathbb{I}_{G^*}$. Now, we lower bound the CRPG of the augmented graph in the following lemma. In particular, combining the following lemma with Proposition 8 implies that $(G', \lambda'_\epsilon)$ is stabilizable whenever $(G, \lambda)$ is.

**► Lemma 32.** For the augmented problem $(G', \lambda'_\epsilon)$, we have

$$ \delta(G', \lambda'_\epsilon) \ge \min \left\{ \epsilon \min_{i \in V} \lambda_i + \delta(G^*, \lambda), (1-\epsilon) \min_{i \in V} \lambda_i + \delta(G^*, \lambda), \delta(G, \lambda) \right\}. $$

**Proof.** Consider $\mathcal{I} \in \mathbb{I}_{G'}$ and let $J \in \{\emptyset\} \cup \mathbb{I}_G$ and $K \in \{\emptyset\} \cup \mathbb{I}_{G^*}$ such that $J^- = \mathcal{I} \cap V^-$ and $K^+ = \mathcal{I} \cap V^+$, so that $\mathcal{I} = J^- \cup K^+$. Using the definition of $G'$, we can verify that, for each $0 < \epsilon < 1$, we have

$$ \sum_{i \in V_{G'}(\mathcal{I})} \lambda'_{\epsilon,i} - \sum_{i \in \mathcal{I}} \lambda'_{\epsilon,i} = \epsilon \left( \sum_{i \in V_G(J)} \lambda_i - \sum_{i \in J} \lambda_i \right) + (1-\epsilon) \sum_{i \in V_G(J) \setminus V_{G^*}(K)} \lambda_i \\ + (1-\epsilon) \left( \sum_{i \in V_{G^*}(K)} \lambda_i - \sum_{i \in K} \lambda_i \right) + \epsilon \sum_{i \in V_G(K) \setminus V_G(J)} \lambda_i. \quad (32) $$
Now, we consider the following two cases.

**Case I:** Either $V_G(K) \not\subseteq V_G(J)$ or $V_G(J) \not\subseteq V_{G^*}(K)$. In this case, either the second term or the fourth term in (32) is non-zero; they are for instance bounded from below by $\min\{\epsilon, 1-\epsilon\} \min_{i \in V} \lambda_i$. In addition, the first and the third term are bounded below by $\epsilon\delta(G^*, \lambda)$ and $(1-\epsilon)\delta(G^*, \lambda)$ by the definition of $\delta$ (22). So, we have

$$ \sum_{i \in V_{G^*}(I)} \lambda'_{\epsilon, i} - \sum_{i \in \mathcal{I}} \lambda'_{\epsilon, i} \geq \min \{\epsilon, 1-\epsilon\} \min_{i \in V} \lambda_i + \delta(G^*, \lambda) \quad \forall I \in \mathbb{I}_{G^*}. \quad (33) $$

**Case II:** We have $V_G(K) \subseteq V_G(J)$ and $V_G(J) \subseteq V_{G^*}(K)$. In this case, we must have $J \neq \emptyset$ and $K \neq \emptyset$. Thus, we have

$$ V_{G^*}(K) \subseteq V_G(K) \subseteq V_G(J) \subseteq V_{G^*}(K) \implies V_{G^*}(K) = V_G(K). $$

Now, as $K \in \mathbb{I}_{G^*}$, we have $K \cap V_{G^*}(K) = \emptyset$. Thus, we have $K \cap V_G(K) = \emptyset$ which implies that $K \in \mathbb{I}_G$. Now, using the above, we get

$$ \sum_{i \in V_{G^*}(K)} \lambda_i - \sum_{i \in K} \lambda_i = \sum_{i \in V_G(K)} \lambda_i - \sum_{i \in K} \lambda_i \geq \delta(G, \lambda), \quad \text{and} \quad \sum_{i \in V_G(J)} \lambda_i - \sum_{i \in J} \lambda_i \geq \delta(G, \lambda), $$

where the inequalities above follow by the definition of $\delta(G, \lambda)$ and noting that $J, K \in \mathbb{I}_G$. Now, using (32), we get

$$ \sum_{i \in V_{G^*}(I)} \lambda'_{\epsilon, i} - \sum_{i \in \mathcal{I}} \lambda'_{\epsilon, i} \geq \delta(G, \lambda). \quad (34) $$

Now, by combining (33) and (34), for all $I \in \mathbb{I}_{G^*}$ we get

$$ \sum_{i \in V_{G^*}(I)} \lambda'_{\epsilon, i} - \sum_{i \in \mathcal{I}} \lambda'_{\epsilon, i} \geq \min \left\{ \epsilon \min_{i \in V} \lambda_i + \delta(G^*, \lambda), (1-\epsilon) \min_{i \in V} \lambda_i + \delta(G^*, \lambda), \delta(G, \lambda) \right\}, $$

which completes the proof by definition of $\delta(G', \lambda'_\epsilon)$. ▼

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

Now that we have stated and proved Lemmas 31 and 32, we are ready to prove Proposition 18 below.

**Proof of Proposition 18.** We divide the proof into two parts. In the first part, we show that the expected queue length is $O(1/\epsilon)$. Then, the second part deals with the matching rates.

**Controlling the expected queue length:** By Lemma 32, we know that $\delta(G', \lambda'_\epsilon) > 0$. The corresponding queueing system is stable by Proposition 8. Furthermore, we have

$$ \mathbb{E}\left[\sum_{i \in V} Q_i\right] = \mathbb{E}\left[\sum_{i \in V^+ \cup V^-} Q_i\right] \leq \frac{2n}{2\delta(G', \lambda'_\epsilon)} \sum_{i \in V} \lambda_i \leq \frac{n}{\min\{\epsilon \min_{i \in V} \lambda_i + \delta(G^*, \lambda), \delta(G, \lambda)\}} \sum_{i \in V} \lambda_i, $$

where the first inequality follows by applying Lemma 31 to the extended matching problem $(G', \lambda'_\epsilon)$, and the second inequality follows by applying Lemma 32 and noting that, for all $\epsilon \in (0, 0.5)$, we have $\epsilon \leq 1-\epsilon$. Now, by defining $C_1 = n \sum_{i \in V} \lambda_i$, the proof of the first part is complete.

**Controlling the matching rates:** Now, we show the second part of the proposition. Let $\Phi'_\epsilon$ denote the ML policy adapted to $(G', \lambda'_\epsilon)$. As explained at the beginning of Section 6.3, the policies $\Phi_\epsilon$ and $\Phi'_\epsilon$ are practically equivalent, except that $\Phi_\epsilon$ is seen as a (non-greedy $\epsilon$-dependent) policy adapted to the original problem $(G, \lambda)$, while $\Phi'_\epsilon$ is seen as a (greedy) policy adapted to the $(\epsilon$-dependent) extended problem $(G', \lambda'_\epsilon)$. Consistently, $\mu(\Phi_\epsilon)$ is the
matching-rate vector (indexed by E) under the $\epsilon$-filtering ML policy adapted to $(G, \lambda)$ with filter $E^*$, while $\mu(\Phi'_\epsilon)$ denotes the matching-rate vector (indexed by $E'$) under the ML policy adapted to $(G', \lambda'_\epsilon)$. The rest of the proof is divided mainly in two parts: first we prove the following bound on our objective $\|\mu - \mu(\Phi_\epsilon)\|_1$ in terms of $\mu(\Phi'_\epsilon)$:

$$ \|\mu - \mu(\Phi_{\epsilon})\|_{1} \le \sum_{\{i,j\} \in E^{*}} |\mu_{i,j} - \mu(\Phi'_{\epsilon})_{i^{+},j^{+}}| + 2\epsilon \sum_{j \in V} \lambda_{j}. \quad (35) $$

Then, we show that $\sum_{\{i,j\} \in E^*} |\mu_{i,j} - \mu(\Phi'_\epsilon)_{i^+,j^+}| = O(\epsilon)$ using properties of ML policy to complete the proof. Intuitively, $\lambda'_\epsilon$ is designed in such a way that under any stable policy, all but $O(\epsilon)$ arrivals are matched using edges in $E^+$. So, $\mu(\Phi'_\epsilon)_{i^+,j^+}$ must be close to $\mu_{i,j}$ for all $\{i,j\} \in E^*$.

We start by proving (35). As the $\epsilon$-filtering ML policy mimics the ML policy adapted to $(G', \lambda'_\epsilon)$, we have

$$ \mu(\Phi_{\epsilon}(\mu))_{i,j} = \begin{cases} \mu(\Phi'_{\epsilon})_{i^+,j^-} + \mu(\Phi'_{\epsilon})_{i^-,j^+} + \mu(\Phi'_{\epsilon})_{i^-,j^-} + \mu(\Phi'_{\epsilon})_{i^+,j^+} & \text{if } \{i,j\} \in E^* \\ \mu(\Phi'_{\epsilon})_{i^+,j^-} + \mu(\Phi'_{\epsilon})_{i^-,j^+} + \mu(\Phi'_{\epsilon})_{i^-,j^-} & \text{if } \{i,j\} \in E \setminus E^*, \end{cases} $$

Using the above, we can upper bound our objective $\|\mu - \mu(\Phi_\epsilon)\|_1$ in terms of $\mu(\Phi'_\epsilon)$ as follows:

$$ \begin{align*} \|\mu - \mu(\Phi_{\epsilon})\|_{1} &\stackrel{(a)}{=} \sum_{\{i,j\} \in E^{*}} |\mu_{i,j} - \mu(\Phi_{\epsilon})_{i,j}| + \sum_{\{i,j\} \in E \setminus E^{*}} \mu(\Phi_{\epsilon})_{i,j}, \\ &\stackrel{(b)}{\le} \sum_{\{i,j\} \in E^{*}} |\mu_{i,j} - \mu(\Phi'_{\epsilon})_{i^+,j^+}| + \sum_{\{i,j\} \in E} (\mu(\Phi'_{\epsilon})_{i^+,j^-} + \mu(\Phi'_{\epsilon})_{i^-,j^+} + \mu(\Phi'_{\epsilon})_{i^-,j^-}), \\ &\stackrel{(c)}{\le} \sum_{\{i,j\} \in E^{*}} |\mu_{i,j} - \mu(\Phi'_{\epsilon})_{i^+,j^+}| + 2\epsilon \sum_{j \in V} \lambda_{j}. \end{align*} $$

Here, (a) follows by recalling that $E^*$ is defined as the support of $\mu$. Next, (b) follows as, for all $\{i,j\} \in E^*$,

$$ \begin{aligned} |\mu_{i,j} - \mu(\Phi_{\epsilon})_{i,j}| &= |\mu_{i,j} - \mu(\Phi'_{\epsilon})_{i^+,j^+} - \mu(\Phi'_{\epsilon})_{i^-,j^-} - \mu(\Phi'_{\epsilon})_{i^-,j^+} - \mu(\Phi'_{\epsilon})_{i^+,j^-}|, \\ &\le |\mu_{i,j} - \mu(\Phi'_{\epsilon})_{i^+,j^+}| + \mu(\Phi'_{\epsilon})_{i^+,j^-} + \mu(\Phi'_{\epsilon})_{i^-,j^+} + \mu(\Phi'_{\epsilon})_{i^-,j^-}. \end{aligned} $$

Lastly, (c) follows by noting that

$$ \begin{align*} \sum_{\{i,j\} \in E} (\mu(\Phi'_{\epsilon})_{i^+,j^-} + \mu(\Phi'_{\epsilon})_{i^-,j^-}) &\le \sum_{j \in V} \sum_{\{i,j\} \in E} (\mu(\Phi'_{\epsilon})_{j^-,i^+} + \mu(\Phi'_{\epsilon})_{j^-,i^-}) \stackrel{(*)}{=} \sum_{j \in V} \lambda'_{\epsilon,j^-} = \epsilon \sum_{j \in V} \lambda_j, \\ \sum_{\{i,j\} \in E} \mu(\Phi'_{\epsilon})_{i^-,j^+} &\le \sum_{i \in V} \sum_{\{i,j\} \in E} \mu(\Phi'_{\epsilon})_{i^-,j^+} \stackrel{(*)}{=} \sum_{i \in V} \lambda'_{\epsilon,i^-} = \epsilon \sum_{i \in V} \lambda_i, \end{align*} $$

where (*) follows by applying the conservation equations (CE) to the extended matching model $(G', \lambda'_\epsilon, \Phi'_\epsilon)$. This completes the proof of (35).

Now, we proceed to show that $\sum_{\{i,j\} \in E^*} |\mu_{i,j} - \mu(\Phi'_\epsilon)_{i^+,j^+}| = O(\epsilon)$. Recall that, by Proposition 13, the rows of matrix $A^*$ are linearly independent. This observation has multiple consequences:

- The system of linear equations $A^*y = \lambda$ of unknown $y$ has a unique solution, which we know to be equal to $\mu$.
■ The system of linear equations $A^*y = \tilde{\lambda}$ of unknown $y$ has a unique solution, which we know to be equal to $\tilde{\mu} = \{\mu(\Phi'_\epsilon)_{i+,j+}\}_{\{i,j\}\in E^*}$, where $\tilde{\lambda}$ is given by

$$ \tilde{\lambda}_i = \sum_{\substack{j \in V: \\ \{i,j\} \in E^*}} \mu(\Phi'_\epsilon)_{i+,j+} \quad i \in V. $$

■ The matrix $(A^*)^T A^*$ is invertible, and the Moore-Penrose inverse of $A^*$ is $((A^*)^T A^*)^{-1}(A^*)^T$. Thus, we have $\mu - \tilde{\mu} = ((A^*)^T A^*)^{-1}(A^*)^T(\lambda - \tilde{\lambda})$ which implies

$$ \sum_{\{i,j\} \in E^*} |\mu_{i,j} - \mu(\Phi'_\epsilon)_{i+,j+}| \le \|(A^*)^T A^*)^{-1} (A^*)^T\|_1 \|\lambda - \tilde{\lambda}\|_1. \quad (36) $$

Now, we upperbound the term $\|\lambda - \tilde{\lambda}\|_1$ as follows:

$$
\begin{align*}
\|\lambda - \tilde{\lambda}\|_1 &= \sum_{i \in V} \left| \lambda_i - \sum_{\substack{j \in V: \\ \{i,j\} \in E^*}} \mu(\Phi'_\epsilon)_{i+,j+} \right|, \\
&\le \sum_{i \in V} \left| (1 - \epsilon)\lambda_i - \sum_{\substack{j \in V: \\ \{i,j\} \in E^*}} \mu(\Phi'_\epsilon)_{i+,j+} \right| + \epsilon \sum_{i \in V} \lambda_i, \\
&\stackrel{(a)}{=} \sum_{i \in V} \sum_{\substack{j \in V: \\ \{i,j\} \in E}} \mu(\Phi'_\epsilon)_{i+,j-} + \epsilon \sum_{i \in V} \lambda_i, \\
&\stackrel{(b)}{\le} 2\epsilon \sum_{i \in V} \lambda_i, \tag{37}
\end{align*}
$$

where (a) again follows by applying (CE) to the extended matching model $(G', \lambda'_\epsilon, \Phi'_\epsilon)$, and (b) is justified as follows:

$$ \sum_{i \in V} \sum_{\{i,j\} \in E} \mu(\Phi'_\epsilon)_{i+,j-} \stackrel{(i)}{=} \sum_{j \in V} \sum_{\{i,j\} \in E} \mu(\Phi'_\epsilon)_{i+,j-} \stackrel{(ii)}{\le} \sum_{j \in V} \lambda'_{\epsilon,j-} = \epsilon \sum_{j \in V} \lambda_j. $$

Here, (i) follows by switching the order of summation, and (ii) follows by noting that $\{i^+ \in V^+ : \{i^+, j^-\} \in E^\pm\} \subseteq \{i \in V' : \{i, j\} \in E'\}$ and again applying (CE) to the matching model $(G', \lambda'_\epsilon, \Phi'_\epsilon)$. Now, by combining (37) with (36), we get

$$ \sum_{\{i,j\} \in E^*} |\mu_{i,j} - \mu(\Phi'_\epsilon)_{i+,j+}| \le 2 \|(A^*)^T A^*)^{-1} (A^*)^T\|_1 \sum_{i \in V} \lambda_i \epsilon. $$

Lastly, by injecting the above inequality into (35) and defining

$$ C_2 = 2 \left( 1 + \|(A^*)^T A^*)^{-1} (A^*)^T \right) \sum_{i \in V} \lambda_i, $$

the proof is complete.

<figure><img src="image_71.png" /></figure>
**E Supplementary material of Section 7 (Practical performance).**

**E.1 k-filtering policies – Section 7.1 (Considered policies)**

We conjecture that k-filtering policies, introduced in Section 7.1, yield a sequence of matching rate vectors that are arbitrarily close to a vertex of the polytope $\Pi_{\ge 0}$, even if this vertex is injective-only. This conjecture is supported by numerical results shown in Sections 7 and 8.

**► Conjecture 33.** 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 ML policy adapted to $G$ with filter $E^*$;

- Otherwise, apply the greedy ML 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 as follows: 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 injective-only with a unique connected component, i.e. when $G^*$ is a tree. If $G^*$ is made of multiple connected components that are connected in $G$, 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 ML 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, see [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 ML policy on the graph $G$.

Now, 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 $G^*$. Also let $L_+ = \max\{Q_i, i \in V_+\}$, $L_- = \max\{Q_i, i \in V_-\}$, and $L = L_+ + L_-$. Also let $L_+ = L_- + 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_+$ or $V_-$) to which this queue belongs. The random variable $L$ will play a crucial role in the proof. Lastly, we let $p_\ell = 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 ML 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 ML 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 $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 (29)). We conjecture that, when $|Q_+ - Q_-|$ is large enough (while still satisfying $|L| \le k$), a distinctive structure emerges due to the filtered ML 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 $E^*$ occur only when the size of the longest queue is greater than $k$, we conclude that the matching rate of an edge outside $E^*$ goes to 0, which by continuity of the conservation principle and injectivity of $G^*$ implies that $\lim_{k \to \infty} \mu(\Phi_k(\mu)) = \mu$. ◀

## E.2 Additional examples

Section 7 evaluated the performance of matching policies on the diamond graph. We present here simulations on other graphs. For additional details, please refer to https://balouf.github.io/stochastic_matchring/companion/simulations.html#Vertices-of-simple-graphs

### E.2.1 Co-domino graph

We first consider the matching problem depicted in Figure 19, with the goal of approaching the injective-only vertex shown in Figure 19f. This vertex disables 5 out of 8 edges: $\{1, 2\}$, $\{2, 6\}$, $\{3, 4\}$, $\{3, 5\}$, and $\{5, 6\}$. The results are presented in Figure 21.

As observed in Section 7.3, The best performance is achieved by $\Phi'_\beta$ and $\Phi_k$, while the performance of $\Phi_\beta$ significantly deteriorates under adversarial rewards.

Still focusing on the codomino graph, we now consider the matching problem from Figure 18. Our objective is to approach the bijective vertex illustrated in Figure 18e, which disables the edges $\{2, 3\}$ and $\{4, 5\}$. The results are presented in Figure 22, with a dotted line representing the delay of $\Phi_{E^*}$, which is reward-optimal and stable for bijective vertices.

As seen in Section 7.4, most policies converge to delays at or below that of $\Phi_{E^*}$, with the notable exception of $\Phi_\beta$.

### E.2.2 Larger graph

To observe the performance of our methods on a larger graph, we generated a simple Erdös-Rényi graph with $n = 100$ nodes and an edge probability of $20/(n-1)$, resulting in $m = 1006$ edges. The edge rewards were drawn uniformly and independently.
<figure><img src="image_72.png" /><figcaption>Figure 21 Matching problem from Figure 19. Targeting the injective-only vertex from Figure 19f.</figcaption></figure>

<figure><img src="image_73.png" /><figcaption>Figure 22 Matching problem from Figure 18. Targeting the bijective vertex from Figure 18e.</figcaption></figure>
<figure><img src="image_74.png" /><figcaption>(a) Injective-only vertex (degree-proportional arrivals). (b) Bijective vertex (perturbated degree-proportional arrivals).</figcaption></figure>

<caption>■ **Figure 23** Reaching a vertex on a larger graph ($n = 100, m = 1006$).</caption>

We aimed to study both an injective-only vertex and a bijective vertex. On graphs of this size, computing the exhaustive list of vertices is unrealistic, but once the reward and arrival-rate vectors are given, calculating the corresponding optimal vertex is straightforward.

To obtain an injective-only vertex, we used degree-proportional arrival rates, following the discussion in Section 5.2.2. This ensured the problem was stabilizable and, in this case, resulted in an optimal vertex with 97 positive edges (injective-only). For the bijective vertex, we added a noisy perturbation to the degree-proportional arrival rates, yielding a bijective vertex, as hinted by Proposition 14.

The performance results for both cases are presented in Figure 23. A key observation is that $\Phi_{\alpha}$ performs significantly better in this scenario compared to what was observed on smaller graphs with lower-dimensional $\Pi_{\ge 0}$.
# F Supplementary material of Section 8 (Extensions of our results).

## F.1 Convexity proofs for $\Pi_P$ and $\Pi_G$ (Propositions 20 and 21).

We consider the extended definition of matching policies, as discussed in Appendix A. 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 selecting each policy after visiting the empty state will be set to achieve the desired matching rate vector in 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$.

- Empty state: $\emptyset_\beta = (\emptyset_1, \emptyset_2)$.

For some $0 < \gamma_\beta < 1$ that will be specified later, the matching policy $\Phi_\beta$ is defined as follows:

$$ \Phi_{\beta}((\emptyset_1, \emptyset_2), i, j, (s_1, \emptyset_2)) = \gamma_{\beta}\Phi_1(\emptyset_1, i, j, s_1), \quad s_1 \in S_1, \quad i \in V, \quad j \in V \cup \{\emptyset\}, $$

$$ \Phi_{\beta}((\emptyset_1, \emptyset_2), i, j, (\emptyset_1, s_2)) = (1 - \gamma_{\beta})\Phi_2(\emptyset_2, i, j, s_2), \quad s_2 \in S_2, \quad i \in V, \quad j \in V \cup \{\emptyset\}, $$

$$ \Phi_{\beta}((s_1, \emptyset_2), i, j, (s'_1, \emptyset_2)) = \Phi_1(s_1, i, j, s'_1), \quad s_1 \in S_1 \setminus \{\emptyset_1\}, \quad s'_1 \in S_1, $$

$$ \Phi_{\beta}((\emptyset_1, s_2), i, j, (\emptyset_1, s'_2)) = \Phi_2(s_2, i, j, s'_2), \quad s_2 \in S_2 \setminus \{\emptyset_2\}, \quad s'_2 \in S_2. $$

The first two equations say that, when the system is empty, we next apply $\Phi_1$ with probability $\gamma_\beta$ and $\Phi_2$ with probability $1 - \gamma_\beta$. The third (resp. fourth) equation says that, once we start applying policy $\Phi_1$ (resp. $\Phi_2$), we keep applying this policy until we re-visit the empty state.

The stability of the policies $\Phi_1$ and $\Phi_2$ implies that of the policy $\Phi_\beta$. According to the elementary renewal theorem for renewal reward processes, the vector giving the long-run average matching rates under the policy $\Phi_\beta$ is given by

$$ \mu(\Phi_{\beta}) = \frac{\gamma_{\beta}T_{1}\mu(\Phi_{1}) + (1 - \gamma_{\beta})T_{2}\mu(\Phi_{2})}{\gamma_{\beta}T_{1} + (1 - \gamma_{\beta})T_{2}} = \frac{\gamma_{\beta}T_{1}}{\gamma_{\beta}T_{1} + (1 - \gamma_{\beta})T_{2}}\mu(\Phi_{1}) + \frac{(1 - \gamma_{\beta})T_{2}}{\gamma_{\beta}T_{1} + (1 - \gamma_{\beta})T_{2}}\mu(\Phi_{2}). $$

where $T_1$ (resp. $T_2$) denotes the mean number of matches between two successive visits to the empty state $\emptyset_1$ (resp. $\emptyset_2$) in the matching model $(G, \lambda, \Phi_1)$ (resp. $(G, \lambda, \Phi_2)$). We let the reader verify that the following value of $\gamma_\beta$ yields $\mu(\Phi_\beta) = \beta\mu(\Phi_1) + (1-\beta)\mu(\Phi_2)$:

$$ \gamma_{\beta} = \frac{\beta T_2}{(1 - \beta)T_1 + \beta T_2}. $$

**Convexity of $\Pi_G$.** It suffices to observe that, if the policies $\Phi_1$ and $\Phi_2$ are greedy, so is the policy $\Phi_\beta$.
## F.2 Supplementary material of Section 8.2 (Greedy policies).

### F.2.1 Proof of Proposition 23 (complete graphs) and discussion.

Consider a matching problem $(K_n, \lambda)$, where $K_n$ is the complete graph with $n \ge 3$ nodes. According to Proposition 8, 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$. We prove Proposition 23 by first demonstrating that all greedy policies are “equivalent”, in the sense that they always (deterministically) make the same matching decisions. The fact that we can formally define many greedy policies in this context is merely an artifact of our extended definition of a matching policy in Appendix A (see in particular Appendix A.2).

Notice that 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 (38)$$

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 leaves no freedom in the 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 is formalized in Proposition 34.

**Proposition 34.** 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 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} \quad (39)$$

(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 Appendix A).

(iii) For each greedy policy $\Phi$ adapted to the graph $K_n$ and each sequence $I = (I_t, t \in \mathbb{N})$ 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.** We prove each statement one by one.

**Proposition 34i.** Consider a (possibly random) size-based greedy policy $\Phi: Q_G(K_n) \times V \times (V \cup \{\perp\}) \to [0, 1]$, as defined in Section 2.3.4, where $Q_G(K_n)$ is given in (38). Given $(q, i) \in Q_G(K_n) \times V$, the definition of $Q_G(K_n)$ implies that $\{j \in V_i : q_j \ge 1\}$ is either a singleton or the empty set. In the former case, letting $j$ denote the unique element of the singleton, we have $\Phi(q, i, \perp) = 1$ if $i = j$, while the greediness of $\Phi$ implies that $\Phi(q, i, j) = 1$ if $i \ne j$. In the latter case, we have directly $\Phi(q, i, \perp) = 1$. In all cases, the matching decision is deterministic and makes the same decisions as in (39).
**Proposition 34ii.** The same argument can be repeated for an arbitrary greedy policy $\Phi$ with state space $(S, |\cdot|)$. Given $(s, i) \in S \times V$, we know that $|s| \in Q_G(K_n)$, so that $\{j \in V_i : |s|_j \ge 1\}$ is either a singleton or the empty set. In the former case, letting $j$ denote the unique element of the singleton, we have $\sum_{s' \in S} \Phi(s, i, \perp, s') = 1$ if $i = j$, while the greediness of $\Phi$ implies that $\sum_{s' \in S} \Phi(s, i, j, s') = 1$ if $i \ne j$. In the latter case, we have directly $\sum_{s' \in S} \Phi(s, i, \perp, s') = 1$. In all cases, we have $\sum_{s' \in S} \Phi(s, i, \Phi_G(|s|, i), s') = 1$.

**Proposition 34iii.** This statement follows directly from Proposition 34ii and from the fact that, under any matching policy, the dynamics of the queue-size process is fully specified by the sequence of incoming item classes and the matching decisions via (2). ◀

Proposition 35 below, which encompasses Proposition 23, builds on this equivalence 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 35.** 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$. Then:

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

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

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

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

**Proof.** We prove each statement one by one.

**Proposition 35i.** Proposition 35i is a consequence of Corollary 27i (Appendix B.3).

**Proposition 35ii.** We can focus without loss of generality on the FCFM policy, as Proposition 34iii implies that all greedy matching policies yield the same vector of matching rates. Equation (40) follows by observing that, for each edge $e_k = \{i, j\} \in E$, a match between classes $i$ and $j$ happens if:

- a class-$i$ item arrives while queue $j$ is non-empty, which happens at rate $\lambda_i p_j$;

- a class-$j$ item arrives while queue $i$ is non-empty, which happens at rate $\lambda_j p_i$.

Equations (41) and (42) follow from [16, Proposition 5]. Indeed, for each $i \in V$, applying [16, Equation (10)] to the independent set $\{i\}$ yields (41), and the value of $p_{\emptyset}$ given in (42) follows from the normalizing equation. This result may also be obtained more directly by observing that, for each $i \in V$, the restriction of the transition diagram of the Markov chain $(K_n, \lambda, \Phi_G)$ to the states where all queues but queue $i$ are empty is similar to a (discrete-time) birth-and-death process with birth probability $\lambda_i$ and death probability $\sum_{j \neq i} \lambda_j$. ◀
<figure><img src="image_75.png" /><figcaption>(a) Generic solution to (CE).</figcaption></figure>

<figure><img src="image_76.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 24 Matching problem ($K_4$, $\lambda$) with $\lambda = (3, 3, 3, 3)$.

Figure 24 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 24a. 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 35 shows that only the solution $\alpha = (0, 0)$ can be achieved by a greedy policy.

## F.2.2 Proof of Proposition 24 (diamond graph) and discussion.

Consider the diamond (double fan) graph introduced in Example 4, for which we will show that the set $\Pi_G$ of matching rate vectors achieved by stable greedy policies is a strict subset of the set $\Pi_{>0}$ of positive solution to (CE). 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{43} \\
\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,3}$ for each $\mu \in \Pi$) is a notational convenience that does not lead to any loss of generality: as already observed in Example 4, 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 (43) implies in particular that the sets $\Pi_{\ge 0}$ and $\Pi_{>0}$, are real intervals, and so are $\Pi_P$ and $\Pi_G$ by convexity.

As in Appendix F.2.1, we first provide an equivalence result that will be useful to describe $\Pi_G$ in details.

### Equivalence of greedy policies

As in Appendix F.2.1, we first identify a common behavior shared by all greedy policies and then we exploit this behavior to characterize the matching rates achievable by stable greedy policies.

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

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, we prove formally in Proposition 36 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 36.** 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 (39) 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_{\substack{j \in V \\ \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})$.

Loosely speaking, the main take-away of Proposition 36iii 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$.

**Proof of Proposition 36.** We prove each statement one by one.

**Proposition 36i.** We leave it to the reader to verify that $Q_G(K_3)$ is the image of $Q_G(D)$ by the application $q = (q_1, q_2, q_3, q_4) \mapsto \langle q \rangle = (q_1 + q_4, q_2, q_3)$. This means in particular that $q_1 + q_4, q_2$, and $q_3$ cannot be positive simultaneously if $q \in Q_G(D)$. Since the diamond graph $D$ has only four nodes, we can then conclude by enumerating all relevant cases, depending on the support of $\langle q \rangle = (q_1 + q_4, q_2, q_3)$. For example, if $q_1 + q_4 \ge 1$ and $q_2 = q_3 = 0$, then we have immediately $\Phi(q, i) = \perp$ if $i \in \{1, 4\}$, and the greediness of the policy $\Phi$ implies that $\Phi(q, i) \in \{1, 4\}$ if $i \in \{2, 3\}$; in other words, we have $\langle \Phi(q, i) \rangle = \perp$ if $\langle i \rangle = 1$ and $\langle \Phi(q, i) \rangle = 1$ if $\langle i \rangle \in \{2, 3\}$. Similarly, if $q_1 + q_4 = q_3 = 0$ and $q_2 \ge 1$, then $\Phi(q, i) = \perp$ if $i = 2$ and $\Phi(q, i) = 2$ if $i \in \{1, 3, 4\}$, that is, $\langle \Phi(q, i) \rangle = \perp$ if $\langle i \rangle = 2$ and $\langle \Phi(q, i) \rangle = 2$ if $\langle i \rangle \in \{1, 3\}$. In all cases, we can verify that $\langle \Phi(q, i) \rangle$ is equal to $\Phi_G(K_3)(\langle q \rangle, \langle i \rangle)$.

Alternatively, by taking a step back, we can prove Proposition 36i more directly by observing that, for each $(q, i) \in Q_G(D) \times V$, (i) the support of $\langle q \rangle$ is a singleton $\{j\}$ whenever $q \ne 0$, and (ii) whether $j \in V_i$ depends on $i$ only via $\langle i \rangle$.
**Proposition 36ii.** The same argument can be repeated for an arbitrary greedy policy $\Phi$ with state space $(S, |\cdot|)$. As in the proof of Proposition 34ii, the key argument consists of observing that we still have $q = |s| \in Q_G(D)$ for each $(s, i) \in S \times V$, so that $q_1 + q_4$, $q_2$, and $q_3$ cannot be positive simultaneously.

**Proposition 36iii.** The conclusion follows in much the same way as in the proof of Proposition 34iii, by injecting statements i and ii from Proposition 36 into (2). ◀

### Matching rates under stable greedy policies.

Propositions 37 and 38, which encompass Proposition 24, use the equivalence result of Proposition 36 to characterize the matching rate vector under stable greedy policies. Proposition 37 bounds the coordinates of the matching-rate vectors achievable by a stable greedy policy, while Proposition 38 details the bounds $\alpha_+$ and $\alpha_-$ of $\Pi_G$. These propositions illustrate the complementarity of edge and kernel coordinates: the results of Proposition 37 are easier to state using edge coordinates, while those of Proposition 38 are easier to state using kernel coordinates. The lower bound (45) is obtained by following a similar approach as in Proposition 35ii.

**Proposition 37 (Edge coordinates).** Consider the matching model $(D, \lambda, \Phi)$, where $(D, \lambda)$ is the diamond problem (43) 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, \quad \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{45} $$

where $p_i$ is the stationary probability that the system contains unmatched items that belong exclusively to class $i$, for each $i \in V$.

(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

$$ p_2 = \frac{\lambda_2}{\lambda_1 + \lambda_3 + \lambda_4 - \lambda_2} p_\emptyset, \quad p_3 = \frac{\lambda_3}{\lambda_1 + \lambda_2 + \lambda_4 - \lambda_3} p_\emptyset, \quad p_{1,4} = \frac{\lambda_1 + \lambda_4}{\lambda_2 + \lambda_3 - \lambda_1 - \lambda_4} p_\emptyset, \tag{46} $$

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. \tag{47} $$

**Proof of Proposition 37.** We prove each statement one after another.

**Proposition 37i.** This is a consequence of Corollary 27ii (Appendix B.3).

**Proposition 37ii.** The equation $\mu_{2,3} = \beta = \frac{1}{2}(\lambda_2 + \lambda_3 - \lambda_1 - \lambda_4)$ is a direct consequence of (CE). The inequalities (45) for $\mu_{1,2}$, $\mu_{1,3}$, $\mu_{2,4}$, and $\mu_{3,4}$ follow by observing that, for each edge $\{i, j\} \in \{\{1, 2\}, \{1, 4\}, \{2, 3\}, \{3, 4\}\}$, a match between classes $i$ and $j$ happens at least in one of the following cases:

- a class-i item arrives while the system contains unmatched items that all belong to class $j$,

- a class-j item arrives while the system contains unmatched items that all belong to class $i$, These events occur at rates $\lambda_i p_j$ and $\lambda_j p_i$, respectively. Equations (45) are not equalities in general because the above list is not exhaustive. For example, depending on the greedy
policy, a match between classes 1 and 2 may happen if a class-2 item arrives while the system contains unmatched items of class 1 and unmatched items of class 4.

**Proposition 37iii.** The expressions for $p_\emptyset$, $p_2$, $p_3$, and $p_{1,4}$ follow directly by combining Proposition 36iii with Equations (41) and (42) in Proposition 35. We now derive the lower bound (47) for $p_1$. The one for $p_4$ follows by symmetry.

First assume that the greedy policy $\Phi$ is deterministic and size-based, so that it satisfies Proposition 36i. For each $q \in Q_G(D)$, let $\pi_q$ denote the probability that the Markov chain $(D, \lambda, \Phi)$ is in state $q$ in stationary regime. The probability that we want to lower-bound is

$$p_1 = \sum_{\ell=1}^{+\infty} \pi_{\ell 1_1}. \qquad (48)$$

Now let $\ell \in \mathbb{N}_{>0}$ and consider the balance equation for state $\ell 1_1$, given by

$$(\lambda_1 + \lambda_2 + \lambda_3 + \lambda_4)\pi_{\ell 1_1} = \lambda_1\pi_{(\ell-1)1_1} + (\lambda_2 + \lambda_3)\pi_{(\ell+1)1_1} + C, \qquad (49)$$

where $C$ is a non-negative real that depends on the model parameters, the integer $\ell$, and the policy $\Phi$, and that accounts for the flow to state $\ell 1_1$ from state $\ell 1_1 + 1_4$, if any. It follows that $(\lambda_1 + \lambda_2 + \lambda_3 + \lambda_4)\pi_{\ell 1_1} > \lambda_1\pi_{(\ell-1)1_1}$. An inductive argument allows us to conclude that

$$\pi_{\ell 1_1} > \left( \frac{\lambda_1}{\lambda_1 + \lambda_2 + \lambda_3 + \lambda_4} \right)^{\ell} p_{\emptyset}, \quad \ell \in \mathbb{N}_{>0}. \qquad (50)$$

Injecting this inequality into (48) allows us to conclude:

$$p_1 > \sum_{\ell=1}^{+\infty} \left( \frac{\lambda_1}{\lambda_1 + \lambda_2 + \lambda_3 + \lambda_4} \right)^{\ell} p_{\emptyset} = \frac{\lambda_1}{\lambda_2 + \lambda_3 + \lambda_4} p_{\emptyset}. \qquad (51)$$

If $\Phi$ is an extended policy with state space $(S, |\cdot|)$, we can still write (48)–(51) and reach the same conclusion. The only difference is that $\pi$ can no longer be defined as the stationary distribution of a Markov chain: instead, we define $\pi_q = \sum_{s \in S: |s|=q} \pi_s$ for each $q \in Q_G(D)$, where $\pi_s$ is the probability that the Markov chain $(D, \lambda, \Phi)$ is in state $s$ in stationary regime, for each $s \in S$. ◀

**► Proposition 38 (Kernel coordinates).** Consider the diamond matching problem $(D, \lambda)$ of (43).

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

$$\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_{+}],$$

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 Highest-Reward-First (HRF) policy adapted to the graph $D$ whereby edges $\{1, 2\}$ and $\{3, 4\}$ have the highest reward.

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

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 of Proposition 38.** We prove each statement one after another.

**Proposition 38i–iia–iib.** The diamond graph $D$ has $n = 4$ nodes and $m = 5$ edges. Therefore, according to Propositions 10 and 21, the sets $\Pi_{\ge 0}$, $\Pi_{>0}$, and $\Pi_G$ have dimension $d = m - n = 1$, meaning that they are intervals in $\mathbb{R}$. The equations for the intervals $\Pi_{\ge 0}$ and $\Pi_{>0}$ follow directly from the change-of-basis equation $\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)$ from (43). That $\Pi_G$ is also an interval is a consequence of its convexity (Proposition 21). The (non-strict) inequality $-2\min(\lambda_1\bar{\lambda}_2, \bar{\lambda}_3\lambda_4) \le \alpha_+ \le 2\min(\lambda_1\bar{\lambda}_3, \bar{\lambda}_2\lambda_4)$ is a consequence of Proposition 21, which states that $\Pi_G \subseteq \Pi_{>0}$. The first and third inequalities are also strict because $\alpha_+$ and $\alpha_-$ belong to $\Pi_G$ (see below), while $2\min(\lambda_1\bar{\lambda}_3, \bar{\lambda}_2\lambda_4)$ and $-2\min(\lambda_1\bar{\lambda}_2, \bar{\lambda}_3\lambda_4)$ do not belong to $\Pi_{>0}$. That $\Pi_G$ is a closed interval of the form $\Pi_G = [\alpha_-, \alpha_+]$ and that $\alpha_+$ and $\alpha_-$ are as given in Proposition 38iia–iib are consequences of Lemma 39 below, which will be proved by a coupling argument later in this appendix$^{21}$.

**► Lemma 39.** Consider the HRF policy $\Phi_+$ adapted to the diamond graph $D$ whereby edges $\{1,2\}$ and $\{3,4\}$ have the highest reward. For each greedy policy $\Phi$ adapted to the compatibility graph $D$, we have

$$ \mu_{1,2}(\Phi) \le \mu_{1,2}(\Phi_+), \quad \mu_{3,4}(\Phi) \le \mu_{3,4}(\Phi_+), \\ \mu_{1,3}(\Phi) \ge \mu_{1,3}(\Phi_+), \quad \mu_{2,4}(\Phi) \ge \mu_{2,4}(\Phi_+), \tag{52} $$

Equivalently, in kernel coordinates, we have $\alpha(\Phi) \le \alpha(\Phi_+)$.

**Proposition 38iic.** Most of the quantities we consider in this proof are functions of $\beta$, but this dependency is left implicit to simplify notation. In particular, we let $\mu$ denote (the edge coordinates of) the matching rate vector in the matching model $(D, \lambda, \Phi_+)$, where $\lambda = (\lambda_1, \bar{\lambda}_2 + \beta, \bar{\lambda}_3 + \beta, \lambda_4)$, with $\lambda_1 + \lambda_4 = \bar{\lambda}_2 + \bar{\lambda}_3 = \frac{1}{2}$, and $\Phi_+$ is the greedy HRF policy defined in Lemma 39. By combining (45) with the conservation equation $\mu_{1,2} + \mu_{1,3} = \lambda_1$, we obtain the following lower and upper bounds for $\mu_{1,2}$:

$$ \lambda_1 p_2 + \lambda_2 p_1 \le \mu_{1,2} \le \lambda_1 - (\lambda_1 p_3 + \lambda_3 p_1). \tag{53} $$

In addition, injecting the definition (43) of $\lambda$ into (46) and (47) shows that, in the model $(D, \lambda, \Phi_+)$, we have

$$ \begin{array}{lll} p_2 = p_{\emptyset} \frac{\bar{\lambda}_2 + \beta}{2\bar{\lambda}_3}, & p_3 = p_{\emptyset} \frac{\bar{\lambda}_3 + \beta}{2\bar{\lambda}_2}, & p_{1,4} = p_{\emptyset} \frac{1}{3\beta}, \\ p_1 > p_{\emptyset} \frac{\lambda_1}{\frac{1}{2} + \lambda_4 + 2\beta}, & p_4 > p_{\emptyset} \frac{\lambda_4}{\frac{1}{2} + \lambda_1 + 2\beta}, & \end{array} \tag{54} $$

with, by the normalization equation $p_{\emptyset} + p_2 + p_3 + p_{1,4} = 1$,

$$ p_{\emptyset} = \left( 1 + \frac{1}{3\beta} + \frac{\bar{\lambda}_2 + \beta}{2\bar{\lambda}_3} + \frac{\bar{\lambda}_3 + \beta}{2\bar{\lambda}_2} \right)^{-1}. \tag{55} $$

Taking the limit of (54) and (55) as $\beta \to +\infty$, we conclude that both the lower-bound and the upper-bound in (53) tend to $2\lambda_1\bar{\lambda}_2$ as $\beta \to +\infty$. Then combining (53) with the squeeze theorem allows us to conclude that $\mu_{1,2}$ also tends to $2\lambda_1\bar{\lambda}_2$ as $\beta \to +\infty$. By symmetry, we

<footnote>$^{21}$Lemma 39 focuses on Proposition 38iia. The case Proposition 38iib is trivially deduced by switching the class labels 2 and 3.</footnote>
obtain directly $\mu_{1,3} \to 2\lambda_1\bar{\lambda}_3$, $\mu_{2,4} \to 2\bar{\lambda}_2\lambda_4$, and $\mu_{3,4} \to 2\bar{\lambda}_3\lambda_4$ as $\beta \to +\infty$. According to the change-of-basis equation $\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)$ from (43), this means that $\alpha_+ \to 0$ as $\beta \to +\infty$. ◀

**Proof of Lemma 39.** Consider a greedy policy $\Phi$ adapted to the graph $D$. We will prove the inequality relations in (52) using a coupling argument. More specifically, we will compare the matching models $(D, I, \Phi)$ and $(D, I, \Phi_+)$, where $I = (I_t, t \in \mathbb{N})$ is a sequence of i.i.d. classes, such that $I_t = i$ with probability $\lambda_i/(\lambda_1 + \lambda_2 + \lambda_4 + \lambda_3)$ for each $t \in \mathbb{N}$ and $i \in V$.

Considering the model $(D, I, \Phi)$, we let $Q_t$ denote the vector of queue sizes at time $t$, $L_{t,i}$ the number of class-i items among the first $t$ arrivals, and $M_{t,\{i,j\}}$ (or $M_{t,i,j}$ for short) the number of times that classes $i$ and $j$ are matched over the first $t$ arrivals, for each $t \in \mathbb{N}$ and $i, j \in V$, as defined in (2)-(5). We introduce similar notation for the model $(D, I, \Phi^+)$, the only difference being that all quantities have superscript $+$. Since both models have the same sequence of incoming items, we have $L_{t,i} = L_{t,i}^+$ for each $t \in \mathbb{N}$ and $i \in V$. As usual, we also assume that $Q_0 = Q_0^+ = 0$. Neither $(Q_t, t \in \mathbb{N})$ nor $(Q_t^+, t \in \mathbb{N})$ need to be Markov chains for our argument to hold.

Our end goal is to prove that the following inequalities are satisfied at each time $t \in \mathbb{N}$:

$$M_{t,1,2} \le M_{t,1,2}^+, \qquad (56-1,2)$$

$$M_{t,3,4} \le M_{t,3,4}^+, \qquad (56-3,4)$$

$$M_{t,1,3} \ge M_{t,1,3}^+, \qquad (56-1,3)$$

$$M_{t,2,4} \ge M_{t,2,4}^+, \qquad (56-2,4)$$

Injecting these inequalities into the definition (8) of the matching rates yields the inequalities (52). We will prove (56) by induction over time $t \in \mathbb{N}$. The following equations will be instrumental to prove the induction step:

$$Q_{t,1} + Q_{t,4} = Q_{t,1}^+ + Q_{t,4}^+, \quad Q_{t,2} = Q_{t,2}^+, \quad Q_{t,3} = Q_{t,3}^+, \qquad (57)$$

$$L_{t,1} = Q_{t,1} + M_{t,1,2} + M_{t,1,3} = Q_{t,1}^+ + M_{t,1,2}^+ + M_{t,1,3}^+, \qquad (58)$$

$$L_{4,t} = Q_{t,4} + M_{t,2,4} + M_{t,3,4} = Q_{t,4}^+ + M_{t,2,4}^+ + M_{t,3,4}^+. \qquad (59)$$

Equation (57) follows from Proposition 36iii, while (58) and (59) follow from our assumption that the arrivals in both models are coupled. Furthermore, given the definition of $Q_G(D)$ in (44), we know that only one integer among $Q_{t,1} + Q_{t,4}$, $Q_{t,2}$, and $Q_{t,3}$ can be positive, for each $t \in \mathbb{N}$.

We now proceed to the induction step. Let $t \in \mathbb{N}$. We now prove that, assuming that the inequalities (56) are satisfied at time $t$, these inequalities are also satisfied at time $t+1$. We distinguish several cases depending on the value of $I_t$:

**Case $I_t = 1$:** We have directly $M_{t+1,i,j} = M_{t,i,j}$ and $M_{t+1,i,j}^+ = M_{t,i,j}^+$ for $(i, j) \in \{(2, 4), (3, 4)\}$, hence the induction assumption implies that (56-2,4) and (56-3,4) hold at time $t+1$. Since the policy $\Phi$ is greedy, we only have three mutually-exclusive cases:

**Case $Q_{t,2} \ge 1$:** The class-1 item is matched with a class-2 item already present, and we obtain $M_{t+1,1,2} = M_{t,1,2} + 1$ and $M_{t+1,1,3} = M_{t,1,3}$.

**Case $Q_{t,3} \ge 1$:** The class-1 item is matched with a class-3 item already present, and we obtain $M_{t+1,1,2} = M_{t,1,2}$ and $M_{t+1,1,3} = M_{t,1,3} + 1$.

**Case $Q_{t,2} = Q_{t,3} = 0$:** The class-1 item is left unmatched, and we obtain $M_{t+1,1,2} = M_{t,1,2}$ and $M_{t+1,1,3} = M_{t,1,3}$.
Since the policy $\Phi^+$ is also greedy, we can repeat the same argument for the quantities associated with $\Phi^+$. Combining this observation with (57) yields $M_{t+1,1,2} - M_{t+1,1,2}^+ = M_{t,1,2} - M_{t,1,2}^+$ and $M_{t+1,1,3} - M_{t+1,1,3}^+ = M_{t,1,3} - M_{t,1,3}^+$. Hence, the induction assumption implies directly that (56-1,2) and (56-1,3) are satisfied at time $t+1$.

**Case $I_t = 2$:** We have directly $M_{t+1,i,j} = M_{t,i,j}$ and $M_{t+1,i,j}^+ = M_{t,i,j}^+$ for $(i,j) \in \{(1,3), (3,4)\}$, hence the induction assumption implies that (56-1,3) and (56-3,4) hold at time $t+1$. Proving that (56-1,2) and (56-2,4) also hold at time $t+1$ is more intricate, and we will distinguish three mutually-exclusive cases depending on the values of $Q_{t,1}$, $Q_{t,4}$, $Q_{t,1}^+$, and $Q_{t,4}^+$:

**Case $Q_{t,1}^+ + Q_{t,4}^+ = 0$:** Under both policies, the class-2 item is either matched with a class-3 item or added to the queue. In particular, we obtain $M_{t+1,i,j} = M_{t,i,j}$ and $M_{t+1,i,j}^+ = M_{t,i,j}^+$ for $(i,j) \in \{(1,2), (2,4)\}$, so that (56-1,2) and (56-2,4) are again satisfied at time $t+1$ thanks to the induction assumption.

**Case $Q_{t,1}^+ + Q_{t,4}^+ \ge 1$:** We again subdivide this case into three mutually-exclusive cases:

**Case $Q_{t,1}^+ \ge 1$ and $Q_{t,4}^+ \ge 1$:** We have $M_{t+1,1,2}^+ = M_{t,1,2}^+ + 1$ and $M_{t+1,2,4}^+ = M_{t,2,4}^+$ by definition of the policy $\Phi^+$, while for the policy $\Phi$ we only know that $M_{t+1,1,2} \in \{M_{t,1,2}, M_{t,1,2} + 1\}$ and $M_{t+1,2,4} \in \{M_{t,2,4}, M_{t,2,4} + 1\}$. We can verify that (56-1,2) and (56-2,4) hold at time $t+1$ thanks to the induction assumption.

**Case $Q_{t,1}^+ = 0$ and $Q_{t,4}^+ \ge 1$:** By greediness, the policy $\Phi^+$ matches the incoming class-2 item with a class-4 item, and we obtain $M_{t+1,1,2}^+ = M_{t,1,2}^+$ and $M_{t+1,2,4}^+ = M_{t,2,4}^+ + 1$. If the policy $\Phi$ makes the same decision, then we also have $M_{t+1,1,2} = M_{t,1,2}$ and $M_{t+1,2,4} = M_{t,2,4} + 1$, hence (56-1,2) and (56-2,4) hold at time $t+1$ thanks to the induction assumption. Otherwise, the policy $\Phi$ matches the class-2 item with a class-1 item, meaning that $M_{t+1,1,2} = M_{t,1,2} + 1$ and $M_{t+1,2,4} = M_{t,2,4}$. Importantly, this is only possible if $Q_{t,1} \ge 1$. We now prove (56-1,2) and (56-2,4) as follows:

- Proving (56-1,2) boils down to proving $M_{t,1,2}^+ \ge M_{t,1,2} + 1$. We have successively:

$$M_{t,1,2}^+ - M_{t,1,2} = (Q_{t,1} - Q_{t,1}^+) + (M_{t,1,3} - M_{t,1,3}^+) \ge 1 + 0 = 1,$$

where the equality follows from (58) and the inequality follows from the induction assumption and the fact that $Q_{t,1} \ge 1$ and $Q_{t,1}^+ = 0$.

- Proving (56-2,4) boils down to proving $M_{t,2,4}^+ + 1 \le M_{t,2,4}$. We have successively:

$$M_{t,2,4} - M_{t,2,4}^+ = (Q_{t,4}^+ - Q_{t,4}) + (M_{t,3,4}^+ - M_{t,3,4}) \ge 1 + 0 = 1,$$

where the equality follows from (59) and the inequality follows from the induction assumption and the observation that $Q_{t,4}^+ - Q_{t,4} = Q_{t,1} - Q_{t,1}^+ \ge 1$.

Intuitively, the only way that an incoming class-2 item is matched at time $t$ with a class-1 item under the policy $\Phi$ and with a class-4 item under the policy $\Phi^+$ is if, in the past, the policy $\Phi^+$ had made one more match along edge $\{1,2\}$ and one less match along edge $\{2,4\}$ compared to the policy $\Phi$.

**Case $Q_{t,1}^+ \ge 1$ and $Q_{t,4}^+ = 0$:** This case is symmetrical to the previous case.

**Case $I_t = 3$:** This case is symmetrical to the case $I_t = 2$.

**Case $I_t = 4$:** This case is symmetrical to the case $I_t = 1$.

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

Proposition 38 can be interpreted as follows. Intuitively, the kernel coordinate $\alpha$ given in (43) (also shown in Figure 3d) 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\}$ on the long run. Remarkably,
Proposition 38 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 edges the most in the short run. This result is proved by a coupling argument. In addition, Proposition 38 uses the lower bound (45) in Proposition 37 to prove that, in the limit as $\beta \to +\infty$, all greedy policies yield the same matching rate vector.

Taken together, Statements i and iic in Proposition 38 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 (43) 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 38iic, this intuition is formalized by taking the limit of (46) as $\beta \to +\infty$, which yields $p_0 \to 0$, $p_2 \to 2\bar{\lambda}_2$, $p_3 \to 2\bar{\lambda}_3$, and $p_{1,4} \to 0$. 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 11.** Some quantities in Proposition 38 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.

To illustrate Proposition 38, Figure 25 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 (45)–(47) (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¹⁰ steps (as specified in Section 7). As announced by Proposition 38, $\Pi_G$ becomes reduced to a single point $\alpha = 0$ when $\beta \to +\infty$. We also notice that the bounds (45)–(47) 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 (45)–(47) comes from the fact that, to obtain the lower bounds for $p_1$ and $p_4$ in (47), 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.

## F.2.3 Intuition of Conjecture 25 (fish matching problem) and discussion.

We consider a matching problem, which we call the Fish problem, where we conjecture 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\}, \{3, 6\}, \{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{60}
\end{align}
$$
<figure><img src="image_78.png" /><figcaption>■ **Figure 25** Evolution of $\Pi_G$ as a function of $\beta$ in the diamond problem (43) 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>

The general solution $\mu$ given in (60) is shown in Figure 12. 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. 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\}$.

<figure><img src="image_79.png" /><figcaption>■ **Figure 12 (repeated)** Generic solution to (CE) in the Fish matching problem of (60) with $\lambda = (4, 4, 3, 2, 3, 2)$.</figcaption></figure>

To support Conjecture 25, 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 21). 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 HRF policy where edges have the following decreasing reward order: $\{1, 3\}$, $\{2, 3\}$, $\{3, 4\}$, $\{5, 6\}$, followed by all other edges in an arbitrary order. Let $\Phi_0^+$ denote the HRF policy where edges have the following decreasing reward 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 leads to a high $\alpha$), but that $\Phi_\infty^+$ gives higher priority to the “tail” of the fish, 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 (60), $\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,
<figure><img src="image_80.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_81.png" /><figcaption>(b) Policy $\Phi_{0}^{+}$, followed by policy $\Phi_{k}^{+}$ when the size of queue 4 is at least $k$</figcaption></figure>

Figure 26 HRF (greedy) policies considered in the Fish matching problem of (60).

$\alpha = \frac{1}{2}$ can be achieved by merely applying the edge-filtering variant of ML (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 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. Stability can be proved by applying a fluid-limit argument that generalizes the framework of [19] $^{22}$. 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) \le (\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.

<footnote>$^{22}$Formalizing this generalization is outside the scope of this paper and could be the topic of a future work.</footnote>
<figure><img src="image_82.png" /><figcaption>■ Figure 27 Approaching the vertex $\alpha = 1/2$ in the Fish graph from Figure 12 with greedy policies ($r = (2, 2, 2, 1, -1, 0, 1)$).</figcaption></figure>

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} \le k - 1$, is upperbounded by

$$ \lambda_3 \left( 1 + \frac{\lambda_1}{\lambda_2 + \lambda_3 - \lambda_1} + \frac{\lambda_2}{\lambda_1 + \lambda_3 - \lambda_2} \right)^{-1} = \frac{9}{11}. $$

This upper bound 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.

- Using this upper bound, 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.

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

## Numerical results.

The performance of $\Phi_k^+$ is shown in Figure 27. Since the vertex at $\alpha = 1/2$ is bijective, we include the delay of the reward-optimal policy $\Phi_{E^*}$ for comparison. The figure corroborates Conjecture 25, demonstrating that the regret of $\Phi_k^+$ converges to zero. However, as mentioned earlier, this reduction in regret comes at the cost of increasing the size of the class-4 queue, thus increasing the delay of the policy.