Online Stochastic Matchings: Stability on Hypergraphs Fabien Mathieu # Ñ Swapcard, Paris, France Sorbonne Université, CNRS, LIP6, Paris, France
arXiv:2607.18935v1 [cs.NI] 21 Jul 2026
Abstract We study stochastic dynamic matching on hypergraphs: items of finitely many classes arrive over time and are removed in multisets by activating hyperedges. We characterize stabilizability, the existence of a matching policy under which the queue process is positive recurrent, in terms of the arrival rates and the incidence matrix alone: (G, λ) is stabilizable if and only if the conservation equation Aµ = λ admits a nonnegative solution whose support induces a surjective submatrix, equivalently λ lies in the interior of the cone generated by the hyperedges. This extends a characterization known for simple graphs (non-bipartiteness together with the independent-set inequalities) to arbitrary hyperedges, allowing multiplicities and mono-edges, and, unlike the constant-regret theory, needs no general-position assumption. Sufficiency is constructive: a single λ-oblivious policy, Virtual-Queue Match-the-Longest (VQML), a rewardless variant of the Extended Greedy Primal–Dual policy of Nazari and Stolyar, stabilizes every stabilizable instance and is therefore maximally stable. 2012 ACM Subject Classification Mathematics of computing → Queueing theory; Mathematics of computing → Markov processes; Mathematics of computing → Matchings and factors Keywords and phrases stochastic dynamic matching, hypergraphs, stability, conservation cone, maximally stable policy, matching rates Acknowledgements The author thanks Céline Comte, Sushil Mahavir Varma, and Ana Bušić for the collaboration on the polytope perspective [6] from which this work grew.
1
Introduction
In an online stochastic matching system, items of finitely many classes arrive at random over time, wait in per-class queues, and are removed in compatible groups: a fixed family of (hyper)edges specifies which multisets of classes may be matched and cleared together. Such models describe kidney-exchange chains, assemble-to-order and manufacturing, ride-sharing, and multi-way resource pooling; three-way matching arises naturally in quantum switches, where an entanglement request consumes one qubit from each of several nodes. The first question about any such system, before optimizing rewards or delay, is stabilizability: does there exist a matching policy under which the queues do not blow up? For matching on simple graphs (every edge has size two) this question is fully answered. Mairesse and Moyal [14] showed that a connected graph is stabilizable for some arrival rate exactly when it is non-bipartite, and that match-the-longest is then maximally stable; the precise stability region is cut out by independent-set (Hall-type) inequalities [14, 7, 1]. The polytope perspective of [6] recasts this through the conservation polytope: writing A for the class-edge incidence matrix and λ for the arrival-rate vector, (G, λ) is stabilizable if and only if λ lies in the interior of the cone generated by the edges, equivalently the conservation equation Aµ = λ admits a nonnegative solution whose support induces a surjective submatrix. This linear-algebraic characterization [6, Proposition 8, §3.3.2] is the starting point of the present paper.
2
Online stochastic matchings: stability on hypergraphs
Contribution. We extend that characterization verbatim to hypergraphs (edges of any size, with multiplicities and mono-edges allowed). Theorem 3.1 shows that (G, λ) is stabilizable if and only if the same support-surjective conservation condition holds, equivalently λ ∈ int cone(A), equivalently there is no boundary certificate: no y ̸= 0 with ⟨y, Ak ⟩ ≥ 0 for all k and ⟨y, λ⟩ ≤ 0. In the simple graph case the condition reduces to non-bipartiteness together with the independentset inequalities, so the theorem is a strict generalization. The original paper outlines this hypergraph extension but leaves its formal treatment out of scope [6, §8.3]. Sufficiency is constructive and λ-oblivious: a single policy defined from G alone, Virtual-Queue Matchthe-Longest (VQML), introduced in [6] as the rewardless variant of the Extended Greedy Primal–Dual policy of Nazari and Stolyar [20], stabilizes every stabilizable instance and is therefore maximally stable. Proving this requires the positive recurrence of the signed virtual queue underlying VQML, which [20] invoke but, to our knowledge, do not prove for the signed chain (see Section 2); supplying it (a uniform inward drift from the interior hypothesis, together with a reachability argument for the origin) is a second contribution.
Why the simple graph proof does not transfer. On simple graphs, sufficiency is obtained by a greedy policy (match-the-longest), through a coupling with the bipartite double cover [14]. That route is unavailable on hypergraphs, and the obstruction is structural rather than technical: greedy (non-idling) policies are in general not maximally stable on hypergraphs, so a maximally stable policy must sometimes idle. Note that even on simple graphs, some greedy policies can be unstable [19]; what is special about simple graphs is that some greedy policies, like match-the-longest, are maximally stable [14], so idling is never needed there. On hypergraphs, no greedy policy can fit the requirement. The phenomenon is documented in several forms: for three-way matching in quantum switches, MaxWeight with idling outperforms every non-idling policy (in a throughput sense, under abandonment) [26], and greedy matching is hindsight-optimal only in two-way networks [13, 12]. This is why VQML carries a signed virtual queue and a reservation mechanism rather than greedy matching on arrival. Section 4 gives a minimal, fully controlled illustration. The rest of the paper goes as follows: Section 2 places the result in the literature; Section 3 fixes the model and states Theorem 3.1. Section 4 illustrates it on a handy toy-example, the candy. Section 5 proves the theorem, with the longer verifications of the sufficiency step deferred to the appendices.
2
Related work
Stability of graph matching. The general (non-bipartite) stochastic matching model was introduced by Mairesse and Moyal [14], who characterized stabilizability by non-bipartiteness and proved match-thelongest maximally stable; Comte [7] and Begeot et al. [1] gave the stability region and product-form and ubiquitous-measure descriptions, and [18] a product form for the general model. The bipartite case, non-stabilizable on its own but central to the FCFS matchingrate theory, goes back to Caldentey–Kaplan–Weiss and Bušić–Gupta–Mairesse [5, 4]. The polytope/conservation viewpoint we build on is that of [6].
F. Mathieu
Multi-way matching and hypergraphs. Rahme and Moyal [21] initiated the stability study of matching on hypergraphs. They give necessary conditions in terms of transversals, rank and anti-rank, and exhibit broad families of non-stabilizable geometries (e.g. a hyperedge with two degree-one classes, or r-uniform “bipartite” hypergraphs), together with the exact region for complete 3-uniform hypergraphs. Two features leave the general question open, and motivate the present work: their policies are greedy (matching is mandatory on arrival), so the possibility that idling enlarges the stabilizable set is outside their framework; and no single policy is shown or conjectured maximally stable, the authors noting that progress seems “likely to be obtained only on a case-by-case basis” [21, §7]. Related threads include matching on multigraphs [2], generalized max-weight policies under mandatory matching [11], and the open-problem survey of Mairesse and Moyal [15]. Three-way matching in quantum switches [24, 26] is a concrete hypergraph application where idling strictly enlarges the achievable region (in a throughput sense, under abandonment) [26].
Control, greedy policies, and regret. A parallel line studies reward maximization and regret rather than bare stability. Nazari and Stolyar [20] introduced the Extended Greedy Primal–Dual (EGPD) policy, whose rewardless variant is our VQML. Kerimov, Ashlagi and Gurvich [13, 12] characterize and achieve constant regret under a general-position condition (i.e. the static planning LP has a unique, nondegenerate optimum) and show greedy policies are hindsight-optimal in two-way networks but not beyond; Gupta [8] gives a greedy multi-way policy with bounded regret from the optimal basis, and Wei, Xu and Yu [25] a constant-regret primal-dual policy for multi-way matching. Gurvich and Ward [9] study the dynamic control of matching queues. These policies are either two-way, or λ-dependent, or tuned to a reward objective; none is a single λ-oblivious maximally stable policy, which is what the characterization requires.
What [20] provides, and what is missing. EGPD supplies exactly the mechanism our sufficiency proof needs: a signed virtual queue driven by MaxWeight [23], decoupled from the physical feasibility constraints. In its rewardless form it is λ-oblivious. But it does not settle the question addressed here on two counts. First, [20] target reward maximization; they do not characterize stabilizability, and in particular do not identify λ ∈ int cone(A) (in support form) as the exact frontier. They do come close informally: [20, §3.6.2] remark that their Assumption 5 is essentially stabilizability together with a condition that the queues “can be moved in any direction”, and our Lemma 5.2 makes one direction of this precise, deriving Assumption 5 from λ ∈ int cone(A). Second, their stability argument [20, §3.5] rests on the positive recurrence of the signed virtual chain, which is asserted with a pointer to [22, §4.9], a MaxWeight positive-recurrence result for nonnegative queues (as [20, §4] themselves note, that model constrains all queues to be nonnegative); for the signed chain, whose coordinates may go negative and whose communicating structure is not a priori irreducible, we could locate no proof. We isolate the rewardless core, prove the missing positive recurrence (a uniform inward drift from the interior hypothesis, together with a deterministic reachability argument for the origin), and only then use the policy as the sufficiency witness. So EGPD, as VQML, is the key that unlocks sufficiency, but both the characterization and the proof that VQML is maximally stable are contributions here.
3
4
Online stochastic matchings: stability on hypergraphs
3
Model and statement
Let V = {1, . . . , n} be a finite set of classes and E = {1, . . . , m} a finite set of hyperedges, described by an incidence matrix A ∈ Nn×m : activating hyperedge k consumes Ai,k items of class i, for each i ∈ V . We write Ak ∈ Nn for the k-th column and assume Ak = ̸ 0 for all k. Mono-edges (Ak = ei , a class that departs on its own) and repeated entries (Ai,k ≥ 2, several items of one class cleared at once) are allowed. We write G = (V, E) for the hypergraph so described, and call a pair (G, λ) a hypergraph matching problem. Items of class i arrive according to independent Poisson processes with rates λi > 0, one item at a time; we write P Λ = i λi and λ̄ = λ/Λ, so that arrival classes at successive epochs are i.i.d. with law λ̄. Unmatched items wait in per-class queues X(t) ∈ Nn . A matching policy decides, at arrival epochs, which hyperedges to activate (each activation of k removes the multiset Ak from the queues, and is allowed only if the queues suffice); policies may use an auxiliary internal state and may idle, subject to: (a) (countable Markov structure) the internal state ranges over a fixed countable set, and both the activation decision and the state update occur at arrival epochs only, each a function of the current state S(t) and the arriving class a(t) alone (possibly through fresh independent randomness); thus S(t) = (queue vector, internal state) is a time-homogeneous Markov chain on a countable state space, and the continuous-time process is its constant-rate-Λ uniformization. Randomization is permitted in the transition kernel, but a continuously distributed quantity may not be stored in the internal state, which would leave the countable setting. (b) The number of activations per epoch is uniformly bounded. The system starts empty: X(0) = 0 and the policy’s internal state starts at its distinguished initial value (matching the convention of [6, Appendix A], whose policy model starts at S0 = ∅). The model (G, λ, Φ), where Φ is a matching policy adapted to the problem (G, λ), is stable if the embedded chain is positive recurrent on the communicating class of the initial (empty) state, equivalently if the continuous-time chain is; the problem (G, λ) is stabilizable if some policy makes it stable. A policy is maximally stable if it stabilizes every stabilizable problem. m The conservation equation is Aµ = λ, µ ∈ Rm ≥0 ; we write cone(A) = A R≥0 for the cone m n spanned by the columns of A, and call A surjective when AR = R (trivial left kernel). ▶ Theorem 3.1. For a hypergraph matching problem (G, λ) with λ ∈ Rn>0 , the following are equivalent: (i) (G, λ) is stabilizable; (ii) for every y ∈ Rn \ {0} such that ⟨y, Ak ⟩ ≥ 0 for all k ∈ E, we have ⟨y, λ⟩ > 0; (iii) the conservation equation admits a solution µ with µk > 0 for all k, and A is surjective; equivalently, λ ∈ int cone(A); (iv) (support form) the conservation equation admits a solution µ ∈ Rm ≥0 such that the restriction of A to the columns in supp(µ) is surjective. Condition (iv) is a convenient form for checking stabilizability: it makes no global assumption on A, asking only for one nonnegative conservation solution whose support is surjective, rather than positivity on every hyperedge. In the simple graph case it reads: some nonnegative solution of Aµ = λ has a support whose each connected component is nonbipartite. A single policy, VQML (see Section 5.3), defined from G alone with no knowledge of λ and no parameter, stabilizes (G, λ) whenever these conditions hold; it is therefore maximally stable. ▶ Remark 3.1 (Scope of the policy class). The class of policies we consider here strictly extends the policy model of [6, Appendix A]: it allows several activations per epoch, matchings
F. Mathieu
5
among already-queued items (not involving the arriving item), and drops the assumptions of a unique empty state and of irreducibility (the latter must then be proven for a given policy, not assumed). In particular, the necessity part of Theorem 3.1 (Proposition 5.1) is proven over this wider class, so the equivalence closes at the wider class and a fortiori constrains those policies. Note that the assumption of a uniform bound in activations per epoch can be relaxed to a first-moment condition on the per-epoch activation count, with the bounded-increment step of Proposition 5.1 then justified by dominated convergence in place of a uniform bound. We keep the uniform bound for simplicity. ▶ Remark 3.2 (Graph case). When every column has two unit entries (simple graphs), (ii) recovers the classical independent-set condition for graphs [14]: for an independent set I with neighborhood Γ(I), the vector y = 1Γ(I) − 1I satisfies y ⊤ Ak ≥ 0 for every edge k (edges inside I do not exist; edges from I go to Γ(I) and contribute 0; all other edges contribute 0, 1 or 2), and ⟨y, λ⟩ > 0 reads λ(Γ(I)) > λ(I). Bipartiteness of a component yields y = ±(1V + − 1V − ) with y ⊤ A = 0, so (ii) fails for one of the two signs: condition (ii) subsumes both non-bipartiteness and the independent-set inequalities. The converse, that these classical conditions (for connected graphs) imply (ii), is the graph characterization of [14]. ▶ Remark 3.3 (A degenerate example covered by Theorem 3.1 but not by general-position conditions). Let n = 3 and let 0 A = 0 1
1 0 1
1 1 1
0 1 , with λ = (1, 1, 2). 1
Then A is surjective and the positive solutions of Aµ = λ form the segment µ(t) = (t, 1 − t, t, 1 − t), t ∈ (0, 1), yet every basic feasible solution is degenerate (supports {1, 3} or {2, 4}, each of rank 2). The general-position conditions on which constant-regret analyses rely [12] therefore fail, yet Theorem 3.1 shows (G, λ) is stabilizable, and by a λ-oblivious policy.
4
Case study: the candy hypergraph
We illustrate Theorem 3.1 on a small but instructive hypergraph, which we call the candy. The candy makes concrete the greedy–idling gap exposed in Section 1: a greedy (non-idling) policy can fail to stabilize a stabilizable instance, so idling is necessary. This is specific to hypergraphs: on simple graphs match-the-longest is maximally stable [14], so idling is never needed there, whereas on hypergraphs it can be necessary, as in quantum switches, where idling strictly enlarges the throughput region under abandonment [26]. While other examples have been proposed before, the candy is, to our knowledge, the simplest fully controlled instance of this phenomenon: a purely combinatorial model with a closed-form stability region and an instability threshold provable for every greedy policy. It separates the combinatorial question answered by Theorem 3.1 from the algorithmic behavior of greedy matching.
The candy. The candy, shown in Figure 1, has n = 7 classes and m = 7 hyperedges: two regular triangles on {1, 2, 3} and {5, 6, 7}, joined by a single central hyperedge {3, 4, 5}, whose private class 4 has degree one (it belongs to no other edge).
6
Online stochastic matchings: stability on hypergraphs
1
6 3
2
4
5
hyperedge {3, 4, 5}
7
Figure 1 The candy: two triangles {1, 2, 3} and {5, 6, 7} joined by the hyperedge {3, 4, 5} (shaded), whose private class 4 has degree one. Simple edges are drawn as segments, the hyperedge as a region enclosing its three classes.
With edge order {1, 2}, {1, 3}, {2, 3}, {5, 6}, {5, 7}, {6, 7}, {3, 4, 5}, the incidence matrix is 1 1 0 A = 0 0 0 0
1 0 1 0 0 0 0
0 1 1 0 0 0 0
0 0 0 0 1 1 0
0 0 0 0 1 0 1
0 0 0 0 0 1 1
0 0 1 1 . 1 0 0
It is square and invertible, so Aµ = λ has a unique solution µ(λ) for every λ, and by Theorem 3.1 (surjectivity holds since det A ̸= 0) (G, λ) is stabilizable iff that solution is strictly positive. Solving the two triangles against the central edge gives the following closed form. ▶ Proposition 4.1 (Stability region of the candy). The candy is stabilizable if and only if |λ1 − λ2 | < λ3 − λ4 < λ1 + λ2
and
|λ7 − λ6 | < λ5 − λ4 < λ6 + λ7 .
Proof. Class 4 has the hyperedge as its only edge, so µ{3,4,5} = λ4 . On the first triangle the remaining balance equations are µ{1,2} +µ{1,3} = λ1 , µ{1,2} +µ{2,3} = λ2 and µ{1,3} +µ{2,3} = λ3 −λ4 , whose unique solution is µ{1,2} = 12 (λ1 +λ2 −(λ3 −λ4 )), µ{1,3} = 12 (λ1 −λ2 +(λ3 −λ4 )), µ{2,3} = 12 (λ2 − λ1 + (λ3 − λ4 )). These are all positive iff |λ1 − λ2 | < λ3 − λ4 < λ1 + λ2 ; the second triangle is symmetric. By Theorem 3.1 positivity of µ(λ) is equivalent to stabilizability. ◀ Proposition 4.1 shows that the bridge class 3 (and similarly class 5) must both feed the central hyperedge (at rate λ4 , leaving λ3 − λ4 ) and absorb its triangle’s imbalance |λ1 − λ2 |; when the leftover cannot cover the imbalance, (G, λ) leaves the cone. For instance λ = (1.5, 1, 1.1, 1, 1.1, 1, 1.5) is not stabilizable: here λ3 −λ4 = 0.1 < 0.5 = |λ1 −λ2 |, the forced solution has µ{2,3} = µ{5,6} = −0.2, and Theorem 3.1(ii) is violated by y = 1{2,3} − 1{1,4} , for which y ⊤ Ak ≥ 0 for every edge yet ⟨y, λ⟩ = −0.4 < 0.
A stabilizable family. Fix α ∈ (0, 1) and take λα = (1, 1, 3α, α, 3α, 1, 1). Both conditions of Proposition 4.1 hold (0 < 2α < 2), so the candy is stabilizable for every α ∈ (0, 1); the unique matching-rate vector puts 1 − α on the two outer edges {1, 2}, {6, 7} and α on the other five edges (including the hyperedge). By Theorem 3.1, VQML (defined in Section 5.3) stabilizes the whole family.
F. Mathieu
Greedy policies fail. A policy is greedy (non-idling) if, whenever an arriving item can be part of an activable edge, some edge is activated at that arrival.1 Match-the-longest is greedy. On the candy, greedy policies are provably unstable for small α, in contrast with VQML. 2 ▶ Proposition 4.2 (Greedy instability of the candy). For the family λα with α < 21 , no greedy policy is stable: no non-idling policy makes the chain positive recurrent. Specifically, Q4 diverges (see Remark 4.1).
Proof. Fix any greedy policy and suppose that the chain is positive recurrent. We first establish two invariants, jointly by induction over arrival epochs from the empty start: (a) in each triangle at most one of its three queues is positive; and (b) Q3 , Q4 , Q5 are not all positive. Both hold at the empty state. Assume (a) and (b) just before an arrival. Then no edge is activable from queued items alone: a triangle edge would need two positive queues in one triangle (excluded by (a)), and the hyperedge {3, 4, 5} would need Q3 , Q4 , Q5 all positive (excluded by (b)). Hence every activable edge contains the arriving item, and a greedy policy, which must activate some edge when it can, activates one containing the arrival, thereby consuming it. So the arriving item never remains beside a compatible neighbor, and checking the arrival classes one by one shows (a) and (b) pass to the post-arrival state; the invariants follow. In particular, when Q3 > 0 we have Q1 = Q2 = 0 by (a), so an arriving class 1 or 2 completes only {1, 3} or {2, 3} and is forced to remove one class-3 item. Thus while Q3 > 0 the queue Q3 decreases at rate at least λ1 + λ2 = 2, and it increases only at class-3 arrivals, of rate λ3 = 3α. Coupling class-3 arrivals to births and class-1/2 arrivals to services, Q3 is pathwise dominated (from the empty start) by an M/M/1 queue of load 3α/2; hence the long-run fraction of time with Q3 > 0 is at most that queue’s, namely 3α 2 , and, the chain being positive recurrent by hypothesis, equals the stationary probability: P(Q3 > 0) ≤ 3α 2 . Symmetrically P(Q5 > 0) ≤ 3α . 2 The hyperedge {3, 4, 5} fires only when an arrival completes it, i.e. on a class-3 arrival with Q4 , Q5 > 0, a class-5 arrival with Q3 , Q4 > 0, or a class-4 arrival with Q3 , Q5 > 0. By PASTA its firing rate satisfies 2 rh ≤ 3α P(Q5 > 0) + 3α P(Q3 > 0) + α P(Q3 > 0, Q5 > 0) ≤ 29 + 92 + 32 α2 = 21 2 α . Class 4 leaves the system only through the hyperedge, so positive recurrence forces the throughput identity rh = λ4 = α (the exact-balance argument of Proposition 5.1, Step 1, 2 2 applied to class 4). Combining yields α ≤ 21 2 α , i.e. α ≥ 21 . Hence no greedy policy is 2 positive recurrent for α < 21 . ◀ ▶ Remark 4.1. The invariants (a) and (b), and the M/M/1 domination, are pathwise and use 2 no recurrence assumption; with the strong law they give lim inf T →∞ Q4 (T )/T ≥ α− 21 2 α >0 2 almost surely for α < 21 : under any greedy policy the central queue diverges at least linearly. 2 The threshold 21 ≈ 0.095 is deliberately conservative: the M/M/1 domination is loose. Simulations put the true match-the-longest threshold near some α0 ≈ 0.45. The robust point
1
This is the non-idling sense. It excludes commit-and-reserve policies such as the bounded-regret greedy of [8], which assigns arrivals to optimal-basis configurations without matching them on the spot (closer to VQML’s virtual backlog than to non-idling matching) and uses knowledge of λ; Proposition 4.2 does not constrain those.
7
Online stochastic matchings: stability on hypergraphs
is the qualitative separation. Figure 2 plots the mean central queue Q4 and the global delay under match-the-longest and under VQML across the family (matching simulator of [16], 107 arrivals per point).
Q4 (mean size of central queue)
103 ML (greedy) VQML α = 2/21 α0 (empirical)
102 101 100 10−1 10−2 10−3 0
0.1
0.2
0.3
0.4
0.5 α
0.6
0.7
0.8
0.9
1
(a) Mean central queue Q4 . For ML, the observed central queue grows sharply as α decreases toward α0 , whereas VQML stays stable for every α. Note that (G, λ0 ) is unstable, which explains why Q4 grows for VQML when α → 0.
102
Delay (mean waiting time)
8
ML (greedy) VQML α = 2/21 α0 (empirical)
101
100
10−1 0
0.1
0.2
0.3
0.4
0.5 α
0.6
0.7
0.8
0.9
1
(b) Average delay, obtained from average queue sizes by Little’s law. Compared with Figure 2a, note the high delay for α → 1: (G, λ1 ) is unstable. The impacted classes are the outer ones (1, 2, 6, and 7), not the central class 4.
Figure 2 Candy family λα = (1, 1, 3α, α, 3α, 1, 1) under match-the-longest (greedy) and VQML policies. 107 simulated arrivals per point. Match-the-longest is shown only where the run is empirically stable. The provable greedy-instability bound α < 2/21 and the empirical bound α0 ≈ 0.45 are marked. Reproduced with the package [16] in the companion notebook [17].
F. Mathieu
Non-stabilizable hyperedges The candy isolates the mechanism behind the non-stabilizable hypergraphs cataloged by Rahme and Moyal [21]: a class that lies in a single hyperedge is drained only jointly with the other classes of that edge, which couples their rates. The extreme case is a lone hyperedge {1, 2, 3}: here A has rank 1, so A is not surjective and Theorem 3.1(iv) fails for every λ (three classes cannot be balanced by one control). Adding an edge {3, 4} (so that the hyperedge {1, 2, 3} has two degree-one classes, 1 and 2) leaves A of rank 2 < 4; for λ = (1, 1, 2, 1) the left-kernel vector y with y1 = 1, y2 = −1 certifies non-stabilizability, matching [21]. In each case the obstruction is exactly the failure of the support-surjectivity of Theorem 3.1(iv); the negative examples of [21] we have checked fail this condition or leave the cone, and condition (iv) recovers their exactly-solved region for the complete 3-uniform case [21, Thm. 1]. ▶ Remark 4.2 (Discarding versus abandonment). A mono-edge Ak = ei is a controlled discard of class i: the policy may remove a class-i item on its own. Adding the mono-edges {ei : i ∈ S} for a set S ⊆ V therefore models discarding (loss) on S, and Theorem 3.1 applies verbatim with A extended by those columns. Discarding only enlarges cone(A), so it can only help: for S = V the mono-edges already span Rn≥0 , hence λ ∈ Rn>0 ⊆ int cone(A) for every λ and the problem is stabilizable unconditionally. This is the familiar fact that abandonment everywhere trivializes stability. However, for a strict subset S ⊊ V the criterion is genuine: the non-discardable classes must still be balanced by matches. Partial discarding is thus covered by the same characterization, with no separate theory, and connects to the loss-queue viewpoint of [7]. This is the controlled face of abandonment. Genuine spontaneous departures, where items leave at exogenous rates (outside the controller’s choice), are a different, non-monotone mechanism. Because a policy may act several times per epoch (Section 3), they can be modeled by appending an environment-driven departure step after the policy’s move, with their own self-edges to keep controlled and uncontrolled removals distinct; but they need not preserve stabilizability, and a maximally stable witness would have to be re-derived (VQML rests on the pathwise slaving of Lemma 5.5, which forced removals break). On the candy, for instance, strong spontaneous departures at the bridge classes 3 and 5 can destabilize an otherwise stabilizable instance: the bridge items vanish before they can be held together with class 4, starving the hyperedge {3, 4, 5}, which is class 4’s only outlet, so that, for strong enough departure rates, one expects Q4 to diverge under every policy, greedy or idling; we do not prove this here. A full treatment of spontaneous departures is left to future work.
5
Proof of Theorem 3.1
We prove the cycle (i) ⇒ (ii) ⇒ (iii) ⇒ (i), folding in the support-form relaxation (iv) by elementary geometry, in four steps. Geometry (Section 5.1). Convex duality collapses (ii), (iii) and λ ∈ int cone(A) into one equivalence class (Lemma 5.1); (iv) is folded in at assembly. From here the analytic content is carried by λ ∈ int cone(A) alone. Necessity (Section 5.2). A short argument combining stationarity with the central limit theorem shows any stabilizing policy forces the exact balance λ̄ = Aµ̄ and admits no boundary certificate (Proposition 5.1); this is (i) ⇒ (ii), and it uses only exogeneity of arrivals and bounded increments, so it covers the whole Markov policy class. Sufficiency (Section 5.3), the substantial step. We exhibit a single λ-oblivious policy, VQML, and prove it stabilizes every (G, λ) with λ ∈ int cone(A); this gives (iii) ⇒ (i) and,
9
10
Online stochastic matchings: stability on hypergraphs
the policy being common to all instances, maximal stability at once. As this step spans several lemmas, it opens with its own plan. Assembly (Section 5.4). The three implications are chained and (iv) is folded in, closing the equivalence.
5.1
Convex geometry: (ii) ⇔ (iii)
▶ Lemma 5.1 (Convex duality). For λ ∈ Rn>0 the following are equivalent: (a) λ ∈ int cone(A); (b) A is surjective and ∃µ ∈ Rm >0 with Aµ = λ; (c) condition (ii) of Theorem 3.1. Proof. Throughout, cone(A) is a finitely generated convex cone, hence closed (Minkowski– Weyl). (b) ⇒ (a). A surjective linear map is open, so A({µ > 0}) is an open subset of Rn (not merely of cone(A)); it contains λ and is contained in cone(A), whence λ ∈ int cone(A). (a) ⇒ (b). Full-dimensionality of cone(A) forces rank A = n, i.e. surjectivity. Let P w = A1 = k Ak . Since λ ∈ int cone(A), λ − εw ∈ cone(A) for small ε > 0: λ − εw = Aν with ν ≥ 0, hence λ = A(ν + ε1) with ν + ε1 > 0. (a) ⇒ (c). Let y ̸= 0 with y ⊤ A ≥ 0. Then cone(A) ⊆ Hy := {x : y ⊤ x ≥ 0}, so int cone(A) ⊆ int Hy = {x : y ⊤ x > 0}, and y ⊤ λ > 0. (c) ⇒ (a). Contrapositive. If λ ∈ / cone(A): since cone(A) is closed and convex, strict separation yields y with y ⊤ λ < 0 ≤ inf x∈cone(A) y ⊤ x; the infimum over a cone being > −∞ forces y ⊤ x ≥ 0 on cone(A), in particular y ⊤ A ≥ 0, and y = ̸ 0, violating (c). If λ ∈ ∂ cone(A): a supporting hyperplane at λ yields y = ̸ 0 with y ⊤ λ = 0 ≤ y ⊤ x on cone(A) (the equality by testing x = 0 and x = 2λ), again y ⊤ A ≥ 0, violating (c). (Degenerate case: if cone(A) is not full-dimensional, any y = ̸ 0 orthogonal to its span satisfies y ⊤ A ≥ 0 for both ±y, and one of ⊤ ±y has y λ ≤ 0; so (c) also forces full-dimensionality, consistently.) ◀
5.2
Necessity: (i) ⇒ (ii)
▶ Proposition 5.1. If (G, λ) is stabilizable, then condition (ii) holds. Proof. Let Φ stabilize (G, λ): the embedded chain (S(t))t∈N (queues X(t) plus internal state, observed at arrival epochs) is positive recurrent on the communicating class of its initial state, hence admits a unique stationary distribution π on that class. Throughout the proof we work with the stationary version: S(0) ∼ π. Let a(t) ∈ {e1 , . . . , en } denote the arrival at epoch t (i.i.d. with law λ̄, independent of (S(u))u≤t , as arrivals are exogenous), let sk (t) ∈ N denote the number of activations of hyperedge k at epoch t (uniformly bounded, P P by assumption (b)), and N (t) = u<t a(u), Mk (t) = u<t sk (u), so that X(t) = X(0) + N (t) − A M (t) ≥ 0.
(1)
By stationarity, µ̄k := E[sk (t)] ∈ [0, ∞) does not depend on t. Step 1: exact balance, λ̄ = Aµ̄. The one-step increment ∆(t) = X(t + 1) − X(t) = a(t) − As(t) is uniformly bounded, say ∥∆(t)∥∞ ≤ C. For M > 0, stationarity of X gives E[min(Xi (t + 1), M ) − min(Xi (t), M )] = 0, while | min(Xi (t + 1), M ) − min(Xi (t), M ) − ∆i (t)| ≤ 2C 1{Xi (t) ≥ M − C}. Taking expectations and letting M → ∞ (the correction term vanishes because Xi (t) is an a.s. finite random variable): E[∆i (t)] = 0 for every i, that is, λ̄ = Aµ̄ with µ̄ ≥ 0. Note: no ergodic theorem and no integrability of X are used, only stationarity and bounded increments.
F. Mathieu
11
Step 2: boundary certificates are impossible. Suppose, for contradiction, that some y ̸= 0 P has y ⊤ A ≥ 0 and ⟨y, λ⟩ ≤ 0. Since λ̄ = Aµ̄ and y ⊤ A ≥ 0, ⟨y, λ̄⟩ = k (y ⊤ Ak )µ̄k ≥ 0; combined with ⟨y, λ⟩ ≤ 0 this forces ⟨y, λ⟩ = 0 and, term by term, µ̄k = 0
for every k with y ⊤ Ak > 0.
(2)
For such k, E[sk (t)] = 0 with sk (t) ≥ 0 implies sk (t) = 0 a.s., for every t; by a countable union, almost surely no hyperedge with y ⊤ Ak > 0 is ever activated. Hence Equation (1) gives, almost surely, ⟨y, X(t)⟩ = ⟨y, X(0)⟩ + St ,
St := ⟨y, N (t)⟩.
The random variables ⟨y, X(t)⟩ are tight in t (their law does not depend on t), hence so is St = ⟨y, X(t)⟩ − ⟨y, X(0)⟩ (a difference of two tight sequences is tight: P(|U − V | > 2K) ≤ P(|U | > K) + P(|V | > K)). But St is a sum of t i.i.d. increments taking value yi with probability λ̄i > 0; the increments are not a.s. zero (some yi ̸= 0, and every class has P positive arrival probability) and have mean exactly ⟨y, λ̄⟩ = 0 and variance σ 2 = i λ̄i yi2 > 0, so by the central limit theorem P(|St | ≤ K) → 0 for every fixed K: St is not tight. Contradiction. ◀ ▶ Remark 5.1. Step 2 quantifies over arbitrary stationary policies within the Markov class: no greediness, no matching-at-arrival restriction, and no knowledge of how ties are broken are used, only exogeneity of the arrivals and the exact-balance structure (1). The argument uses only the existence of some invariant probability for the chain, so condition (ii) is necessary under weaker stability notions as well: positive recurrence of any reachable class, or (by a Cesàro-averaging argument) mere tightness of the queue-length laws.
5.3
Sufficiency: (iii) ⇒ (i), via a maximally stable policy
Plan of the sufficiency proof. Fix (G, λ) with λ ∈ int cone(A); we build one policy, VQML, and show it makes the physical system positive recurrent. The argument runs in three stages: the first is purely about an auxiliary chain, the last two about the real system. Stage 1: an autonomous virtual chain, stable by design (Lemmas 5.2–5.4 and Proposition 5.2). VQML maintains a signed virtual queue Q ∈ Zn (coordinates may go negative) driven by MaxWeight, decoupled from the feasibility constraints of the physical queues. On this chain alone the interior hypothesis λ ∈ int cone(A) gives a uniform inward drift in every direction (Lemma 5.2), making ∥Q∥22 a Foster–Lyapunov function with negative drift outside a finite set (Lemma 5.3); a separate deterministic steering argument shows the origin is reachable from every state (Lemma 5.4), and drift plus reachability give positive recurrence of Q on the communicating class of 0 (Proposition 5.2). This stage never mentions physical items. Stage 2: the physical system is slaved to Q (Lemma 5.5 and Corollary 5.1). The real state is a triple (X, Q, B): physical queues X, the same virtual queue Q, and a FIFO backlog B of matchings decided virtually but not yet physically completed. Following the pipeline pathwise (Lemma 5.5) shows the physical quantities are governed by Q: the unassigned items equal Q+ , the residual demand equals Q− , and the backlog and total item count are bounded in terms of ∥Q∥1 (Lemma 5.5). In particular Q(t) = 0 forces the whole system empty (Corollary 5.1), so the virtual and physical chains regenerate at the same instants.
12
Online stochastic matchings: stability on hypergraphs
Stage 3: transfer (Lemma 5.6). Since regenerations coincide, the finite mean return time of Q to 0 from Stage 1 is the mean return time of the full state to empty, giving positive recurrence of the physical system; a renewal–reward count along regeneration cycles identifies the long-run activation rates µ̄ with Aµ̄ = λ̄, so VQML matches every class at its full arrival rate. This proves (iii) ⇒ (i), and since VQML depends only on G, it is maximally stable.
5.3.1
The policy VQML.
Following Nazari and Stolyar [20], run a virtual system alongside the physical one. The virtual queue vector Q(t) ∈ Zn (signed, no reflection) starts at Q(0) = 0. At each arrival epoch t (arrival vector a(t) ∈ {e1 , . . . , en }), the controller activates a multiset of at most two hyperedges, chosen by signed MaxWeight: s(t) ∈
arg max
⟨Q(t), As⟩,
Q(t + 1) = Q(t) + a(t) − A s(t),
(3)
s∈Nm , ∥s∥1 ≤2
with the canonical tie-breaking rule: idle (s = 0) whenever maxk ⟨Q(t), Ak ⟩ ≤ 0; otherwise take the lexicographically smallest maximizer of smallest ℓ1 -norm. This is a deterministic, state-only rule, so (Q(t)) is a time-homogeneous Markov chain. Only the idle clause matters: for adversarial rules that activate zero-score hyperedges at ties, the state 0 can be transient (see Remark 5.2), whereas any rule with the idle clause works (see Lemma 5.4). Note ⟨Q(t), As(t)⟩ ≥ 0 always. Virtually activated hyperedges join a FIFO backlog of incomplete matchings, completed by the mechanism specified before Lemma 5.5 below (Nazari–Stolyar’s completion mechanism, [20, Sec. 3.3–3.4]). The policy uses no knowledge of λ and no parameter: scaling Q by any β > 0 does not change the argmax. ▶ Lemma 5.2 (Interior point yields drift mixtures). Assume (iii) and let λ̄ = λ/Λ. There exists ε > 0 such that for every sign vector σ ∈ {−1, +1}n there is φσ ∈ Rm ≥0 with ∥φσ ∥1 ≤ 2 and Aφσ = λ̄ + εσ. Proof. Let µ > 0 solve Aµ = λ and set µ̄ = µ/Λ. Summing the rows of Aµ̄ = λ̄: P k µ̄k ∥Ak ∥1 = ∥λ̄∥1 = 1, and ∥Ak ∥1 ≥ 1, so ∥µ̄∥1 ≤ 1. Thus µ̄ lies in the interior of the domain D = {φ ≥ 0, ∥φ∥1 ≤ 2} relative to Rm (componentwise positive, budget slack ≥ 1). Since A is surjective it is an open map, so A(int D) is an open neighborhood of λ̄; pick ε with λ̄ + εσ ∈ A(int D) for all 2n vectors σ. ◀ ▶ Lemma 5.3 (Foster–Lyapunov drift for the virtual chain). Assume (iii), let ε > 0 be as in Lemma 5.2, and set R = 1 + 2 maxk ∥Ak ∥1 . The virtual chain (Q(t))t∈N defined by Equation (3) satisfies E ∥Q(t + 1)∥22 − ∥Q(t)∥22 Q(t) = q ≤ R2 − 2ε∥q∥1 for every q ∈ Zn , (4) which is ≤ −1 outside the finite set F = {q : ∥q∥1 ≤ M }, M := (R2 + 1)/(2ε). Consequently: P (a) started at Q(0) = 0, supT ≥1 T1 t<T E∥Q(t)∥1 ≤ R2 /(2ε); (b) Eq [τF ] ≤ ∥q∥22 for every q∈ / F , and Eq [τF+ ] ≤ 1 + (M + R)2 for every q ∈ F , where τF = inf{t ≥ 0 : Q(t) ∈ F } and + τF = inf{t ≥ 1 : Q(t) ∈ F }. The drift bound Equation (4) holds for any tie-breaking rule (any measurable selection of a maximizer, including the canonical rule, whose idling choice is itself a maximizer when maxk ⟨q, Ak ⟩ ≤ 0, since every s ≥ 0 then scores ≤ 0 = ⟨q, A · 0⟩). Proof. Q is a time-homogeneous Markov chain on a countable subset of Zn (increments take finitely many values; the tie-breaking rule is deterministic and state-only). The arrival a(t) is exogenous, i.i.d. with law λ̄, independent of Q(t) (which is a function of past arrivals
F. Mathieu
13
only), so E[a(t) | Q(t) = q] = λ̄. Let L(q) = ∥q∥22 . With ∆ = a(t) − As(t) (bounded: ∥∆∥1 ≤ 1 + 2 maxk ∥Ak ∥1 = R), E[L(Q(t + 1)) − L(Q(t)) | Q(t) = q] = 2 q, λ̄ − A E[s(t) | q] + E[∥∆∥22 | q] ≤ 2⟨q, λ̄⟩ − 2⟨q, As(q)⟩ + R2 , where s(q) is the MaxWeight choice at q (deterministic given q up to tie-breaking; any measurable selection works). The feasible set of Equation (3) contains the vertices {0, 2ek : k ∈ E} of D = {φ ≥ 0, ∥φ∥1 ≤ 2}, and a linear objective attains its maximum over D at a vertex, so ⟨q, As(q)⟩ =
max
s∈Nm ,∥s∥1 ≤2
⟨q, As⟩ ≥ max⟨q, Aφ⟩ ≥ ⟨q, Aφσ(q) ⟩ φ∈D
= ⟨q, λ̄⟩ + ε⟨q, σ(q)⟩ = ⟨q, λ̄⟩ + ε∥q∥1 , taking σ(q) = sign(q) (arbitrary signs on zero coordinates) and φσ(q) from Lemma 5.2. This proves Equation (4); F is finite as a set of lattice points in an ℓ1 -ball. (a) All expectations involved are finite (∥Q(t)∥1 ≤ tR from Q(0) = 0 and the increment bound), so telescoping Equation (4) from Q(0) = 0 is legitimate and gives 0 ≤ E∥Q(T )∥22 ≤ P T R2 − 2ε t<T E∥Q(t)∥1 ; rearrange. (Telescoping yields only this Cesàro bound, not supt E∥Q(t)∥1 < ∞; the latter does hold, by a pathwise drift lemma à la Hajek [10] applied to ∥q∥2 , but is not needed anywhere below.) (b) For q ∈ / F , the stopped process L(Q(t ∧ τF )) + (t ∧ τF ) is a supermartingale under Pq by Equation (4), so Eq [t ∧ τF ] ≤ L(q) for every t, and monotone convergence gives Eq [τF ] ≤ L(q) = ∥q∥22 . For q ∈ F , one step lands in {q ′ : ∥q ′ ∥1 ≤ M + R} (increments have ℓ1 -norm at most R); conditioning on Q(1) and using the previous bound together with ∥q ′ ∥2 ≤ ∥q ′ ∥1 yields Eq [τF+ ] ≤ 1 + (M + R)2 . ◀ ▶ Lemma 5.4 (The origin is accessible from every state). Assume every row of A is nonzero. This holds under (iii), since Aµ = λ with µ > 0 and λi > 0 forces row i to have a positive entry. Let (Q(t)) be the virtual chain of Equation (3) under any tie-breaking rule with the canonical idle clause: s(q) = 0 whenever Ψ(q) := maxk∈E ⟨q, Ak ⟩ ≤ 0 ( idle states), and s(q) is an arbitrary maximizer of Equation (3) otherwise ( active states). P Write V (q) = i max(qi , 0) for the positive mass of q, and set amax = maxk ∥Ak ∥1 and λ̄min = mini λ̄i > 0. Then, for every q ∈ Zn , Pq τ0 ≤ ∥q∥1 + 2amax V (q)
∥q∥ +2amax V (q)
≥ λ̄min1
> 0,
τ0 := inf{t ≥ 0 : Q(t) = 0}.
In particular, 0 is accessible from every state of Zn (a fortiori from every state reachable from 0) and the set of states reachable from 0 coincides with the communicating class of 0. Proof idea; the full steering construction is in Appendix A. For each starting state q we exhibit a deterministic arrival word of length at most ∥q∥1 + 2amax V (q) that drives the chain to 0; since every prescribed arrival class has probability at least λ̄min , this yields the bound. Two facts drive the construction. First, the idle clause makes the nonpositive orthant a safe parking area: at an idle state one may feed a negative coordinate, storing the arrival without triggering an activation and lowering the negative mass by one at unchanged positive mass. Second, at an active state every maximizer removes ∥As∥1 ≥ 2 units, so one steered arrival lowers the positive mass V (q) by at least one. The positive mass therefore decreases monotonically to 0, after which the bounded negative-mass excursion is drained. ◀
14
Online stochastic matchings: stability on hypergraphs
▶ Proposition 5.2 (Positive recurrence on the class of the origin). Assume (iii), and let the tie-breaking rule be deterministic and state-only, satisfying the idle clause of Lemma 5.4 (in particular, the canonical rule of Equation (3) qualifies). Then the virtual chain started at Q(0) = 0 is positive recurrent on the communicating class of 0, which coincides with the set of states reachable from 0; in particular m0 := E0 [τ0+ ] < ∞, where τ0+ = inf{t ≥ 1 : Q(t) = 0}. Proof. Let R ⊆ Zn be the set of states reachable from 0; it is closed by definition. By Lemma 5.4, every q ∈ R leads back to 0 with positive probability, so every state of R communicates with 0: R is a single closed communicating class containing 0, and the chain restricted to R is irreducible. The drift bound Equation (4) holds at every q ∈ R, with drift ≤ −1 outside the finite set F ∩ R and finite expected one-step L-increment on it (finitely many bounded transitions per state), so Foster’s criterion for irreducible chains [3] yields positive recurrence of R. In an irreducible positive recurrent chain every state has finite mean return time; in particular m0 = E0 [τ0+ ] < ∞. ◀
▶ Remark 5.2 (Tie-breaking matters, but only through the idle clause). Positive recurrence on the communicating class of 0 does require a condition on the selection rule: for n = m = 2, A = I2 (two mono-edges), λ = (1, 1), for which (iii) is satisfied, there is a legal deterministic rule (among maximizers prefer 2e1 , then e1 , then 2e2 , then 0, then e2 , then e1 + e2 ) under which the reachable set from 0 has nine states, 0 is visited exactly once, and the chain is absorbed into a seven-state class. This is verified by exhaustive search over the reachable set, reproduced in the companion notebook [17]; the drift bound Equation (4) is unaffected, only the class structure is, and the absorbing class, being finite, is itself positive recurrent. Lemma 5.4 shows the idle clause is the only feature of the rule that matters: the adversarial rule above activates zero-score hyperedges at ties, violating precisely that clause. ▶ Remark 5.3 (What the accessibility proof uses, and what it does not). (a) Tie-breaking. The only feature of the canonical rule that is used is the idle clause: s(q) = 0 as soon as maxk ⟨q, Ak ⟩ ≤ 0. At active states, any maximizer may be selected, e.g. lexicographic, of any norm, even randomized, and Lemma 5.4 persists: for a nonanticipating randomized maximizer (one independent of the current arrival, as the decide-then-arrive convention of Equation (3) guarantees), Step 1 of the proof applies to every realized maximizer, so each steered step succeeds with conditional probability ≥ λ̄min given the past, and the bound of Lemma 5.4 holds verbatim. Intuitively, the idle clause makes negative coordinates a safe parking area: the controller can always store arrivals there without triggering activations, while any activation, having positive score, must burn at least one unit of positive mass, and its overshoot only creates more (bounded) parking space. (b) Hypotheses. Condition (iii) enters only through the innocuous consequence that every row of A is nonzero (every class belongs to some hyperedge). Accessibility of 0 needs neither surjectivity nor λ ∈ int cone(A), as those are needed for the negative drift of Lemma 5.3, not for the class structure. (c) Quantitative form. The steering word has length linear in ∥q∥1 , with explicit constant 1 + 2amax ; hence inf q∈F Pq (τ0 ≤ TF ) > 0 for the fixed horizon TF = (1 + 2amax ) maxq∈F ∥q∥1 , which combines with the uniformly bounded return times to F in the standard renewal argument (an alternative route to positive recurrence, detailed in Appendix C, not used by the main line, which goes through Proposition 5.2). (d) Numerical corroboration. The steering construction of Lemma 5.4 and the adversarial I2 trap of Remark 5.2 were crosschecked numerically over a range of incidence matrices and starting states in the companion notebook [17].
F. Mathieu
5.3.2
15
The full physical state.
Recall amax = maxk ∥Ak ∥1 from Lemma 5.4 (so R = 1 + 2amax ), and write q + = max(q, 0), P q − = max(−q, 0) componentwise, so that q = q + − q − and ∥q∥1 = i (qi+ + qi− ). A backlog entry is a pair b = (k, c) with k ∈ E and c ∈ Nn , c ≤ Ak componentwise, c ̸= Ak : a virtually activated, not yet completed matching of type k, whose fill status c records how many physical items of each class have been assigned to it; its residual is r(b) = Ak − c ≥ 0, r(b) ̸= 0. Entries live in the finite alphabet XY ΣA = (k, c) : k ∈ E, c ∈ Nn , c ≤ Ak , c ̸= Ak , |ΣA | = (Ai,k + 1) − 1 < ∞. k∈E i∈V
The full descriptor of the VQML-controlled system at epoch t is S(t) = X(t), Q(t), B(t) ∈ Nn × Zn × ΣA∗ , where X(t) counts all physical items present (assigned to a backlog entry or not), Q(t) is the virtual queue of Equation (3), and B(t) = (b1 (t), . . . , b|B(t)| (t)) is the backlog, an ordered list, oldest entry first (FIFO). Countability in one line: finite words over a finite alphabet form a countable set, so Nn × Zn × ΣA∗ is a product of three countable sets, hence countable. All components are pre-arrival snapshots, consistent with Equation (3) and with the strict sums u < t of the balance equation (1); the system starts empty, S(0) = ∅ := (0, 0, ϵ),
ϵ = empty list.
P From (X, B) we derive the assigned counts Wi = j cj,i , the unassigned counts U = X −W ∈ P P Nn , and the deficit Di = j (Ai,kj − cj,i ) = j ri (bj ), all sums running over the entries bj = (kj , cj ) of B. We restrict the state space to {(x, q, β) : W (β) ≤ x} (assigned items are physically present), a countable set that contains ∅ and is invariant under the epoch mechanism below, so that U ≥ 0 and step (D5) is well defined.
5.3.3
One epoch: decide, arrive, assign, complete.
Given S(t) and the arrival a(t) = ei , epoch t executes, in this order: (D1) Decision. s(t) = s(Q(t)) by Equation (3) with the canonical rule, computed from Q(t) alone, before the arrival lands (the decide-then-arrive timing convention already fixed by Equation (3); see Remark B.1). (D2) Virtual update. Q(t + 1) = Q(t) + a(t) − A s(t). (D3) Append. For each k, append sk (t) fresh entries (k, 0) at the tail of the list, in increasing order of k (at most two entries in total). (D4) Arrival. The arriving class-i item joins the pool of unassigned items: X becomes X + ei , hence U becomes U + ei (W unchanged). (D5) FIFO assignment. Scan the list from head (oldest) to tail; at each entry (k, c), assign min(Uj , Aj,k − cj ) currently unassigned class-j items to the entry, for each class j: Uj decreases and cj increases by that amount. (Items of one class are exchangeable, so the resulting state does not depend on which items are assigned; the scanning order over classes within an entry is immaterial.) (D6) Completion. Remove every entry whose fill status has reached c = Ak ; each removal is a physical activation of k: the entry’s ∥Ak ∥1 assigned items leave the system, so X decreases by Ak for each removed entry of type k. Removals return no items to the unassigned pool, so a single scan suffices (no cascades). The resulting triple is S(t + 1).
16
Online stochastic matchings: stability on hypergraphs
The map (S(t), a(t)) 7→ S(t + 1) is deterministic and the arrivals are i.i.d., so (S(t))t∈N is a time-homogeneous Markov chain on a countable state space. Moreover, by (D1)–(D2) the Q-component is autonomous: it evolves as a function of itself and the arrival only, and coincides pathwise (same arrival sequence) with the virtual chain of Lemmas 5.3 and 5.4. Steps (D3)–(D6) are Nazari–Stolyar’s completion mechanism [20, Sec. 3.3–3.4], written at the level of the full state; Remark B.1 details the exact relation. ▶ Lemma 5.5 (Pathwise structure of the full state). From the empty start, every trajectory of (S(t)) satisfies, for all t ∈ N: (a) (conservation) Q(t) = U (t) − D(t); (b) (complementarity) Ui (t) Di (t) = 0 for every i; consequently U (t) = Q+ (t) and D(t) = Q− (t); P (c) (backlog bound) |B(t)| ≤ i Q− (t); P P − P Pi (d) (queue bound) i Xi (t) ≤ i Q+ i (t) + (amax − 1) i Qi (t); in particular i Xi (t) ≤ P + P − Q (t) + a Q (t). max i i i i The proof uses only (D2)–(D6) and never the decision rule (D1): all four statements hold for an arbitrary decision sequence (s(t))t , with Q defined from that sequence by (D2). In particular under either within-epoch timing convention (decide-then-arrive, as in Equation (3), or arrive-then-decide), provided the epoch pipeline (D3)→(D4)→(D5)→(D6) is preserved and only the position of the decision moves (the single scan must follow both the appends and the arrival). Proof idea; details in Appendix B. Identities (a) and (b) follow by induction over the epoch pipeline (D2)–(D6): each step’s effect on (U, D) is immediate, and the single FIFO scan (D5) forces Ui Di = 0, whence U = Q+ and D = Q− by uniqueness of the Jordan decomposition. Bounds (c) and (d) then follow by summing residuals over the backlog. ◀ ▶ Remark 5.4 (VQML lies in the admissible policy class). Physical activations occur exactly at completions (D6), hence at arrival epochs only, and remove items that are physically present and assigned: the “queues suffice” requirement holds by construction, and the balance equation (1) holds in the form X(t) = N (t) − A C(t) ≥ 0, the physical activation counts being the completion counts Ck (t) := number of completed type-k matchings at epochs u < t. At most three matchings complete per epoch: by Lemma 5.5(b), for every class j, either Uj (t) = 0 or no entry of B(t) has a class-j residual; moreover every entry of B(t) is incomplete (the ΣA invariant maintained by (D6)) and the pool gains no item within the epoch besides the arrival ((D4) is the only addition; (D6) returns none), so the entries of B(t) can absorb only the single arriving item during epoch t (at most one of them completes) while at most the two entries appended in (D3) complete besides. Together with the countable internal state (Q, B) and deterministic decisions at arrival epochs, VQML satisfies conditions (a) and (b) of the policy class of Section 3. ▶ Corollary 5.1 (Regeneration identity). Pathwise from the empty start: for every t, Q(t) = 0 ⇐⇒ S(t) = ∅. In particular, for the chain started at S(0) = ∅, the return times τ∅ = inf{t ≥ 1 : S(t) = ∅} and τ0+ = inf{t ≥ 1 : Q(t) = 0} coincide almost surely, as do all successive return times. P P Proof. If Q(t) = 0 then i Q− i (t) = 0, so B(t) is empty by Lemma 5.5(c), and i Xi (t) ≤ 0 + (amax − 1) · 0 = 0 by Lemma 5.5(d), whence X(t) = 0: S(t) = ∅. The converse is the definition of ∅. The equivalence holds at every t along every trajectory from the empty start, so the hitting times of {S = ∅} and {Q = 0} coincide pathwise. ◀
F. Mathieu
17
▶ Lemma 5.6 (Transfer to the physical system). Assume (iii) and run VQML with the canonical rule of Equation (3) (or any deterministic, state-only tie-breaking rule satisfying the idle clause of Lemma 5.4).2 Then: (a) (stability) The embedded chain (S(t)) started at ∅ is irreducible on its reachable set, which is exactly the communicating class of ∅, and positive recurrent there; the continuous-time chain is positive recurrent on the same class. In particular VQML stabilizes (G, λ), and the irreducibility required of the [6, Appendix A] policy model is discharged (proven, not assumed). P (b) (rate identity) Let Mk (t) = u<t sk (u) count virtual activations and Ck (t) completed (physical) matchings of type k at epochs u < t, so that, for VQML, the balance equation (1) reads X(t) = N (t) − A C(t), the role of its physical activation counts being played by C (Remark 5.4); the symbol M is reused here for the virtual counts. Then, almost surely, for every k, lim
t→∞
Ck (t) Mk (t) = lim = µ̄k := Eπ [sk (·)], t→∞ t t
and
Aµ̄ = λ̄,
where π is the stationary law of the virtual chain on the class of 0: the physical matching rates coincide with the virtual activation rates. Per unit of continuous time, type-k matchings complete at rate Λµ̄k , with A(Λµ̄) = λ: the physical system matches all arriving items at full rate. Proof idea; details in Appendix B. By Proposition 5.2 the virtual chain is positive recurrent on the class of 0 with finite mean return time m0 , and by Corollary 5.1 the full chain returns to ∅ exactly when Q returns to 0; hence ∅ has mean return time m0 < ∞ and (S(t)) is positive recurrent on the communicating class of ∅, giving (a). For (b), a renewal–reward count over regeneration cycles identifies the physical matching rates with the virtual activation rates µ̄, and the virtual balance evaluated at regeneration times gives Aµ̄ = λ̄. ◀
5.4
Putting things together
Proof of Theorem 3.1. (ii) ⇔ (iii) is Lemma 5.1. For (iv): (iii) ⇒ (iv) is trivial (take supp(µ) = E); and (iv) ⇒ (ii) by applying Lemma 5.1, (b) ⇒ (c), to the submatrix Asupp(µ) (its columns are nonzero, and µ restricted to its support is strictly positive), since any y with ⟨y, Ak ⟩ ≥ 0 for all k ∈ E in particular satisfies it for k ∈ supp(µ), so ⟨y, λ⟩ > 0 follows. (i) ⇒ (ii) is Proposition 5.1. (iii) ⇒ (i): VQML is a policy in the admissible class (Remark 5.4), and Lemmas 5.2–5.4 and 5.6 together with Proposition 5.2 show it stabilizes (G, λ). Since VQML is defined from G alone (no knowledge of λ, no parameter) the same policy stabilizes (G, λ) for every λ satisfying (iii); by the equivalence, VQML stabilizes every stabilizable problem: it is maximally stable. ◀
2
Nonanticipating randomized state-only rules can also be handled; the extension is not needed here, so we only record the route: the pair (virtual state, randomization draw) is Markov and the Q-marginal is Markov with the averaged kernel; the drift bound Equation (4) holds for any measurable selection and Lemma 5.4 persists (Remark 5.3(a)), so Proposition 5.2 applies to the averaged chain, giving π and m0 ; Corollary 5.1 is pathwise for arbitrary decision sequences; the cycles of the augmented chain between the Q-visits to 0 are i.i.d. by the strong Markov property, and the Kac step then yields part (b) with µ̄k = Eπ [ E[sk | Q = · ] ].
18
Online stochastic matchings: stability on hypergraphs
References 1
2
3
4
5
6
7 8 9 10 11
12 13 14
15 16 17
18
19 20
Jocelyn Begeot, Irène Marcovici, and Pascal Moyal. Stability regions of systems with compatibilities and ubiquitous measures on graphs. Queueing Systems, 103(3):275–312, 2023. doi:10.1007/s11134-023-09872-0. Jocelyn Begeot, Irène Marcovici, Pascal Moyal, and Youssef Rahme. A general stochastic matching model on multigraphs. ALEA, Lat. Am. J. Probab. Math. Stat., 18(2):1325–1351, 2021. URL: http://arxiv.org/abs/2011.05169. Pierre Bremaud. Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues. Texts in Applied Mathematics. Springer-Verlag, New York, 1999. URL: https://www.springer. com/gp/book/9780387985091, doi:10.1007/978-1-4757-3124-8. Ana Bušić, Varun Gupta, and Jean Mairesse. Stability of the Bipartite Matching Model. Advances in Applied Probability, 45(2):351–378, June 2013. Publisher: Cambridge University Press. doi:10.1239/aap/1370870122. René Caldentey, Edward H. Kaplan, and Gideon Weiss. FCFS infinite bipartite matching of servers and customers. Advances in Applied Probability, 41(3):695–730, 2009. doi:10.1239/ aap/1253281061. Céline Comte, Fabien Mathieu, Sushil Mahavir Varma, and Ana Bušić. Online Stochastic Matching: A Polytope Perspective. Working paper (HAL version 6), November 2025. URL: https://hal.science/hal-03502084v6. Céline Comte. Stochastic non-bipartite matching models and order-independent loss queues. Stochastic Models, 38(1):1–36, January 2022. doi:10.1080/15326349.2021.1962352. Varun Gupta. Greedy algorithm for multiway matching with bounded regret. Operations Research, 72(3):1139–1155, 2024. Itai Gurvich and Amy Ward. On the Dynamic Control of Matching Queues. Stochastic Systems, 4(2):479–523, 2014. doi:10.1287/13-SSY097. Bruce Hajek. Hitting-time and occupation-time bounds implied by drift analysis with applications. Advances in Applied Probability, 14(3):502–525, 1982. doi:10.2307/1426671. Matthieu Jonckheere, Pascal Moyal, Claudia Ramírez, and Nahuel Soprano-Loto. Generalized max-weight policies in stochastic matching. Stochastic Systems, 13(1):40–58, 2023. doi: 10.1287/stsy.2022.0098. Süleyman Kerimov, Itai Ashlagi, and Itai Gurvich. Dynamic matching: Characterizing and achieving constant regret. Management Science, 70(5):2799–2822, 2024. Süleyman Kerimov, Itai Ashlagi, and Itai Gurvich. On the optimality of greedy policies in dynamic matching. Operations Research, 73(1):560–582, 2025. Jean Mairesse and Pascal Moyal. Stability of the stochastic matching model. Journal of Applied Probability, 53(4):1064–1077, 12 2016. Publisher: Cambridge University Press. doi:10.1017/jpr.2016.65. Jean Mairesse and Pascal Moyal. New frontiers for stochastic matching. Queueing Systems, 2022. hal-03561106. doi:10.1007/s11134-022-09832-0. Fabien Mathieu. Stochastic Matching, 2022. URL: https://balouf.github.io/stochastic_ matching/index.html. Fabien Mathieu. Online Stochastic Matchings: Stability on Hypergraphs – companion notebook. Companion page, stochastic-matching documentation, 2026. URL: https://balouf.github. io/stochastic_matching/companion/hypergraph_candy.html. Pascal Moyal, Ana Bušić, and Jean Mairesse. A product form for the general stochastic matching model. Journal of Applied Probability, 58(2):449–468, 06 2021. doi:10.1017/jpr. 2020.100. Pascal Moyal and Ohad Perry. On the instability of matching queues. The Annals of Applied Probability, 27(6):3385–3434, 2017. URL: https://arxiv.org/abs/1511.04282. Mohammadreza Nazari and Alexander L. Stolyar. Reward maximization in general dynamic matching systems. Queueing Systems, 91(1):143–170, February 2019. doi:10.1007/ s11134-018-9593-y.
F. Mathieu
21 22 23
24
25
26
Youssef Rahme and Pascal Moyal. A stochastic matching model on hypergraphs. Advances in Applied Probability, 53(4):951–980, December 2021. doi:10.1017/apr.2021.8. Alexander L. Stolyar. Maximizing queueing network utility subject to stability: Greedy primaldual algorithm. Queueing Systems, 50(4):401–457, 2005. doi:10.1007/s11134-005-1450-0. Leandros Tassiulas and Anthony Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Transactions on Automatic Control, 37(12):1936–1948, 1992. doi:10.1109/9.182479. Thirupathaiah Vasantam and Don Towsley. A throughput optimal scheduling policy for a quantum switch. In Quantum Computing, Communication, and Simulation II, volume 12015, pages 14–23. SPIE, 2022. doi:10.1117/12.2616950. Yehua Wei, Jiaming Xu, and Sophie H. Yu. Constant regret primal-dual policy for multi-way dynamic matching, 2023. Working paper. URL: https://papers.ssrn.com/sol3/papers. cfm?abstract_id=4357216. Martin Zubeldia, Prakirt R. Jhunjhunwala, and Siva Theja Maguluri. Matching queues with abandonments in quantum switches: Stability and throughput analysis. Operations Research, 74(1):339–355, 2026. arXiv:https://doi.org/10.1287/opre.2023.0032, doi:10.1287/opre. 2023.0032.
19
20
Online stochastic matchings: stability on hypergraphs
A
The steering construction: proof of the accessibility lemma
Proof of Lemma 5.4. Recall the transition mechanism: from state q the chain moves to q − As(q) + ei with probability λ̄i > 0, i ∈ V , the activation s(q) being determined by q alone, before the arrival. We exhibit, for each starting state q, an explicit arrival word of length at most ∥q∥1 + 2amax V (q) after which the chain sits at 0; since each prescribed arrival class occurs with probability at least λ̄min , independently of the past, the probability bound P follows. Write η(q) = i max(−qi , 0) for the negative mass, so that ∥q∥1 = V (q) + η(q). Step 0: three elementary facts. P (F1) If q ≤ 0 componentwise, then q is idle: each ⟨q, Ak ⟩ = i qi Ai,k is a sum of nonpositive terms. ̸ 0, then q is active: pick i with qi ≥ 1 and, the i-th row of A being (F2) If q ≥ 0 and q = nonzero, a column k with Ai,k ≥ 1; all terms of ⟨q, Ak ⟩ are nonnegative and the i-th is ≥ 1. (F3) If q is active, then every maximizer s of Equation (3) satisfies ⟨q, As⟩ = 2Ψ(q) > 0 and ∥s∥1 = 2; in particular ∥As∥1 ≥ 2. Indeed, doubling a best column, s = 2ek∗ with k ∗ ∈ arg maxk ⟨q, Ak ⟩, is feasible and scores 2Ψ(q); any s with ∥s∥1 ≤ 1 scores at most Ψ(q) < 2Ψ(q); and any s with ∥s∥1 = 2, say As = Ak + Al (possibly k = l), scores ⟨q, Ak ⟩ + ⟨q, Al ⟩ ≤ 2Ψ(q). Finally ∥Ak + Al ∥1 = ∥Ak ∥1 + ∥Al ∥1 ≥ 2, the columns being nonnegative and nonzero. Step 1: from an active state, one steered step decreases the positive mass. Let q be active, s = s(q) and r = q − As. We claim that there is an arrival class i with V (r + ei ) ≤ V (q) − 1,
while for every class j,
η(r + ej ) ≤ η(q) + 2amax .
The negative-mass bound holds for any arrival: coordinatewise, q drops by at most (As)i ≥ 0, so η(r) ≤ η(q) + ∥As∥1 ≤ η(q) + 2amax , and adding ej cannot increase η. For the positive mass, distinguish two cases. Overshoot case: rj ≤ −1 for some j. Feed i = j, so that V (r + ej ) = V (r). Now P P 0 < ⟨q, As⟩ = i qi (As)i ≤ i: qi ≥1 qi (As)i , so some class i∗ has qi∗ ≥ 1 and (As)i∗ ≥ 1; then max(ri∗ , 0) ≤ qi∗ − 1, while max(rj , 0) ≤ max(qj , 0) for every j. Summing, V (r) ≤ V (q) − 1. No-overshoot case: r ≥ 0. Then q = r + As ≥ 0, so V (q) = ∥q∥1 , and for any arrival i, using (F3), V (r + ei ) = ∥r∥1 + 1 = ∥q∥1 − ∥As∥1 + 1 ≤ V (q) − 1. Step 2: from an idle state ̸= 0, one steered step consumes one unit of negative mass at constant positive mass. Let q = ̸ 0 be idle. By (F2), q has a coordinate qj ≤ −1 (otherwise q ≥ 0, q = ̸ 0 would be active). Feed i = j: by the idle clause the transition is q 7→ q + ej , so V is unchanged and η decreases by exactly one. Note that if q ≤ 0, then by (F1) the steered chain stays idle and in the nonpositive orthant all the way up to 0. Step 3: assembly. Starting from q, repeat: stop if the current state is 0; otherwise apply the steered step of Step 1 (active state) or Step 2 (idle state). The procedure is well defined, and it terminates: V never increases and each active step decreases it by at least one, so at most V (q) active steps occur in total; each idle step decreases η by one while each active step increases it by at most 2amax , so, η being nonnegative throughout, at most η(q) + 2amax V (q) idle steps occur; an infinite run would require infinitely many idle steps. Hence the procedure stops (by construction, only at 0) after at most V (q) + η(q) + 2amax V (q) = ∥q∥1 + 2amax V (q) steps, as announced.
◀
F. Mathieu
B
Full-state bounds and transfer
Proof of Lemma 5.5. (a)+(b) by induction over epochs. At t = 0 all quantities vanish. Assume (a)–(b) at t and follow the pair (U, D) through epoch t. Step (D3) adds, for each appended entry (k, 0), a full residual Ak : D increases by A s(t) and U is unchanged. Step (D4): U increases by a(t), D unchanged. Each elementary assignment in (D5) moves one unassigned item of some class j onto some entry: Uj decreases by one and the entry’s class-j residual decreases by one, so Dj decreases by one and U − D is unchanged. Step (D6) removes entries with zero residual only, changing neither D nor U (the removed items were assigned, not unassigned). Summing, and using the induction hypothesis and (D2), U (t + 1) − D(t + 1) = U (t) − D(t) + a(t) − A s(t) = Q(t) + a(t) − A s(t) = Q(t + 1), which is (a) at t + 1. For (b), fix a class j. Along the scan (D5) the pool Uj is non-increasing. Suppose Uj (t + 1) > 0, i.e. the pool is still positive at the end of the scan, and suppose some entry of the post-scan list retained a positive class-j residual. When that entry was processed, the amount assigned to it, min(pool, residual), was strictly less than its residual, so it equaled the pool, which therefore dropped to 0 there and, being non-increasing, stayed at 0, contradicting Uj (t + 1) > 0. Hence every entry of the post-scan list, and in particular every entry of B(t + 1) (a sublist), has zero class-j residual: Dj (t + 1) = 0. This is complementarity at t + 1; since U, D ≥ 0 and Q = U − D, uniqueness of the Jordan decomposition gives U = Q+ , D = Q− . (c) Every entry of B(t) is incomplete, so ∥r(bj )∥1 ≥ 1; summing residuals over the backlog P P P and using (b), |B(t)| ≤ j ∥r(bj )∥1 = i Di (t) = i Q− (t). P P P P P i (d) i Xi = i Ui + i Wi , where i Ui = i Q+ ∥cj ∥1 = i by (b) and, per entry, P P ∥Akj ∥1 − ∥r(bj )∥1 ≤ amax − 1; hence i Wi ≤ (amax − 1) |B(t)| ≤ (amax − 1) i Q− i (t) by (c). ◀ Proof of Lemma 5.6. Virtual chain. By Lemma 5.4, the set R0 of virtual states reachable from 0 is the communicating class of 0, and by Proposition 5.2 the virtual chain restricted to it is irreducible and positive recurrent, with m0 = E0 [τ0+ ] < ∞. (a) The Q-component of (S(t)) is autonomous and starts at 0, so Corollary 5.1 gives τ∅ = τ0+ pathwise for the S-chain started at ∅, whence E∅ [τ∅ ] = m0 < ∞: ∅ is a positive recurrent state of (S(t)). Irreducibility on the reachable set: let σ be reachable from ∅, say via a finite arrival word w of positive probability, and let q be the Q-component of σ; then q ∈ R0 , and by Lemma 5.4 some finite arrival word w′ of positive probability drives the virtual chain from q to 0 (given the arrival word, the trajectory is deterministic, and every fixed word has positive probability since λ̄i > 0). Running w followed by w′ from ∅ produces a trajectory from the empty start that passes through σ and whose virtual state at time |w| + |w′ | is 0; by Corollary 5.1, its full state at that time is ∅. Hence ∅ is accessible from every reachable σ: the reachable set of S is the communicating class of ∅, the restricted chain is irreducible, and since positive recurrence is a class property, the whole class is positive recurrent, which is the stability of the embedded chain in the sense of Section 3. For the continuous-time chain: state changes occur only at the arrival epochs, which form a Poisson process of constant rate Λ whose class marks are independent of the epoch times, so the continuous-time process is the rate-Λ uniformization of (S(t)). In fact the kernel has no self-loops: Q changes at every epoch, since idle steps add ei ̸= 0 and active steps have ∥As∥1 ≥ 2; constant-rate uniformization would tolerate self-loops anyway. Pτ∅ A continuous-time return to ∅ lasts j=1 Ej with (Ej ) i.i.d. exponential(Λ) independent of the marks; by Wald’s identity its mean is m0 /Λ < ∞, so the continuous-time chain is
21
22
Online stochastic matchings: stability on hypergraphs
positive recurrent on the same class, with stationary law equal to that of the embedded chain (constant uniformization rate). (b) Let T0 = 0 < T1 < T2 < · · · be the successive visits of S to ∅, or equally the visits of Q to 0 by Corollary 5.1. By the strong Markov property the cycles S(Tj ), . . . , S(Tj+1 −1) , j ≥ 0, are i.i.d. with E[Tj+1 − Tj ] = m0 < ∞; hence Tj /j → m0 a.s. and Tj+1 /Tj → 1 a.s. Every virtually activated matching enters the backlog at (D3) and can leave it only via its completion at (D6), at most once; therefore Mk (t) − Ck (t) equals the number of type-k entries of B(t), so 0 ≤ Ck (t) ≤ Mk (t), with equality at regeneration times: Ck (Tj ) = Mk (Tj ), the backlog PTj+1 −1 (k) being empty there. The per-cycle rewards Rj := Mk (Tj+1 ) − Mk (Tj ) = u=T sk (Q(u)) j (k)
are i.i.d. with 0 ≤ Rj ≤ 2(Tj+1 − Tj ), hence E[R(k) ] ≤ 2m0 < ∞, and the renewal–reward theorem yields Mk (t)/t → E[R(k) ]/m0 =: µ̄k a.s. For j ≥ 1 and Tj ≤ t < Tj+1 , monotonicity gives Mk (Tj ) Ck (t) Mk (Tj+1 ) ≤ ≤ , Tj+1 t Tj and both bounds converge a.s. to µ̄k (using Tj+1 /Tj → 1), so Ck (t)/t → µ̄k a.s.: the physical matching rates coincide with the virtual activation rates. The identification µ̄k = Eπ [sk (·)] is the cycle representation (Kac’s formula) of the stationary law: π(q) = P P −1 (k) + 1{Q(u) = q} , so Eπ [sk ] = m m−1 E ]/m0 (Tonelli; 0 0 0 E0 u<τ0 u<τ0+ sk (Q(u)) = E[R all terms nonnegative). Finally, the virtual balance Q(t) = N (t) − A M (t) (from (D2) and Q(0) = 0, with Ni (t) the number of class-i arrivals before t), evaluated at t = Tj for j ≥ 1, gives 0 =
Q(Tj ) N (Tj ) M (Tj ) a.s. = −A −−−→ λ̄ − Aµ̄, j→∞ Tj Tj Tj
by the strong law for the i.i.d. arrival marks, whence Aµ̄ = λ̄. Multiplying by Λ and invoking the Poisson strong law converts per-epoch rates into per-time rates. ◀ ▶ Remark B.1 (Provenance, timing, and constants: relation to NS19). Steps (D3)–(D6) are Nazari–Stolyar’s completion mechanism [20, Sec. 3.3–3.4], extended verbatim to budget-two decision multisets, and Lemma 5.5(c)–(d) are the full-state analogues of the pathwise bounds of [20, Prop. 3] (arXiv-v4 numbering). We re-prove rather than import them, for three reasons. (1) Level: NS19 state their bounds for the count triple (Q, Q̂, Q̂0 ), a projection of S(t) that is not obviously Markov (future completions depend on the composition of the FIFO list, not merely on its length), whereas the stability definition refers to the full chain; the bounds are needed, and are proven here, at that level. (2) Budget: NS19’s written proof activates one matching per slot; encoding our budget-two multisets ∥s∥1 ≤ 2 as single composite matchings would roughly double the constant (to 2amax − 1), while the per-entry accounting above keeps amax − 1. (3) Timing: Equation (3) decides from Q(t) before the arrival a(t) lands (decide-then-arrive); Lemma 5.5 treats (s(t)) as an arbitrary given sequence, so the pathwise bounds are insensitive to the within-slot ordering and no alignment with NS19’s convention is required, while what Corollary 5.1 and Lemma 5.6 rest on is the pathwise coincidence of the Q-component with the chain of Equation (3) analyzed in Lemmas 5.3 and 5.4 and Proposition 5.2, which is what (D1)–(D2) under the decide-then-arrive convention deliver (an arrive-then-decide variant would also have an autonomous Q-component, but a different chain, to which those lemmas would not apply verbatim). The FIFO order and the fixed appending/scanning orders in (D3)/(D5) matter only to make the transition kernel deterministic: any eager assignment rule (one leaving no unassigned item next to an entry that needs it) preserves Lemma 5.5; FIFO is kept for definiteness and to match NS19.
F. Mathieu
C
An alternative renewal route
▶ Corollary C.1 (Confinement). For C ∈ N let n o P FC := (x, q, β) ∈ Nn × Zn × ΣA∗ : ∥q∥1 ≤ C, |β| ≤ C, x ≤ a C , i max i a finite set, of cardinality at most (amax C + 1)n (2C + 1)n (|ΣA | + 1)C . Along every trajectory from the empty start, S(t) ∈ FC ⇐⇒ ∥Q(t)∥1 ≤ C : P P + P indeed ∥Q(t)∥1 ≤ C gives i Q− i (t) ≤ C and i Qi (t) ≤ C, so |B(t)| ≤ C and i Xi (t) ≤ C + (amax − 1)C = amax C by Lemma 5.5(c)–(d); the converse is the projection on the Qcoordinate. Consequently, for the chain started at the empty state (or at any state reachable from it), the hitting-time bounds of Lemma 5.3(b) for Q are, pathwise, hitting-time bounds of the full chain (S(t)) to the finite set FM : the virtual drift analysis already controls returns of the full chain to a finite set, with no further stochastic argument. (This corollary is not needed for Theorem 3.1, whose proof goes through Corollary 5.1; it is recorded because it makes the F -return structure of the full chain explicit and supports the alternative renewal route of Remark 5.3(c).)
23