Decentralized Dynamic Stable Matching

Decentralized Dynamic Stable Matching Mengtong Gao Zhenhe Zhang jchencs@tsinghua.edu.cn {gmt25, zhenhe-z21}@mails.tsinghua.edu.cn Department of Computer Science and Technology Tsinghua University, Beijing, China

arXiv:2610.41912v1 [cs.DC] 30 Oct 2026

Jing Chen

Abstract In this work we study decentralized computing of the player-optimal stable matching (POSM) under unannounced player arrivals and departures. Without a common clock, arrival/departure events information, or direct communication, players can only make individual proposals to the arms and observe individual accept/reject outcomes. We measure the mismatch cost — the total number of rounds in which the realized matching differs from the POSM of that round, as the time horizon T grows. For known preferences, we develop a deterministic polynomial-time self-calibrating protocol that achieves a mismatch cost of O(t∗ + K 2 log T ), greatly improving the existing upper-bound O(T 1−1/K (log T )2/K ). Here K and t∗ are respectively the number of arms and the time of the last event in the problem instance. Each player individually runs the protocol based on his/her own local time and proposal-outcome history, without knowing t∗ or T . More generally, our protocol can be configured with a non-decreasing and polynomial-timecomputable function g(t) = Ω(t), so as to achieve a mismatch cost of O(g(t∗ ) + K 2 Ng (T )), where Ng (T ) counts iterations of t 7→ t + g(t) below T . Roughly speaking, g(t) reflects the protocol’s convergence speed. The relationship between g(t) and Ng (T ) highlights the tradeoff between convergence speed and asymptotic mismatch cost. We next show that any randomized protocol with a convergence speed g(t) ≥ 1 and an asymptotic sublinear mismatch cost has a worst-case expected cost of Ω(t∗ + Ng (T )). This further implies that, up to a K 2 factor, our protocol with g(t) = t is optimal among all protocols with sublinear cost and convergence speed O(t∗ ). Finally, for unknown preferences on both sides, each player and each arm individually observe their own preferences after being matched to the other side. We develop a decentralized learning protocol that achieves expected mismatch cost O(t∗ + K 4 ∆−2 min log T ), where ∆min measures the preference gaps in the learning problem. A complementary static-setting lower bound adapted from the literature establishes that the dependencies on T and ∆min are tight.

Keywords: stable matching; decentralized algorithm; dynamic matching market; multi-arm bandit.

1

Introduction

Classical studies of two-sided matching markets focus on computing a stable matching for a fixed set of participants. When preferences are known, player-proposing deferred acceptance (DA) computes the player-optimal stable matching (POSM), which assigns to each player its most preferred arm among all stable matchings [GS62]. In dynamic markets, player arrivals and departures may change the POSM. Without any notification of these changes, remaining players may continue being matched to their previously assigned arms, even when the resulting matching is no longer the current POSM. In this work, we study decentralized protocols for maintaining the POSM under such changes, where each player acts on its own local clock and proposal-outcome history. We measure the cumulative mismatch cost by the number of rounds in which the realized matching differs from the POSM of that round, as the time horizon T grows. As a toy example, consider two players p, q and two arms a, b. Both players prefer a to b, arm a prefers p to q, and arm b prefers q to p. With both players present, the POSM assigns p to a and q to b. If p departs, the new POSM should have assigned q to a, but player q continues to be accepted when proposing to b. In fact, as long as q continues proposing to b, it receives the same acceptance outcome whether p stays or departs. To distinguish the two cases, therefore, q must propose to a, which disrupts the correct matching if p is still present. This creates a trade-off between recovery from hidden departures and maintenance of a correct matching in a static scenario where the population doesn’t change. Besides detecting population changes, players must also coordinate in a decentralized manner when computing the POSM. They may have different arrival times and local states, without a common clock, population roster, or direct communication. Consequently, coordination must be achieved through individual proposals and accept/reject outcomes. To tackle these problems, our approach alternates between deferred acceptance and replay of the resulting matching, using only a player’s local information to schedule subsequent computation.

1.1

Our Contributions

Dynamic matching with known preferences. We develop Self-Calibrating Deferred Acceptance (SC-DA), a deterministic decentralized protocol for maintaining the POSM when preferences are known. With K arms and finitely many player arrivals and departures, SC-DA achieves cumulative mismatch cost O(t∗ + K 2 log T ), where T is the time horizon and t∗ is the last population-event time. Using only each player’s local clock and proposal-outcome history, the protocol coordinates deferred acceptance computations and calibrates replay lengths without requiring any player to know T or t∗ . Recovery–mismatch trade-off. More generally, SC-DA can be configured with a recovery scale function g, yielding different guarantees on convergence speed and asymptotic mismatch cost. We establish an information-theoretic lower bound on the cost of maintaining the POSM. Any protocol with sublinear mismatch cost relative to g incurs Ω(Ng (T )) expected cumulative mismatch in the worst case, even when the market remains static. For the linear choice g(t) = t, our dynamic lower bound further establishes the asymptotic optimality of SC-DA up to a factor K 2 . Dynamic matching with two-sided learning. We develop Self-Calibrating Preference Certification (SC-PC), a decentralized protocol for maintaining the POSM when both players and arms must learn their preferences. SC-PC achieves expected cumulative mismatch O(t∗ +K 4 ∆−2 min log T ), where ∆min denotes the minimum relevant preference gap in the final market, as defined in Section 5.1. A 2

lower bound adapted from prior work shows that the dependence on T and ∆min is tight even in static markets.

1.2

Related Work

Dynamic matching markets. Dynamic matching has been studied under evolving preferences and rewards, with objectives including the number of blocking pairs, changes between stable matchings, and nonstationary regret [KLM16, BCK+ 20, GSR+ 24, MMKS23]. Closest to our setting, [GZL+ 26] study decentralized matching bandits with unannounced player arrivals and departures and no global clock. The Way-SE-2S algorithm uses a Restless Ping mechanism to probe arms that may become attainable following hidden departures and achieves per-player POSM regret with horizon dependence O(T 1−1/K (log T )2/K ) under two-sided learning. Building on this setting, we isolate the coordination and recovery challenges caused by population changes from preference learning, and develop a self-calibrating mechanism that addresses these challenges with POSM mismatch in the known-preference setting and extends to two-sided learning. Recovery and maintenance in distributed protocols. A central question in distributed computing is how quickly correctness can be restored after changes and how long it can be maintained. Dynamic size-counting protocols study convergence and holding times under adversarial population changes [DE22, KL24], while loosely-stabilizing leader election establishes a tight trade-off between these times [SEIM21]. For matching, self-stabilizing stable-marriage algorithms recover stable matchings from arbitrary configurations [LMB+ 17, BBB+ 18], and dynamic maximal-matching algorithms bound cumulative incorrect rounds with topology-change notifications and message passing [CHDK+ 21]. Silent-failure monitoring separately studies the trade-off between probing overhead and detection delay [CHK+ 14]. In our setting, departures are unannounced, and detecting them requires proposals that may disrupt the POSM even when the market remains static, directly coupling recovery requirements with cumulative mismatch. Learning in matching markets. Bandit matching markets study preference learning through repeated interactions [LMJ20]. For player-side learning in static markets, decentralized approaches differ in their feedback and coordination mechanisms, including publicly observed matching outcomes [LRMJ21, KL23, KWL24], phase-based exploration [BSS21], and deliberate collision-based communication [ZWF22]. Coordination-free learning has been studied under structural assumptions on preferences [MSM22] and through game-theoretic dynamics [ES25]. For two-sided preference learning, existing methods employ player indexing and coordinated exploration [PG24, ZF24], or use super-stability to certify stable matchings from partial preference rankings [Bas25]. Completely uncoupled trial-and-error learning has also been studied with noiseless utility feedback [SFM25]. Our work combines two-sided preference learning with unannounced player arrivals and departures, using local feedback to maintain the current POSM while controlling cumulative mismatch.

2

Preliminaries

2.1

Dynamic Market and Stable Matchings

We consider a dynamic two-sided matching market with K ≥ 2 fixed arms, indexed by K = {0, . . . , K − 1}, where K is publicly known. Time proceeds in discrete rounds t = 1, 2, . . .. Each player i enters at round bi ≥ 1 and departs at round di > bi , with di = ∞ if the player never leaves. The set of active players at round t is Pt = {i : bi ≤ t < di }, and |Pt | ≤ K for all t. We 3

consider markets with finitely many player arrivals and departures. Counting the initial market as a population event in round 1, we denote the last population-event time by t∗ . Both sides have complete, strict preference rankings over the other side, represented by fixed true utilities. For each player i, the utility of arm k is µi,k ∈ [0, 1]; for each arm k, the utility of player i is πk,i ∈ [0, 1]. Their preferences satisfy k ≻i ℓ ⇐⇒ µi,k > µi,ℓ ,

i ≻k j ⇐⇒ πk,i > πk,j .

All agents prefer any partner to remaining unmatched. We write ranki (k) and rankk (i) for the corresponding preference ranks, with rank 1 being the most preferred. Let pi (r) denote player i’s arm of rank r. Each arm’s ranking is defined over all players that participate at any time in the instance. At each round t, a matching m consists of disjoint player–arm pairs from Pt × K. We write m(i) for player i’s assigned arm, with m(i) = ⊥ when i is unmatched. A pair (i, k) is a blocking pair of m if player i and arm k prefer each other to their respective partners under m. A matching is stable if all active players are matched and no blocking pair exists. Among all stable matchings at round t, the POSM, denoted by m∗t , assigns each active player its most preferred arm attainable in any stable matching: µi,m∗t (i) ≥ µi,m(i)

for every stable matching m and every i ∈ Pt .

The POSM is unique and can be computed by player-proposing deferred acceptance [GS62].

2.2

Decentralized Protocol Model

A decentralized protocol specifies how players make proposals and how arms respond, using only locally available information. In each round t, every active player proposes to exactly one arm. Each arm observes its proposers and accepts one if the proposal set is nonempty; all other proposers are rejected. The accepted player–arm pairs form the realized matching Mt . Upon entry, player i initializes its local state and sets its local clock to 0. Its local age in round t is ai = t − bi . Active players retain their local states across population changes. Each player observes whether its proposal is accepted or rejected (A/R) and, when accepted, its realized utility. Neither players nor arms have access to a global clock. Players cannot observe the active player set Pt or other players’ actions and feedback. No direct communication, population-event notification, or public reset is available. In the known-preference setting, each player i knows its true utilities {µi,k }k∈K , and each arm knows its true utilities {πk,i }i . Each arm accepts its highest-ranked current proposer; the rule uses no interaction history. In the two-sided learning setting, both players and arms initially lack knowledge of their own true utilities and preference rankings. When player i is matched with arm k, both sides observe their respective stochastic utilities in [0, 1]. Conditional on the complete interaction history and the current proposals and acceptance decisions, their expected utilities are µi,k and πk,i , respectively. Rejected proposals yield no utility observations. Each arm recognizes returning proposers through private handles with a fixed local ordering and maintains its own local clock and interaction history. Its acceptance decisions may depend on these records.

2.3

Tracking Objective and Performance Measure

An instance I specifies both sides’ true utilities and a population path fixed independently of the protocol’s randomization and utility observations. In the two-sided learning setting, I also specifies the conditional distributions of utility observations, subject to the assumptions above. 4

For a protocol Π and an integer time horizon T ≥ 1, we define the cumulative POSM mismatch cost as DΠ (T ; I) =

T X

1{Mt ̸= m∗t }.

(1)

t=1

We write D(T ; I) when the protocol is clear. This cost counts rounds in which the realized matching differs from the POSM of that round, whereas binary stable regret [Bas25] counts rounds in which the matching is not stable. When utility observations or protocol decisions are random, we consider the expected mismatch cost E[DΠ (T ; I)]. The protocol’s decision rules are fixed before the instance and horizon are chosen; agents are not given T or t∗ .

3

Dynamic Matching with Known Preferences

After a population change, players that remain active may continue to be accepted by their previously assigned arms even when the resulting matching is no longer the current POSM. We introduce Self-Calibrating Deferred Acceptance (SC-DA), which combines coordinated computation of the POSM via deferred acceptance with replay of the resulting matching. Each player calibrates its replay length using its own local clock, enabling recovery from unannounced population changes while limiting cumulative mismatch.

3.1

The Self-Calibrating Deferred Acceptance Protocol

To compute the POSM, SC-DA coordinates players with different arrival times and local states. Priority competition at a designated arm allows one player to initiate a sweep across all arms. In a fixed market, a successful sweep initiates a coordinated computation of the POSM using player-proposing deferred acceptance. Since the computation phase has the same duration for every player, the offsets between their entry times into this phase are preserved at completion. After computation, each player saves its output arm and repeatedly proposes to it until a rejection or its replay deadline triggers another coordination attempt. Subsequent computations are scheduled through self-calibration. Each player uses its own clock and the age recorded at its preceding computation output to count the rounds since that output and set its next replay length. SC-DA uses four player-local modes: Replay, Seek, Sweep, and Work. In Replay, a player repeatedly proposes to its saved arm. Seek and Sweep coordinate active players for the next computation, while Work performs the matching computation and updates the replay length and deadlines. Each newly arriving player starts in Seek. Figure 1 illustrates the state transitions, and Algorithm 1 specifies the player-local rules. We designate arm 0 as BUS for coordinating players and arm 1 as PARK for the initial stage of matching computation. For each player i, let TOPi = pi (1) denote its most preferred arm. The protocol sets J = K 2 + 5K + 1, H = 4J + 4. (2) Here J determines the duration of Work and the number of consecutive BUS acceptances required to enter Sweep, while H specifies the minimum replay length. Replay. In Replay, a player repeatedly proposes to its saved arm y. A rejection causes it to enter Seek in the next round, whereas reaching its replay deadline q causes it to enter Seek at the start of that round (Lines 22–23 and 13–14, respectively, in Algorithm 1). The deadline ensures periodic computation even when the player continues to be accepted by its current arm. 5

Seek. A player in Seek repeatedly proposes to BUS. In a fixed market, we call the active player most preferred by BUS the root. Priority competition at BUS allows the root to accumulate consecutive acceptances and eventually enter Sweep. Each player maintains a counter ρ, initially zero and capped at J, recording consecutive BUS acceptances. An accepted BUS proposal increments ρ up to J, while a BUS rejection or a proposal to another arm resets it to zero. The counter is updated in every mode and preserved across mode transitions. (Lines 21 of Algorithm 1). At the start of a round, a player in Seek with ρ = J enters Sweep (Lines 16–17 of Algorithm 1). On entering Seek, a player clears its rejection flag, which is set upon receiving a BUS rejection. Once the flag is set, two consecutive BUS acceptances trigger an AA handoff, and the player enters Work in the following round (Lines 24–27 of Algorithm 1). Sweep. A player entering Sweep repeatedly executes 2K-round blocks, each with the proposal sequence σ = (0, 1, 0, 2, . . . , 0, K − 1, 0, 0). (3) A rejection at BUS causes the player to return to Seek in the next round. A rejection at a non-BUS arm marks the current block as unsuccessful; the player completes the block and starts a new one unless rejected at BUS. If every proposal in a block is accepted, the player enters Work in the following round (see SweepFeedback, called in Line 29 of Algorithm 1). The sweep visits every arm while leaving BUS for only one round at a time. A successful block also brings players in Replay back to Seek, preparing them for the next coordinated computation. Work. A player enters Work following either an AA handoff or a successful sweep. Each Work invocation lasts exactly J rounds and consists of three consecutive stages: Park, Top, and DA (see SelectArm in Algorithm 1). In Park, the player proposes to PARK for 2K rounds, leaving BUS available for other players to enter Work. In Top, it proposes to its first-choice arm TOPi for the next 2K + 1 rounds. When players enter Work at staggered two-round offsets, their Top stages share a round in which all players propose to their first-choice arms. In DA, the player uses an application index k, initially 1, to propose to arm pi (k) for the remaining J − 4K − 1 rounds. Upon acceptance, it continues proposing to the same arm. After a rejection in a nonfinal DA round, it increases k by one, capped at K (Lines 36–37 of Algorithm 1). These repeated proposals implement the application and rejection steps of deferred acceptance. In the final Work round, regardless of the feedback, the player records its proposed arm as the computation output y and updates L = H + 2(a − ℓ),

q = a + L,

ℓ ← a,

(4)

where a is its current local age and ℓ is the age of its preceding Work completion, initially zero. The update uses the previous value of ℓ. The player enters Replay in the following round (Lines 32–34 of Algorithm 1). Section 3.2 establishes the performance guarantees and extends the analysis to more general convergence speeds.

6

Algorithm 1 SC-DA 1: Input: Arms K = {0, . . . , K − 1}, K ≥ 2; player i’s strict ranking pi (1), . . . , pi (K). 2: Parameters: BUS ← 0; PARK ← 1; J ← K 2 + 5K + 1; H ← 4J + 4. 3: Initialization: a, ℓ, ρ ← 0; m ← Seek; ν ← none; seenR ← false. 4: while player i is active do 5: if ν ̸= none then ▷ Apply scheduled transition. 6: m ← ν; ν ← none 7: if m = Seek then 8: seenR ← false 9: else if m = Work then 10: h ← 0; k ← 1 11: end if 12: end if 13: if m = Replay and a ≥ q then 14: m ← Seek; seenR ← false 15: end if 16: if m = Seek and ρ = J then 17: m ← Sweep; s ← 1; blockOK ← true 18: end if 19: x ← SelectArm(m) 20: Propose to x; observe z ∈ {A, R}. (

min{J, ρ + 1}, x = BUS and z = A, 0, otherwise. 22: if m = Replay and z = R then 23: ν ← Seek 24: else if m = Seek and z = R then 25: seenR ← true 26: else if m = Seek and z = A and seenR ∧ ρ ≥ 2 then 27: ν ← Work ▷ AA handoff. 28: else if m = Sweep then 29: SweepFeedback(x, z) 30: else if m = Work then 31: if h = J − 1 then 32: y←x ▷ Save even if rejected. 33: L ← H + 2(a − ℓ) ▷ Use previous output time. 34: q ← a + L; ℓ ← a; ν ← Replay 35: else 36: if h > 4K and z = R then 37: k ← min{k + 1, K} 38: end if 39: h←h+1 40: end if 41: end if 42: a ← a + 1 43: end while 21:

3.2

ρ←

SelectArm(m) Input: m and local y, s, h, k, as used below. Return: The arm specified below. y m = Replay BUS m = Seek σs m = Sweep For m = Work: PARK 0 ≤ h < 2K pi (1) 2K ≤ h ≤ 4K pi (k) 4K < h < J σ = (0, 1, 0, 2, . . . , 0, K − 1, 0, 0). In Work: Park lasts 2K rounds, Top 2K + 1, and DA K 2 + K.

SweepFeedback(x, z) Input: x, z and local s, blockOK . Updates (in place): s, blockOK , ν. A BUS rejection skips all block tests, including at s = 2K; other rejections do not interrupt the block. if x = BUS and z = R then ν ← Seek else blockOK ← blockOK ∧ (z = A) if s < 2K then s←s+1 else if blockOK then ν ← Work else s ← 1; blockOK ← true end if end if

Performance Upper Bounds

We first establish the cumulative mismatch guarantee of SC-DA under known preferences.

7

Figure 1: Player-Local State Transitions of SC-DA. The four player-local modes and the three stages of WORK are shown. Feedback-triggered transitions take effect in the next round. Theorem 1 (Cumulative Mismatch of SC-DA). For every K ≥ 2, every legal finite-event instance I in the known-preference setting with last population-event time t∗ , and every T ≥ 1, SC-DA satisfies D(T ; I) = O(t∗ + K 2 log T ). In a fixed nonempty market, suppose that two coordinated computations give consecutive actual outputs to every player, with each player’s output offset from the root unchanged between the two computations. Let o1 < o2 be the root’s output rounds and let δi be player i’s common output offset in the two computations. Let a′i and ai denote player i’s local ages at the first and second outputs, respectively. Using its entry round bi , we have a′i = o1 + δi − bi ,

ai = o2 + δi − bi , ′ ai − ai = (o2 + δi − bi ) − (o1 + δi − bi ) = o2 − o1 . Thus the elapsed time between the two outputs is the same for every player. Since the outputs are consecutive in each player’s actual history, the old register satisfies ℓi = a′i at the second output. The replay update in (4) therefore gives all players the same replay length using only their local output histories. The same equality of replay lengths holds when all players apply a common function to a−ℓ. More generally, let g : N≥1 → N≥1 be nondecreasing and polynomial-time computable with g(t) = Ω(t). Here g specifies the desired convergence speed. Define s0 = H,

sj+1 = sj + g(sj )

(j ≥ 0),





Fg (x) = H + 2x + max {g(sj ) − sj : j ≥ 0, 64sj ≤ x} ∪ {0} ,

x ≥ 1.

(5)

Define Πg by replacing only the replay-length assignment in (4) and Line 33 in Algorithm 1 with L ← Fg (a − ℓ). When g(t) = t, we have Fg (x) = H + 2x, so Πg coincides with SC-DA. The next two lemmas connect the calibration identity to the protocol’s execution. Lemma 1 guarantees the two computations needed for calibration. To state its recovery bound, define ΨFg (x) = x + Fg (x + H) + 3H. Lemma 2 then shows that subsequent maintenance preserves calibration. Their proofs appear in Appendices A.4 and A.5, respectively. 8

Lemma 1 (Recovery and Calibration). For every legal finite-event instance I with last populationevent time t∗ and a nonempty final market, Πg produces two coordinated computations of the final POSM, both initiated after t∗ . Each player’s outputs are consecutive in its actual output history and have the same offset from the root’s output in both computations. Let Vcal be the round when all active players have entered Replay after the second computation. At this round, their replay lengths agree and the realized matching equals the final POSM, with t∗ < Vcal ≤ Ψ◦3 Fg (t∗ + 1). The players’ global replay deadlines retain the output offsets because their replay lengths agree. After this calibration, a maintenance window begins at the root’s replay deadline and ends when all active players have returned to Replay after the next computation. Lemma 2 (Maintenance after Calibration). Starting from the calibration in Lemma 1, each maintenance window of Πg produces every player’s next actual output in a coordinated computation of the final POSM, preserving the fixed output offsets and a common replay length. The matching equals the final POSM outside these windows, each lasting O(K 2 ) rounds uniformly over g and I. The common replay lengths L0 , L1 , . . ., starting with the calibrated length L0 , satisfy L0 ≥ H,

Lj+1 ≥ Fg (Lj )

(j ≥ 0).

To bound the number of maintenance windows, define r0 = 2,

Ng (T ) = #{j ≥ 0 : rj < T }.

rj+1 = rj + g(rj ),

(6)

Lemma 3 (Properties of the Replay Rule Fg ). For every K ≥ 2 and every g as above, the rule Fg is nondecreasing and polynomial-time computable, satisfies Fg (x) ≥ H + 2x, and, for all t, T ≥ 1, 



2 Ψ◦3 , Fg (t + 1) = O g(t) + K

#{j ≥ 0 : Fg◦j (H) < T } = O(Ng (T )) .

The first implied constant may depend on g; the second is absolute. The proof appears in Appendix A.6. Combining the three lemmas yields the following guarantee. Theorem 2 (Cumulative Mismatch of Πg ). For every K ≥ 2 and every function g satisfying the conditions above, there exists a deterministic decentralized matching protocol Πg such that, for every legal finite-event instance I in the known-preference setting with last population-event time t∗ , and every T ≥ 1,   DΠg (T ; I) = O g(t∗ ) + K 2 Ng (T ) . (7) Proof of Theorems 1 and 2. We first prove Theorem 2 for the protocol Πg defined above. If the final market is empty, no mismatches occur after t∗ . Thus DΠg (T ; I) ≤ min{T, t∗ } = O(g(t∗ )), since g(t) = Ω(t). For a nonempty final market, Lemmas 1 and 3 give Vcal = O(g(t∗ ) + K 2 ). If T < Vcal , then DΠg (T ; I) ≤ T < Vcal . Otherwise, charge at most Vcal for all rounds before calibration. After calibration, Lemma 2 guarantees that mismatches occur only during maintenance windows, each lasting O(K 2 ) rounds. Let oj be the root’s output round for the common replay length Lj , and let Qj = oj + Lj be the global starting round of the corresponding maintenance window. By Lemma 2 and the monotonicity of Fg , we have Lj ≥ Fg◦j (H). Any maintenance window contributing to the first T rounds must satisfy Fg◦j (H) ≤ Lj < Qj ≤ T. 9

Lemma 3 therefore bounds the number of these windows by O(Ng (T )). Since each window contributes O(K 2 ) mismatches, including an unfinished last window, we obtain 



DΠg (T ; I) = O g(t∗ ) + K 2 [1 + Ng (T )] . For T ≥ 3, we have Ng (T ) ≥ 1, which absorbs the additional K 2 term. For T = 1, 2, the desired bound follows directly from DΠg (T ; I) ≤ T and g(t∗ ) ≥ 1. This proves Theorem 2. Finally, taking g(t) = t gives SC-DA. Since rj = 2j+1 , we have Ng (T ) = O(log T ), establishing Theorem 1.

4

Lower Bounds and Optimality

Detecting an unannounced departure may require proposals that disrupt an otherwise correct matching. We formalize the resulting recovery requirement, establish the necessary mismatch cost, and characterize optimal static maintenance. Throughout this section, we consider the known-preference setting, where each arm accepts its most preferred proposer in every round.

4.1

Recovery and Necessary Mismatch

For a protocol Π and a legal finite-event instance I with last population-event time t∗ , define LΠ (h; I) = E[DΠ (t∗ + h; I) − DΠ (t∗ ; I)] ,

h ≥ 1.

(8)

This is the expected mismatch in rounds t∗ + 1, . . . , t∗ + h, after the last population event. Players that remain active across the event retain their actual states. Definition 1 (Sublinear mismatch cost relative to g). Let g : N≥1 → N≥1 be nondecreasing. A decentralized matching protocol Π has sublinear mismatch cost relative to g if, for every ε ∈ (0, 1), there is a constant cε > 0 such that, for every legal finite-event instance I with last population-event time t∗ and every h ≥ cε g(t∗ ), LΠ (h; I) ≤ ε. h Intuitively, g specifies the required convergence speed: g(t∗ ) controls the length of the post-event window needed to make the expected fraction of mismatched rounds small. For each ε, the same coefficient cε must work for every legal instance. The condition still allows mismatches caused by later maintenance. Corollary 1 (Recovery of flexible SC-DA). For every K ≥ 2 and every nondecreasing, polynomialtime computable g : N≥1 → N≥1 with g(t) = Ω(t), the protocol Πg in Theorem 2 has sublinear mismatch cost relative to g. This follows by bounding recovery and subsequent maintenance within each post-event window; the proof is in Appendix A.7. In particular, the original SC-DA satisfies the condition for the linear function g(t) = t. The lower bound requires only that g be a nondecreasing positive integer function. For such functions, use the same recurrence (6) to define Ng (T ). Theorem 3 (Necessary mismatch cost). For every K ≥ 2, every nondecreasing g : N≥1 → N≥1 , and every legal randomized adaptive protocol Π with sublinear mismatch cost relative to g, the following bounds hold. 10

There is a two-player static instance I0 , such that EDΠ (T ; I0 ) = Ω(Ng (T ))

(T → ∞).

For every t∗ ≥ 2, there exists a dynamic instance I ′ with last population-event time t∗ such that, for every T ≥ t∗ , (9) EDΠ (T ; I ′ ) = Ω(t∗ + Ng (T )) . Proof idea. We use a two-player market where detecting a hidden departure requires trying the other player’s arm, causing a mismatch if nobody leaves. The recovery requirement limits how long these tests can be postponed, yielding the static bound. For the dynamic bound, population changes first force transient mismatches, after which the same argument forces maintenance costs in the final fixed market. Both costs therefore arise on the same instance. The full proof appears in Section B.1. For every fixed function g covered by Theorem 2, the constructed protocol Πg achieves worst-case static mismatch Θ(Ng (T )) as T → ∞. Theorem 3 gives a matching Ω(Ng (T )) lower bound for every fixed protocol satisfying Definition 1. For the linear function g(t) = t, the dynamic lower bound in Theorem 3 matches the dependence on t∗ and T achieved by SC-DA in Theorem 1, for fixed K, t∗ ≥ 2, and T ≥ t∗ .

4.2

Representative Functions

Table 1 gives the iteration count Ng (T ) for representative functions. Function g(t), t ≥ 1

Ng (T ), as T → ∞

t t(1 + ⌊log t⌋) δ t 2⌊(⌊log t⌋) ⌋ , 0 < δ < 1 ⌈tα ⌉, α > 1 δ t 2⌊(⌊log t⌋) ⌋ , δ > 1

Θ(log T ) Θ(log T / log log T ) Θ((log T )1−δ ) Θ(log log T ) Θ(log log log T )

Table 1: Iteration counts Ng (T ) for representative functions g. For fixed K and g, these give the optimal static maintenance orders. All logarithms in the table are base two. All shape parameters in the table are fixed rational numbers. The five functions are nondecreasing, polynomial-time computable1 , and satisfy g(t) ≥ t, as shown in Section B.2. Thus Theorems 2 and 3 establish their optimal static maintenance orders. Beyond these representative functions, the iteration count satisfies the following asymptotic relations for nondecreasing integer-valued functions g with g(t) = Ω(t): g(t) = t1+o(1) g(t) = t

=⇒

Ng (T ) = ω(log log T ),

α>1

=⇒

Ng (T ) = Θ(log log T ),

g(t) = tω(1)

=⇒

Ng (T ) = o(log log T ).

α+o(1)

,

(10)

The proofs of these relations and the table entries appear in Section B.2. 1 Although g(t) = 2t is not polynomial-time computable from binary t, it is computable in linear time from the unary input 1t . The corresponding protocol updates take time polynomial in the player’s elapsed local time.

11

5

Dynamic Matching with Two-Sided Learning

5.1

Setting and Guarantee

We now consider the two-sided learning setting, where both players and arms initially lack knowledge of their own true utilities and preference rankings. We introduce Self-Calibrating Preference Certification (SC-PC), which combines local coordination with learning from accepted interactions to maintain the POSM under population changes. We use the model of Section 2.2, with fixed strict preferences induced by the utility means and a population path independent of rewards and protocol randomness. Accepted rewards lie in [0, 1] with fixed means conditional on the past and current proposals and acceptance decisions; rejections give no samples. Each agent runs SC-PC using only K, its own local clock, and its local observations. Arms retain their own private handles and statistics and follow the stateful service in Section C.1, which may accept lower-utility requesters for sampling. Section 5.2 explains the protocol’s design and local behavior; Appendix C.2 gives the complete local algorithms. For a nonempty final population P∞ , let m∗ be its POSM and set Ei∗ = {x ∈ K : µi,x ≥ µi,m∗ (i) }. The minimum relevant gap is 

∆min = min {1} ∪ {µi,x − µi,z : i ∈ P∞ , x ∈ Ei∗ , z ∈ K, µi,x > µi,z } 

∪ {|πx,i − πx,j | : i, j ∈ P∞ , i ̸= j, x ∈ Ei∗ ∩ Ej∗ } .

(11)

Empty comparison families are omitted. Strict preferences give ∆min > 0. Using the minimum over all final-market comparisons gives a weaker bound. Theorem 4 (Two-sided learning and dynamic POSM matching). Under this setting, fix K ≥ 2 and any legal finite-event instance I with at most K active players per round and last population-event time t∗ . For every integer T ≥ 1, if the final population is nonempty, SC-PC satisfies 



ED(T ; I) = O t∗ + K 4 ∆−2 min log T . The bound holds with the same constant for all admissible parameters, instances, and reward processes. Neither T , t∗ , nor ∆min is an input. If the final population is empty, then D(T ; I) ≤ min{T, t∗ }. The complete proof of Theorem 4 is given in Appendix C.7. For the statistical lower bound, call a protocol uniformly efficient if its decision rules are fixed without the unknown means and it has ED(T ; I) = o(T α ) for every α > 0 on every fixed static strict Bernoulli instance. In the following claim, log denotes the base-two logarithm. Claim 1 (Static statistical lower bound). Fix K ≥ 2 and 0 < ∆ ≤ min{1/8, 1/[4(K − 1)]}. There is a static K-player instance I, depending only on K, ∆, with a unique stable matching and ∆min = ∆, such that every uniformly efficient protocol Π satisfies EDΠ (T ; I) K −1 ≥ . T →∞ log T 4∆2

lim inf

By Theorem 4, SC-PC has O(log T ) expected mismatch on every fixed static strict Bernoulli instance and is therefore uniformly efficient. Static instances are legal dynamic instances. Thus, for fixed K, its upper bound matches the logarithmic horizon and inverse-square gap orders required on this family, with T → ∞ taken for each fixed ∆. No optimality in K is claimed. The construction and change-of-measure proof [KCG16], together with the comparison with binary-stability bounds [Bas25], appear in Appendix D. 12

5.2

Protocol Overview and Design Rationale

SC-PC retains SC-DA’s collection-work-replay structure. With unknown preferences, a rejection need not reveal a true preference comparison. Both endpoints therefore accumulate evidence from every acceptance across all modes. Confidence comparisons retain options not yet ruled out as best; under valid comparisons, a singleton certifies the best option in the current set. Player modes. Seek uses BUS feedback to enter Work or Root. Root clears earlier work and gathers replaying players for a new computation. During Work, players explore unresolved comparisons, hold certified arms, and remove arms only under the prescribed rejection rule. Replay repeats the final actual work proposal. Every output updates a persistent replay scale from local output intervals. The next replay uses this scale if the final request to a held arm is accepted, and a minimum grace otherwise. Rejection may shorten the deadline subject to that grace, and expiry returns the player to Seek. Arm service and safe deletion. Every arm, including BUS and PARK, uses Control service to support coordination through a fixed private priority order, and Business service to sample among confidence candidates. In either state, it accepts the eligible requester whose last acceptance is oldest; transitions depend only on requests and its local clock. During coordinated work in a fixed market with valid comparisons, this service and the spacing of exploratory requests ensure that each permitted deletion has a witness: another holder whom the arm prefers to the deleting player. Thus no stable-matching edge is deleted, and distinct held arms for all players yield the POSM. Appendix C.1 gives the precise rules and Appendix C.2 their pseudocode. Learning progress and cost. Along a consecutive episode chain in the final market satisfying the coordination and confidence conditions in Appendices C.3 and C.4.1, failed episodes add permanent samples, limiting their number to O(∆−2 min log T ), while replay-scale growth limits successful ones to O(log T ). Each interval between coordinated replays costs O(K 4 ) mismatches. Concentration and recovery from histories affected by statistical errors control the remaining expected cost, yielding Theorem 4.

AI Methodology We used ChatGPT and Codex for manuscript preparation and consistency checks throughout the paper, as well as for technical discussions and mathematical checks of the algorithms and theoretical analyses. The authors take full responsibility for the correctness, originality, and integrity of the paper, including all proofs and references.

13

A

Analysis of SC-DA

This appendix proves Lemmas 1 to 3 and Corollary 1. We first establish matching correctness and calibration for mature executions, then prove recovery and bounded maintenance under a general replay rule. We finally verify the properties of the rule Fg defined in (5) and prove its post-event guarantee. Fix K ≥ 2, with J = K 2 + 5K + 1 and H = 4J + 4 as in Algorithm 1. For the analysis, allow any nondecreasing computable replay rule F : N≥1 → N≥1 satisfying F (x) ≥ H + 2x

(x ≥ 1).

(12)

Keep all control rules unchanged. At every actual output, with final proposed arm y, replace only the replay-length update by L ← F (a − ℓ),

q ← a + L,

ℓ ← a.

(13)

The update uses the old ℓ, even if the output is incorrect or the final proposal is rejected. The original SC-DA uses F (x) = H + 2x. The protocol Πg uses F = Fg ; the required properties of Fg are verified in Appendix A.6.

A.1

Local Protocol Rules

We use Algorithm 1 with the replay update in (13) and record the local conventions used below. A player’s persistent state consists of its preference ranking, local age a, saved arm y, previous output age ℓ, and BUS-acceptance counter ρ. At birth, a = ℓ = ρ = 0,

m = Seek.

(14)

The pending mode ν and rejection flag seenR are initially none and false, respectively; mode-specific registers are initialized on entry. Round order and mode entry. Population events occur first and are not announced to players. Before proposing, each player applies its pending mode change and clears ν, checks expiration of its Replay deadline q, and checks sweep qualification, in that order. Expiration at a ≥ q returns the player to Seek; qualification applies only in Seek with ρ = J. Thus expiration can lead to Sweep in the same round, while qualification never interrupts Work. The player then makes one proposal, updates ρ, processes feedback in its current mode, and increments a. Feedback-triggered mode changes take effect next round. Round-start states below are taken after these checks and before proposals. Mode entry preserves a, y, ℓ, ρ. A fresh Seek visit clears seenR; Sweep starts with s = 1 and blockOK = true; Work starts with h = 0, k = 1; and Replay retains the deadline computed at output. Only an actual output changes ℓ. BUS feedback and replay. In every mode, an accepted BUS proposal sets ρ ← min{J, ρ + 1}; every other proposal resets ρ to zero, even after saturation. In Seek, the player proposes to BUS: a rejection sets seenR = true, and an acceptance with this flag set and updated ρ ≥ 2 schedules Work through an AA handoff. In Replay, the player proposes to y; acceptance leaves the deadline unchanged, while rejection schedules Seek.

14

Sweep blocks. Each block follows the 2K-entry scan word (3). A BUS rejection schedules Seek and skips every block-completion test, including at s = 2K. A non-BUS rejection marks the block as failed but does not interrupt it. At completion, an all-accepted block schedules Work; otherwise, a new block starts next round. Thus a continuing sweep leaves BUS only for isolated one-round gaps, including across failed-block restarts. Work and output. A Work invocation lasts exactly J rounds, indexed by h = 0, . . . , J − 1. It proposes to PARK in Park for h < 2K, to pi (1) in Top for 2K ≤ h ≤ 4K, and to pi (k) in DA for 4K < h < J. Only a rejection in a nonfinal DA round advances k, capped at K. The final round saves the actual proposed arm and performs (13), then schedules Replay. The argument of F is always positive: the first output has ℓ = 0 and a ≥ J − 1 > 0, and later outputs occur at strictly greater local ages than the output recorded in ℓ.

A.2

Correctness and Calibration of Mature Executions

For this subsection, fix a nonempty market of n ≤ K players, labeled 1, . . . , n in decreasing priority at BUS. Player 1 is the root, and m∗ is the market’s POSM. These labels and global round numbers are only for analysis; players need not know their BUS ranks or detect mature entry. Definition 2 (Mature entry). After the round-start updates in round c and before proposals, suppose the root has just entered Work, while every other player is in Seek with ρ = 0 and a BUS rejection recorded during its current Seek visit. Then c is a mature entry, and the computation it initiates is a mature execution. With the staggered entry times below, the Top stages share a round in which every player proposes to its first-choice arm. The following lemma proves correctness of the ensuing DA updates, and Lemma 5 establishes the entry times and the replay handoff. Lemma 4 (Deferred Acceptance with Delayed Proposals). Suppose player j starts Work at sj = c + 2(j − 1), no population event occurs in [c, o1 ), where o1 = c + J − 1, and all players are in Top with application index 1 at t0 = maxj sj + 2K. On [t0 , o1 ), the execution implements playerproposing deferred acceptance with delayed proposals. Every rejection processed in DA excludes its edge from every stable matching. An arm that rejects a player retains an acceptor preferred to that player through round o1 − 1. An all-accepted round occurs by c + J − 2; its matching is m∗ and persists through round o1 − 1. Proof. Call a rejection adopted when it is processed in a nonfinal DA round. On consecutive rounds of [t0 , o1 ), every accepted player repeats its arm, including across the Top–DA transition. If displaced, it is replaced by a proposer the arm prefers. Thus an arm’s acceptor can only improve after its first acceptance in this interval. For rejection validity, induct on rounds from t0 , when all application indices are 1. Suppose i adopts a rejection by arm x, whose winner is w. Every arm that w prefers to x was passed after an adopted rejection in a strictly earlier round; this set is empty if w is still in Top. By induction, none can be w’s partner in a stable matching m. If m(i) = x, then w prefers x to m(w), and x prefers w to i, so (w, x) blocks m. This contradiction uses only rejections from earlier rounds. A rejection at a player’s last arm would require better actual acceptors at all K arms, by persistence at its previously rejected arms. These would be K distinct other players, contradicting n ≤ K. Hence the cap never prevents an advance, and at most n(K − 1) advances occur. Rejected proposals are repeated during Top; otherwise these are player-proposing DA updates. 15

All players are in DA by t1 = c + 6K − 1, and t1 + n(K − 1) ≤ c + 6K − 1 + K(K − 1) = c + J − 2 < o1 .

(15)

Every round in [t1 , t1 + n(K − 1)] without universal acceptance produces an advance. These n(K − 1) + 1 rounds therefore include an all-accepted round. Let M be the matching in an all-accepted round. Every arm that a player prefers to its partner has rejected that player and retains a better acceptor, so M is stable. Rejection validity also excludes every such preferred edge from all stable matchings, proving M = m∗ . Repeated accepted proposals preserve this matching through round o1 − 1. Lemma 5 (Correctness and Output Offsets of Mature Executions). Suppose c is a mature entry and no population event occurs from c through V = c + J + 2(n − 1). Player j starts Work and outputs at sj = c + 2(j − 1), oj = c + J − 1 + 2(j − 1) = o1 + 2(j − 1). The actual matching reaches m∗ by c + J − 2 and remains there through V = on + 1 ≤ c + J + 2K − 2. Each player outputs m∗ (j) exactly once in [c, V ] and enters Replay with that saved arm at oj + 1. We call V , when all players have entered Replay, the replay handoff completion round. Proof. Entry and output times. At mature entry, each remaining seeker has a recorded BUS rejection and ρ = 0. While earlier entrants stay in Park, the highest-priority remaining seeker receives two consecutive BUS acceptances and enters Work next round. Induction gives sj = c + 2(j − 1),

1 ≤ j ≤ n.

(16)

For n ≥ 2, the last qualifying pair ends at c + 2n − 3 ≤ c + 2K − 3, before the root leaves Park at c + 2K. Each seeker takes its AA handoff before accumulating the J > 2 acceptances needed for a sweep. The case n = 1 is immediate. The last entrant reaches Top at t0 = c + 2(n − 1) + 2K ≤ c + 4K − 2, while the root remains in Top through c + 4K. Thus all players are in Top with application index 1 at t0 . Since each Work invocation lasts exactly J rounds, oj = sj + J − 1 = o1 + 2(j − 1),

o1 = c + J − 1.

(17)

All players remain in Top or DA on [t0 , o1 ). By Lemma 4, the matching reaches m∗ by c + J − 2 < o1 and remains correct before the first output. Output and replay. Every output assigns a replay length at least H, so each new global deadline is at least oj + H ≥ o1 + H. Since V = on + 1 = o1 + 2(n − 1) + 1 ≤ o1 + 2K − 1 < o1 + H, no replay expires during the replay handoff. Inductively, players still in Work repeat their accepted arms and save them at output, while players already in Replay propose to those same arms and remain accepted. Hence the matching stays at m∗ through V . Each player outputs exactly once, enters Replay at oj + 1, and remains there through V .

16

Calibration from consecutive outputs. Consider any two mature executions in this fixed market that give consecutive actual outputs for every player. Let om−1 , om be the root’s output rounds in these executions. By Lemma 5, player j, born at bj , outputs at local ages aj,s = os + 2(j − 1) − bj for s ∈ {m − 1, m}. Actual adjacency gives the old register ℓj = aj,m−1 , so aj,m − ℓj = om − om−1 ,

Lm = F (om − om−1 ).

Thus the replay lengths agree, while the global deadlines retain the output offsets: Qj,m = om + 2(j − 1) + Lm .

(18)

A replay handoff with a common replay length is called calibrated.

A.3

Sweep Isolation and Mature Entry

The next lemma shows that a sweep accepted at every BUS proposal isolates the other players, and that a successful block followed by an event-free round establishes a mature entry. Its isolation property will also bound recovery time. Lemma 6 (Sweep isolation and mature entry). Consider a history of Algorithm 1 with the update (13), reachable from the prescribed initialization, and let player z enter Sweep in global round b. (i) Isolation during a continuing sweep. Suppose z remains in this visit through round d and is accepted at every BUS action in rounds b, . . . , d. At the start of b, after all round-start checks, every other present player is in Seek or Replay, with ρ = 0 and no pending Work entry. Throughout b, . . . , d, all other players remain in Seek or Replay and never schedule Work; in particular, none enters Sweep or produces an output. Population events and failed blocks are allowed. (ii) Mature entry after success. If this visit completes an all-accepted block in round e, and no population event occurs in round c = e + 1, then c is a mature entry with z as root. Population events during qualification and the sweep, including at the start of round e, are allowed. Proof. Proof of (i). Put v = b − J. Since every action other than an accepted BUS proposal resets ρ, even after saturation, qualification at b implies that z is accepted at BUS in v, v + 1, . . . , b − 1.

(19)

No other player can complete an AA pair or a successful block in this interval, since both require a final BUS acceptance. Thus no other Work entry is scheduled. Any Work entry pending from v − 1 takes effect at v, so all earlier Work invocations finish by v + J − 1 = b − 1. A competing sweep present at v reaches BUS by v + 1 and, if still present, returns to Seek by v + 2. Every other player’s counter is reset in each qualification round, excluding new sweeps in v + 1, . . . , b. Since J > 2, all other players are in Seek or Replay at b, with zero counters and no pending Work. Arrivals start in Seek with ρ = 0, and departures simply remove players. The scan word (3) leaves BUS only for isolated single rounds, including across failed-block restarts. Non-BUS rejections mark a block as failed without restarting it. Since z wins every BUS action, every other player’s consecutive BUS-acceptance count stays at most one. Thus neither an AA handoff nor a new sweep qualification is possible, and all other players remain in Seek or Replay. This proves (i) on every continuing prefix, regardless of eventual success. Proof of (ii). On a BUS rejection, the player skips the block-completion test and leaves Sweep in the following round. Thus a visit completing a successful block at e has only BUS acceptances, 17

and (i) applies with d = e. No other output occurs: each old replay keeps its saved arm until it ends, and no seeker reenters Replay. A player still replaying when its saved arm is visited is rejected. Every arm is visited by e − 2, so all old replays have ended by e − 1; later arrivals start in Seek. The final two proposals are to BUS. In round e, every other present player, including any new arrival, therefore proposes to BUS and is rejected. Each ends the round in Seek with a rejection recorded during its current visit, ρ = 0, and no pending Work. Since z wins against all these players, it is the highest-ranked player at BUS. With no population event at c = e + 1, its scheduled Work entry establishes the mature entry in Definition 2.

A.4

Proof of Lemma 1

To apply the calibration identity, we must obtain two mature executions whose outputs are consecutive for every player in the final market. For the replay rule F satisfying (12), define the nondecreasing recovery map ΨF (x) = x + F (x + H) + 3H. (20) Lemma 7 (Recovery to actual consecutive mature outputs). For every normally initialized finiteevent history with a nonempty final market, there are two mature executions beginning after t∗ whose replay handoffs are complete by a round Vcal ≤ Ψ◦3 F (t∗ + 1).

(21)

Each player’s two outputs are consecutive in its actual output history, so the second output uses the local age of the first as its old ℓ. Proof of Lemmas 1 and 7. Let n be the final population size and z its root, the highest-priority player at BUS. At any output in round v, including an incorrect one, a player born at bi ≥ 1 has 0 ≤ ℓ ≤ a = v − bi ≤ v. By monotonicity of F , the old register ℓ gives the global deadline Qi = v + F (a − ℓ) ≤ v + F (v).

(22)

Replay expires in its deadline round; acceptance never extends it, and rejection can end it earlier. First mature execution. From round t∗ + 1, z is never rejected at BUS. Before reaching a continuing sweep, it can produce at most one output from an inherited Work invocation or an old Seek rejection record, and any such output occurs by t∗ +J +2. A fresh Seek visit clears that record and cannot trigger an AA handoff. By (22), every preceding replay ends by t∗ + J + 2 + F (t∗ + J + 2). At most J further qualification rounds therefore give a continuing sweep by β ≤ t∗ + J + 2 + F (t∗ + J + 2) + J ≤ ΨF (t∗ + 1).

(23)

An inherited sweep already satisfies the isolation invariant from its original qualified entry, even if events occurred in the meantime. Until success, Lemma 6(i) excludes other Work entries, sweeps, and outputs. All remaining replays therefore expire by β + F (β). A residual block and one full block take at most 4K further rounds; the full block succeeds if no earlier one does. By Lemmas 5 and 6, the resulting mature execution completes its replay handoff at Vfirst ≤ β + F (β) + J + 6K − 2 ≤ ΨF (β). All players are then in correct Replay, although their replay lengths can differ. 18

(24)

The next Work entry is mature. Before any new Work entry, no output replaces the current deadlines, all of which are at most Vfirst + F (Vfirst ). If no entry has occurred by that round, all current replays have ended. Player z is then already sweeping or qualifies within J rounds, and a residual block followed by a full block succeeds within at most 4K more rounds. Thus a new Work entry occurs by Vfirst + F (Vfirst ) + J + 4K; let r > Vfirst be the first such round. Suppose player i enters Work through an AA handoff at r. Its current Seek visit began after Vfirst with the rejection flag cleared. The final acceptance run must have length exactly two, or Work would have started earlier. Hence, in that same visit, i was rejected at r − 3 and accepted at r − 2, r − 1. Let w be the BUS winner at r − 3. It outranks i and remains present, so it must avoid BUS in both following rounds. A winning seeker continues on BUS, including upon sweep qualification; a player accepted while replaying BUS proposes there again, including after expiration; and a continuing sweep leaves BUS only for isolated rounds. A Work entry in either intervening round would contradict the choice of r. This two-round absence is impossible, so the first new Work entry follows a successful sweep and is mature by Lemma 6(ii). Consecutive outputs and calibration. By Lemma 5, each player outputs exactly once in each mature execution. No output occurs between Vfirst and r, so these are consecutive actual outputs. The second replay handoff completes at r + J + 2(n − 1); hence Vcal = r + J + 2(n − 1) ≤ Vfirst + F (Vfirst ) + 2J + 6K − 2

(25)

≤ ΨF (Vfirst ) ≤ Ψ◦3 F (t∗ + 1). For K ≥ 2, J + 1 < H, J + 6K − 2 < H, and 2J + 6K − 2 < H; these inequalities and monotonicity justify all three applications of ΨF . Applying (18) to these two executions gives a common replay length at Vcal . Together with the correct matching and completed replay handoff, taking F = Fg proves Lemma 1.

A.5

Proof of Lemma 2

After calibration, each maintenance window starts at the root’s replay deadline and ends at the next replay handoff. We show that these windows have bounded length and preserve calibration. Lemma 8 (Bounded maintenance under a general replay rule). Suppose two mature executions in a fixed market of 1 ≤ n ≤ K players with POSM m∗ give consecutive actual outputs for every player, and the population remains fixed thereafter. Every subsequent maintenance cycle produces each player’s next actual output in a mature execution, preserving the output offsets and a common replay length. For cycle m, let o = om and L = Lm be the current root output time and common replay length, and put Q = o + L. If o′ is the next root output and V ′ its replay handoff completion round, then 0 < Cm := o′ − Q ≤ 2J + 2K − 1, V ′ − Q ≤ U = 2K 2 + 14K, and Lnext = F (L + Cm ) ≥ H + 2(L + Cm ) > 2L. The maintenance window is [Q, V ′ ); between these windows, Mt = m∗ . Proof of Lemmas 2 and 8. Order the players by decreasing priority at BUS. We induct on calibrated replay handoffs. The deadlines are Q + 2(j − 1) by (18), and L ≥ H > 2K places Q after the current 19

handoff. All players remain in correct Replay through round Q − 1; every other current replay ends by Q + 2K − 2, possibly earlier after rejection. Once the root sweeps, Lemma 6(i) excludes other Work entries, sweeps, and outputs. If m∗ (1) ̸= BUS, the root enters a fresh Seek visit at Q with ρ = 0 and its rejection record cleared. Its J BUS acceptances in Q, . . . , Q + J − 1 cannot trigger its own AA handoff and prevent every other AA handoff. Any other BUS replayer is rejected at Q, before its own deadline, resetting its counter; non-BUS replayers already have zero counters. Thus no competing sweep or Work invocation begins. Since J > 2K − 2, all others are seekers when the root enters Sweep at Q + J, and the first block succeeds: c = Q + J + 2K. (26) If m∗ (1) = BUS, all L ≥ H > J proposals in o, . . . , Q − 1, including the output round o, are accepted at BUS. The counter is saturated, so expiration followed by qualification starts Sweep at Q. All other replays end by Q + 2K − 2, so the second block, starting at Q + 2K, succeeds unless the first already did. Hence c ≤ Q + 4K ≤ Q + J + 2K. (27) In both cases, no output occurs between the current handoff and c, and c ≤ Q + J + 2K. By Lemma 6(ii) and Lemma 5, the next execution is mature and gives each player’s next actual output with the same offsets. Since o′ = c + J − 1, Cm := o′ − Q,

0 < Cm ≤ 2J + 2K − 1.

(28)

Calibration therefore applies again with o′ − o = L + Cm : Lnext = F (L + Cm ) ≥ H + 2(L + Cm ) > 2L.

(29)

The last player enters Replay one round after its output, so V ′ = o′ + 2(n − 1) + 1 ≤ o′ + 2K − 1, giving V ′ − Q ≤ Cm + 2K − 1 ≤ 2J + 4K − 2 = 2K 2 + 14K = U. (30) Thus [Q, V ′ ) costs at most U mismatch rounds. Since Lnext ≥ H > 2K, the next deadline follows V ′ , with correct replay between the windows, completing the induction. The initial calibrated length is at least H, and monotonicity gives Lnext = F (L + Cm ) ≥ F (L). Applied with F = Fg to the pair supplied by Lemma 7, these bounds prove Lemma 2. Finite-prefix accounting. b0 = H,

Write DF (T ; I) for the mismatch cost under replay rule F , and let NF (T ) = #{j ≥ 0 : bj < T }.

bj+1 = F (bj ),

Starting with the calibrated handoff, write Lj and oj for the common replay length and root output round in cycle j. If the final population has n players, its handoff completion round is Vj = oj + 2n − 1, with V0 = Vcal . By Lemma 8, L0 ≥ H and Lj+1 ≥ F (Lj ), so Lj ≥ bj . A maintenance window meeting the first T rounds starts at Qj = oj + Lj ≤ T . Since oj ≥ 1, it satisfies bj ≤ Lj < T . At most NF (T ) windows contribute, each costing at most U , including an unfinished last window. Charging at most one per round before calibration and using Lemma 7 gives DF (T ; I) ≤ min{T, Ψ◦3 F (t∗ + 1) + U NF (T )}.

(31)

This also covers prefixes ending before calibration. If the final market is empty, DF (T ; I) ≤ min{T, t∗ − 1}, so the same bound holds; at T = 0, both sides are zero. 20

A.6

Proof of Lemma 3

Proof. Fix a nondecreasing, polynomial-time computable function g : N≥1 → N≥1 with g(t) = Ω(t), and put ( ) t Mg = max 1, sup < ∞. t≥1 g(t) The asymptotic linear lower bound controls the ratios for all sufficiently large t, and positivity controls the remaining finite set. The constant Mg is used only in the analysis. For the sequence (sj ) and rule Fg in (5), write

Ag (x) = max {g(sj ) − sj : j ≥ 0, 64sj ≤ x} ∪ {0} ,

Fg (x) = H + 2x + Ag (x).

The maximum is nonnegative and nondecreasing in x, even though the individual differences need not increase with j. Hence Fg is nondecreasing and satisfies (12). Since sj+1 ≥ (1 + 1/Mg )sj , evaluation visits O(1 + log(x + 1)) eligible values of sj , with a constant depending only on g. It calls g(sj ) only while 64sj ≤ x, and maintains the maximum of the differences. The assumed polynomial-time computability of g, together with integer additions and comparisons, therefore gives a polynomial-time evaluation of Fg . The protocol Πg uses (13) with this function, fixed by K, g before the instance and horizon; it does not need Mg as an input. Recovery. The recovery map is ΨFg (x) = 3x + 6H + Ag (x + H). We show (

Ψ◦3 Fg (t + 1) ≤ Cg (t),

Cg (t) =

105H, 118(t + g(t)),

1 ≤ t < H, t ≥ H.

(32)

For an integer t ≥ H, choose sj ≤ t < sj+1 and put a = sj+1 . Then t + 1 ≤ a = sj + g(sj ) ≤ t + g(t),

H ≤ a.

Whenever z + H < 64a, only indices k ≤ j can be activated, so Ag (z + H) ≤ maxk≤j sk+1 = a. Writing z0 = t + 1 and zi+1 = ΨFg (zi ) gives z0 + H ≤ 2a, z1 ≤ 10a, z1 + H ≤ 11a, z2 ≤ 37a, z2 + H ≤ 38a, z3 ≤ 118a ≤ 118(t + g(t)). Every input stays below 64a. For 1 ≤ t < H, z0 ≤ H, and the three inputs to Ag are at most 2H, 10H, 34H, below the first threshold 64H. Thus all three additional terms vanish and z3 = 27(t + 1) + 78H ≤ 105H. This proves (32) without any bound on g(t + 1)/g(t). The function Cg is nondecreasing, including at H. Iteration count. Let b0 = H and bj+1 = Fg (bj ). Since Fg (x) ≥ 2x, six iterations from sj reach at least 64sj , and Fg (64sj ) ≥ H + 128sj + g(sj ) − sj ≥ sj + g(sj ) = sj+1 . Monotonicity therefore gives b7j ≥ sj ,

NFg (T ) ≤ 7#{j : sj < T } ≤ 7Ng (T ). 21

Indeed, if m = #{j : sj < T }, then b7m ≥ sm ≥ T ; also r0 = 2 ≤ H = s0 and monotonicity imply rj ≤ sj . These comparisons include horizons equal to an iterate. Since t ≤ Mg g(t) and H ≤ 16K 2 , (32) gives the first bound in Lemma 3, with a constant depending only on g. The identity bj = Fg◦j (H) gives the second with the universal constant 7. When g(t) = t, every difference in Ag vanishes, so Fg (x) = H + 2x for all x ≥ 1. Combining (31) with the recovery and iteration bounds gives DΠg (T ; I) ≤ min{T, 118(t∗ + g(t∗ )) + 105H + 7U Ng (T )}.

(33)

For a static instance, t∗ = 1 < H, so the sharper recovery estimate in (32) gives sup DΠg (T ; I) ≤ 105H + 7U Ng (T ).

(34)

I: t∗ =1

Here H ≤ 16K 2 and U ≤ 9K 2 , so the static bound has constants uniform in K, g, I, T . The joint proof of Theorems 1 and 2 in Section 3.2 absorbs the startup term and handles the small horizons.

A.7

Proof of Corollary 1

Proof. Fix η ∈ (0, 1). Starting with the calibrated handoff, let oj , Lj , Qj have the meanings used in the finite-prefix accounting above. By Lemma 8, oj+1 = oj + Lj + Cj ,

Lj+1 = Fg (Lj + Cj ) ≥ H + 2Lj ,

Cj > 0.

Thus Lj ≥ (2j+1 − 1)H,

Qj+1 − Qj = Cj + Lj+1 ≥ (2j+2 − 1)H.

Every [Qj , Vj+1 ) costs at most U , and Q0 > Vcal . Put mη = min{m ∈ Z≥0 : (2m+2 − 1)H ≥ U/η},

QK,η = (mη + 1)U.

Charge the first mη windows separately. Later starts are at least U/η apart, so at most 1 + ηh/U occur in any h consecutive rounds. In particular, DΠg (Vcal + h; I) − DΠg (Vcal ; I) ≤ QK,η + ηh

(h ≥ 0).

(35)

This difference counts rounds Vcal + 1, . . . , Vcal + h. Because U/H ≤ 1, QK,η = O(K 2 [1 + log(1/η)]), independently of g. The post-event window. Let τ = t∗ and a = Vcal − τ in a nonempty final market. The first a rounds of the event-excluding window cost at most a ≤ Cg (τ ). Splitting a longer window at Vcal and using (35) gives, for every h ≥ 1, LΠg (h; I) ≤ min{h, Cg (t∗ ) + QK,η + ηh}.

(36)

Empty final markets have zero post-event cost. Recovery coefficients. For 0 < ε < 1, take η = ε/2 and cε =

2(118(1 + Mg ) + 105H + QK,ε/2 ) > 0. ε

Since g(t∗ ) ≥ 1 and Cg (t∗ ) ≤ 118(1+Mg )g(t∗ )+105H, the condition h ≥ cε g(t∗ ) implies LΠg (h; I) ≤ εh. For ε ≥ 1, the claim follows from LΠg (h; I) ≤ h. Thus the same Πg has sublinear mismatch cost relative to g; its rule has no accuracy parameter.

22

B

Lower Bounds and Optimality

This appendix proves Theorem 3 and the iteration-count results in Section 4.2, and gives the computational details for the exponential function. We use the known-preference setting, in which each arm accepts its most-preferred proposer in each round. The lower bounds allow private state, private randomness, adaptive proposals, and accepted utilities.

B.1

Proof of Theorem 3

Proof of Theorem 3. Fix K, g, Π as in the theorem. Static bound. In the static instance I0 , players p1 , p2 enter in round 1 and remain forever, both ranking 0 ≻ 1 ≻ · · · ≻ K − 1. Arm 0 prefers p1 to p2 ; every other arm prefers p2 to p1 . Acceptance on arm x gives either player deterministic utility (K − x)/(K + 1). The unique stable matching is {(p1 , 0), (p2 , 1)}. For each τ ≥ 2, let Iτ remove p1 at the start of round τ ; thereafter the POSM assigns p2 to 0. This family is fixed independently of the protocol, function g, recovery coefficient, and horizon. Write m(T ) = EDΠ (T ; I0 ), LΠ (h; Iτ ) = E[DΠ (τ + h; Iτ ) − DΠ (τ ; Iτ )]. Couple the executions using identical private random tapes. The two histories agree before τ . Until p2 ’s first proposal to 0 at or after τ , every other arm accepts it in both executions with identical utility, independently of p1 ’s actions. Induction preserves its local state, clock, and random-tape consumption through the selection of that first proposal, before its feedback is observed. The proposal is therefore made in the same round in both executions; its feedback may differ, and no subsequent agreement is needed. In the static execution, every proposal by p2 to 0 causes mismatch. The expected number of such proposals in {τ, . . . , τ + h} is at most m(τ + h) − m(τ − 1). With probability at least max{0, 1−m(τ +h)+m(τ −1)}, there is no such proposal. On that event all h rounds τ +1, . . . , τ +h are mismatched in the departure execution. Therefore LΠ (h; Iτ ) ≥ h max{0, 1 − m(τ + h) + m(τ − 1)},

τ ≥ 2, h ≥ 1.

(37)

Including τ in the static charge accounts for detection in the event round, which the recovery cost itself excludes. In particular, (37) implies LΠ (h; Iτ ) ≤ h/2

=⇒

m(τ + h) − m(τ − 1) ≥ 1/2.

(38)

Choose a half-accuracy coefficient c1/2 > 0 supplied by Definition 1, and put q = max{1, ⌈c1/2 ⌉}. Define x0 = 2, hj = qg(xj ), xj+1 = xj + hj + 1. The recovery window of Ixj is {xj + 1, . . . , xj+1 − 1}, of length hj . Since hj ≥ c1/2 g(xj ), the recovery condition bounds its expected cost by hj /2. Equation (38) therefore forces at least 1/2 expected static mismatch in the augmented interval {xj , . . . , xj+1 − 1}. These intervals are disjoint. If n(T ) = #{j : xj+1 ≤ T + 1}, then m(T ) ≥ n(T )/2, since all these intervals lie among the first T rounds.

23

Let Φ(x) = x + g(x), and recall r0 = 2. Since g is nondecreasing and positive, Φ◦(q+1) (x) ≥ x + (q + 1)g(x) ≥ x + qg(x) + 1. Thus xj ≤ r(q+1)j . Since xn(T )+1 > T + 1, also r(q+1)(n(T )+1) > T , giving Ng (T ) ≤ (q + 1)(n(T ) + 1). We have proved the uniform finite bound 1 Ng (T ) max 0, −1 2 q+1 

EDΠ (T ; I0 ) ≥



(T ≥ 0).

(39)

Every iterate is finite, and the sequence is unbounded, so Ng (T ) → ∞. For fixed K, the coefficient q depends only on the chosen protocol and function g. Thus (39) proves the static bound on the same instance I0 for every protocol. Dynamic bound. Fix t∗ ≥ 2. A permanent player b enters in round 1. There is a potential fresh guard cr for each r = 1, . . . , t∗ . All players rank 0 ≻ 1 ≻ · · · ≻ K − 1. Arm 0 ranks every guard above b, while every other arm ranks b above every guard. Complete the orders among guards arbitrarily and fix consistent deterministic utilities. When b is alone, its POSM assignment is 0; with a guard present, the unique stable matching assigns the guard to 0 and b to 1. Before execution, choose independent fair bits ξ1 , . . . , ξt∗ −1 , independently of the protocol’s private randomness. Guard cr , for r < t∗ , enters in round r and leaves at the start of round r + 1 if ξr = 1, and never enters otherwise. In round t∗ , the fresh guard ct∗ enters and remains forever. At most two players are active in any round, each identity has one contiguous lifetime, and the last event is exactly at t∗ . Every player is initialized normally; the permanent player keeps its actual state throughout. Before its round-r proposal, for r < t∗ , player b has no observation of ξr . Conditional on the past, let p0 , p1 be its probabilities of proposing to arms 0, 1. Correct matching requires proposal 0 when ξr = 0, and proposal 1 when ξr = 1. Its conditional probability of making the required proposal is at most 1 1 1 2 p0 + 2 p1 ≤ 2 , regardless of the guard’s actions. Averaging over the preselected bit strings therefore gives one fixed instance I ′ such that, writing m(T ) = EDΠ (T ; I ′ ), m(T ) ≥ m(t∗ − 1) ≥

t∗ − 1 t∗ ≥ 2 4

(T ≥ t∗ ).

(40)

This choice depends on the protocol’s distribution and t∗ , but not on its realized random tape or on T. For each τ ≥ t∗ + 1, form a comparison instance Iτ′ by keeping the entire history of I ′ before τ and removing ct∗ at the start of round τ . Its last event is τ . Couple the two executions with identical private random tapes. Until b’s first proposal to 0 at or after τ , every other arm accepts it in both executions with the same utility, so its local history and state agree. Such a proposal causes mismatch in I ′ ; without it, every post-departure round is mismatched in Iτ′ . The same event-round accounting as in (37) gives LΠ (h; Iτ′ ) ≥ h max{0, 1 − m(τ + h) + m(τ − 1)}

(τ ≥ t∗ + 1, h ≥ 1).

This coupling preserves the actual states inherited at t∗ . With the same coefficient q, let j⋆ = min{j : rj ≥ t∗ + 1},

x0 = rj⋆ , 24

xj+1 = xj + qg(xj ) + 1.

(41)

Since rj ≥ j + 2, we have j⋆ ≤ t∗ − 1. Apply the recovery condition to Ix′ j with window length qg(xj ). Equation (41) forces at least 1/2 expected mismatch in each augmented interval {xj , . . . , xj+1 − 1}. These intervals are disjoint and start after the population prefix. If n(T ) = #{j : xj+1 ≤ T + 1}, then n(T ) ≤ 2m(T ). The iteration comparison used for the static bound yields xj ≤ rj⋆ +(q+1)j ,

Ng (T ) ≤ j⋆ + (q + 1)(n(T ) + 1).

The latter inequality also holds when no augmented interval is complete. By (40), t∗ ≤ 4m(T ) and 1 ≤ 2m(T ). Consequently, Ng (T ) ≤ 4m(T ) + 4(q + 1)m(T ) ≤ 8(q + 1)m(T ). Combining these inequalities gives the finite bound on this same instance: EDΠ (T ; I ′ ) ≥

t∗ + Ng (T ) 12(q + 1)

(T ≥ t∗ ≥ 2).

(42)

The coefficient is independent of t∗ and T , and the selected instance works for all T ≥ t∗ , proving the dynamic bound. The static bound also rules out sublinear mismatch cost relative to a bounded function g. Indeed, suppose K ≥ 2 and g(t) ≤ G for all t, for some fixed positive integer G. Then rj ≤ 2 + jG, so Ng (T ) = Ω(T ). If Π satisfied Definition 1, (39) would give m(T ) = EDΠ (T ; I0 ) = Ω(T ). On the same static instance, t∗ = 1, and the recovery condition gives m(1 + h) − m(1) ≤ εh for every ε ∈ (0, 1) and h ≥ cε g(1). Hence m(T ) = o(T ), a contradiction. At g(t) = t, the iteration is rj = 2j+1 , and t∗ + Ng (T ) = Θ(t∗ + log T ) uniformly for T ≥ t∗ ≥ 2. Together with Theorem 1 and corollary 1, this proves the stated per-protocol optimality for fixed K. The lower constant can depend on the fixed protocol’s recovery coefficient; a uniform comparison requires a common coefficient.

B.2

Proofs for Section 4.2

Throughout this subsection, g : N≥1 → N≥1 is nondecreasing and satisfies g(t) = Ω(t), and Ng is defined by (6). Positivity implies that g(t) ≥ δg t for every t ≥ 1, for some constant δg > 0. Thus every iterate is finite and rj+1 ≥ (1 + δg )rj , giving Ng (T ) → ∞ and Ng (T ) = O(log T ). Polynomial-time computability will be verified for the representative functions to which the upper bound applies. Lemma 9 (Comparison of iteration counts). Let ge : N≥1 → N≥1 be nondecreasing. If g(t) ≤ ge(t) ≤ c g(t) for every t ≥ 1, then, with d = max{1, ⌈c⌉}, Neg (T ) ≤ Ng (T ) ≤ dNeg (T )

(T ≥ 0).

In particular, g(t) = Θ(ge(t)) implies Ng (T ) = Θ(Neg (T )). Proof. Put d = max{1, ⌈c⌉}.

Qg (x) = x + g(x),

e(x), and hence Monotonicity gives Q◦d g (x) ≥ x + dg(x) ≥ x + g

Qg (x) ≤ Qeg (x) ≤ Q◦d g (x). 25

Iterating from 2 gives the claimed inequalities. If two functions are within constant factors only for sufficiently large t, positivity allows the comparison constant to be enlarged to cover the finitely many initial values. Applying the preceding inequalities to their pointwise minimum and maximum proves the final assertion. Proof of (10). Put yj = log rj and zj = log yj . The recurrence (6) gives !

g(rj ) . yj+1 − yj = log 1 + rj

(43)

For n = Ng (T ) and T > 2, the strict count gives rn−1 < T ≤ rn , including when T is an iterate. Hence yn−1 < log T ≤ yn , zn−1 < log log T ≤ zn . If log g(t)/ log t → α ∈ [1, ∞], then yj+1 /yj → α, hence zj+1 − zj → log α and, by Cesaro averaging, zj /j → log α, with log ∞ = ∞. The second pair of inequalities gives Ng (T ) ∼ log log T / log α for 1 < α < ∞. At α = 1 and α = ∞, its upper and lower bounds give Ng (T ) = ω(log log T ) and Ng (T ) = o(log log T ), respectively. Equation (43) also shows that g(t)/t → ∞ implies yj+1 − yj → ∞. Cesaro averaging then gives yj /j → ∞, and the first pair of inequalities yields Ng (T ) = o(log T ). Proof of Table 1. The parameters α, δ are fixed rational numbers. Put yj = log rj and zj = log yj . For a positive integer input t, let b = 1 + ⌊log t⌋ be its bit length. Linear and logarithmically enlarged functions. The linear function is polynomial-time computable, as is g(t) = tb, since b is obtained directly from the input representation. The latter function is nondecreasing and has growth Θ(t log(e + t)), so it satisfies g(t) = Ω(t). For g(t) = t, rj = 2j+1 gives Ng (T ) = Θ(log T ). For g(t) = t(1 + ⌊log t⌋), the logarithmic recurrence gives yj+1 − yj = log(2 + ⌊yj ⌋) = Θ(log yj ) eventually. Consider intervals [2k , 2k+1 ) in the yj -coordinate. If j is the first index with yj ≥ 2k , then, for sufficiently large k, 0 ≤ yj − 2k ≤ log(2 + 2k ) = O(k). Applying this bound at both endpoints gives a traversed distance of 2k + O(k). Since increments inside the interval are Θ(k), traversal takes Θ(2k /k) steps. When log T ∈ [2k , 2k+1 ), the preceding complete interval [2k−1 , 2k ) provides Ω(2k /k) steps. Summing completed intervals and bounding the last partial interval by a full one gives O(2k /k) steps, hence Ng (T ) = Θ(log T / log log T ). Polynomial functions. For fixed α = p/q > 1, with positive integers p, q, ⌈tp/q ⌉ = min{m ∈ N≥1 : mq ≥ tp }. Integer binary search computes this value, including equality cases, in polynomial time in b: the searched integers have O(b) bits, and comparisons use exact integer powers. This function is also nondecreasing and satisfies g(t) = Ω(t). For g(t) = ⌈tα ⌉, α > 1, the general classification gives Ng (T ) ∼ log log T / log α. The functions gδ . Fix positive integers p, q, put δ = p/q, and define δ

gδ (t) = t 2⌊(⌊log t⌋) ⌋ ,

t ≥ 1.

Let b be the input bit length and put n = b − 1 = ⌊log t⌋. The exponent is the integer k = max{m ∈ Z≥0 : mq ≤ np } = ⌊nδ ⌋. 26

(44)

It can be computed exactly by integer binary search on [0, np + 1), including equality cases. For fixed p, q, the endpoints and powers used in the comparisons have O(log(b + 1)) bits, and the search uses O(log(b + 1)) comparisons. The output is obtained by appending k zero bits to the input, and its length satisfies b + k ≤ b + (b − 1)δ = O(b + bδ ). Thus reading the input, computing the exponent, and writing the output all take polynomial time in b. When t = 1, we have n = 0, and the search returns k = 0, giving gδ (1) = 1. As t increases, both n and k are nondecreasing, including at bit-length boundaries. Hence gδ is nondecreasing and satisfies gδ (t) ≥ t. For g = gδ in (44), put kj = ⌊(⌊yj ⌋)δ ⌋. For real y ≥ 2, the mean value theorem and ⌊y⌋ ≥ y/2 give 0 ≤ y δ − (⌊y⌋)δ ≤ Cy δ−1 . Rounding the power down changes it by less than one. Also, 0 < log(1 + 2−k ) ≤ 1 for k ≥ 0. Therefore the actual integer orbit satisfies 



yj+1 − yj = log 1 + 2kj = yjδ + O(yjδ−1 + 1) ∼ yjδ .

(45)

Here gδ (t) ≥ t implies yj ≥ j + 1, so the relative error O(yj−1 + yj−δ ) tends to zero. If 0 < δ < 1, (45) gives yj+1 /yj → 1. The mean value theorem, with ξj ∈ [yj , yj+1 ], gives 1−δ yj+1 − yj1−δ = (1 − δ)ξj−δ (yj+1 − yj ) −→ 1 − δ.

Summing the increments gives yj1−δ ∼ (1 − δ)j. The horizon sandwich yn−1 < log T ≤ yn , with n = Ng (T ), therefore gives Ng (T ) = Θ((log T )1−δ ). For g = gδ with δ > 1, (45) gives yj+1 /yjδ → 1. Thus, with zj = log yj , zj+1 = δzj + εj ,

yj+1 εj = log yjδ

!

−→ 0.

Choose j0 so that |εj | ≤ 1 for every j ≥ j0 and zj0 > 1/(δ − 1). Expanding the recurrence and bounding the geometric sum of errors yields, for every m ≥ 0, 

δ m zj0 −

1 δ−1





≤ zj0 +m ≤ δ m zj0 +

1 . δ−1 

The lower coefficient is positive, so zj = Θ(δ j ) and log zj = j log δ + O(1). Applying the horizon sandwich in this third logarithmic coordinate yields Ng (T ) =

log log log T + O(1). log δ

At δ = 1, t2 /2 < g1 (t) ≤ t2 , so its count is covered by the polynomial case. The five functions in Table 1 satisfy the hypotheses of Theorem 2. For fixed K and g, their optimal static maintenance orders follow from Theorems 2 and 3 and corollary 1. Constants and thresholds may depend on the fixed rational shape parameters.

B.3

The Exponential Function

Iteration count. For g(t) = 2t , let E(x) = 2x . Since E(x) ≤ x + 2x ≤ E ◦2 (x) for x ≥ 2, monotone iteration gives E ◦j (2) ≤ rj ≤ E ◦(2j) (2). With log∗ T = min{m ∈ Z≥0 : log◦m T ≤ 1}, the horizon sandwich gives (log∗ T − 1)/2 ≤ Ng (T ) ≤ log∗ T for T > 2. Hence Ng (T ) = Θ(log∗ T ). 27

Computation in local time. The binary representation of 2t has t + 1 bits, so g(t) = 2t is not polynomial-time computable from binary t. From the unary input 1t , it is computed in linear time by writing a one followed by t zeros. Fix K and substitute this function into (5). To evaluate Fg (x), generate the iterates starting at s0 = H, evaluating 2sj only while 64sj ≤ x. Each such value has at most ⌊x/64⌋ + 1 bits; the next iterate sj + 2sj , the candidate 2sj − sj , and the running maximum all have O(x) bits. Since sj+1 ≥ 2sj , at most O(1 + log(x + 1)) eligible iterates are examined. If none is eligible, Fg (x) = H + 2x. Thus additions, comparisons, and writing the output take time polynomial in x, with K fixed. At each output, x = a − ℓ ≤ a, so the new replay length and deadline have O(a + 1) bits and can be computed in time polynomial in the player’s local age. Between outputs, these stored values remain of polynomial bit length in the current age, so the remaining local updates also take polynomial time. This local-time bound does not satisfy the binary-input polynomial-time hypothesis of Theorem 2.

28

C

The SC-PC Protocol and Its Analysis

We give the local implementation of SC-PC and prove Theorem 4. Sections C.1 and C.2 describe the protocol and the order of actions within a round. A statistical error may delete a stable edge or lead to an incorrect replay. We therefore prove collection and recovery without assuming that earlier comparisons were correct. In a mature episode with covered comparisons, stable edges are preserved; failures add permanent samples, while successes force the replay scale to grow in subsequent episodes. These two forms of progress bound the cost along a chain of good episodes. Finally, concentration and two cold recoveries bound the expected time before such a chain begins. All executions use the model of Section 2.2 and the prescribed initialization below; surviving players retain their actual states. The population path is fixed before rewards are generated, and each identity has one contiguous lifetime. Write P∞ for the final population. Throughout this appendix, log is base two and ln is the natural logarithm. The last population-event time t∗ refers to the full schedule even when T ≤ t∗ . A static schedule has t∗ = 1; a permanently empty market has zero cost. For integer endpoints 1 ≤ s ≤ t, write D([s, t); I) :=

t−1 X

1{Mr ̸= m∗r } = D(t − 1; I) − D(s − 1; I).

r=s

C.1

Local Protocol Rules

Figure 2 shows the player modes and arm service states. Algorithm 2 summarizes the protocol; Algorithms 3–8 give the complete transition rules. Their only input is K ≥ 2, with K = {0, . . . , K−1}, BUS = 0, and PARK = 1. All parameters are fixed by χL = 4K − 2,

κL = χL − 1,

HL = dL = χL + 1,

bK = 2K 2 ,

WL = K(K − 1)2 + (2K − 1)bK = 5K 3 − 4K 2 + K, hD,L = 2χL + 1,

fL = WL + 3χL ,

GL = 2K + 3,

Rc,L = 2K + 1,

EL = τL + 1,

ML = EL + K.

(46)

JL = WL + 4χL ,

τL = JL + 2χL + 3,

The timing margin χL is a fixed protocol constant; the recovery scale g in Section 4 remains a separate object. The following table groups the parameters by their role. Their exact values are given above; asymptotic orders refer to K. Parameters

Role

Order

χL , κL dL , HL GL , Rc,L hD,L , fL

Timing margin and maximum mature entry span Initial parking length and minimum replay grace Control-service period and commitment acceptance suffix Deletion window hD,L ≤ h < fL ; certification allowed through h = fL Required sample quota and length of the common work window Work duration and business-service lease Fresh-entry guard and minimum commitment duration

K K K K, K 3

bK , WL JL , τL EL , ML

29

K 2, K 3 K3 K3

Time and state notation. The protocol reads local age a; physical round t is used only in the analysis. Within work, h counts completed rounds, so action h = 0 is the first work action. The registers ℓ, q are local ages (last output and replay deadline), whereas P, L are lengths. Uppercase Q always denotes a set of options, with confidence subset Ca (Q); the analysis threshold QT is a number. The remaining-arm set S is local state in the pseudocode; in the proofs, S denotes the physical round of first common replay. Each use is identified when introduced. Permanent records and confidence decisions. Each endpoint stores a count Nx , reward sum Ux , and last-acceptance time for each option: an arm for a player, or a permanent private player handle for an arm. Counts and sums start at zero and timestamps at −∞. Every acceptance, including a zero reward, updates both endpoints (Line 5 of Algorithm 3 and Lines 18–20 of Algorithm 4); rejection gives no sample. Records persist through mode changes and handle absence. Thus the two endpoints have the same edge count, denoted Ni (x) for edge (i, x). At local age a, define (

θbx =

Ux /Nx , 0,

Nx > 0, Nx = 0,

s

B(a) = 5 log(a + 2),

βa (x, z) =

B(a) 2



1 1 . + Nx Nz 

(47)

Set βa (x, z) = +∞ if either count is zero. For nonempty Q, let Ca (Q) = {x ∈ Q : θbz − θbx ≤ βa (z, x) for every z ∈ Q}.

(48)

Decisions use completed-round statistics. Every empirical maximizer belongs to Ca (Q), so it is nonempty. All comparisons matter: comparing only against one empirical maximizer need not give the same set. Arm service. Every arm, including BUS and PARK, follows Algorithm 3. Its clock starts at its first request and advances even in empty rounds; initially a = e = λ = 0. For nonempty requester set R, the eligible set is    Ca (R),

λ > 0, Q = R, λ = 0 and a ≡ 0 (mod GL ),   {min R}, λ = 0 and a ̸≡ 0 (mod G ), ≺ L

(49)

where ≺ is the arm’s private handle order. The arm accepts the eligible requester with the oldest acceptance timestamp, breaking ties by ≺ (Lines 3–4 of Algorithm 3). The counter e records consecutive empty rounds; updated e ≥ 2 refreshes the lease to τL at round end, and otherwise the lease decreases toward zero (Lines 6–7 of the same algorithm). Thus business service starts after the second empty round, overrides fair control rounds, and is renewed by further empty rounds. Before startup the lease stays zero. Player initialization and round order. A new player sets a = 0, P = HL , ℓ = ⊥, and enters fresh Seek (Lines 1–3 of Algorithm 4). The loop then applies scheduled transitions, checks replay expiry, makes one request, updates permanent records, and processes mode-specific feedback, in that order. Feedback transitions take effect next round; replay expiry changes the current request. Permanent records, P , and ℓ survive all transitions.

30

Collection. The signed counter x records consecutive BUS outcomes, ignoring non-BUS root requests. Fresh entry at age w sets the following registers (Lines 1–5 of Algorithm 5): x = 0,

armed = false,

b = w + EL ,

c = w + JL + χL + 4.

Qualification uses only ages a ≥ b: K consecutive post-guard rejections arm the player, and three consecutive post-guard acceptances send it to work if armed or to root otherwise. Guard feedback still updates x and sets c = a + JL + χL + 3 whenever x ≤ −3 (Lines 1–10 of Algorithm 6). Root entry freezes c and clears x; demotion enters armed Seek with x = 0, b set to the current local age, and no guard. Birth and replay expiry always enter fresh, and the armed flag persists within a visit. A root clears old work, scans 1, . . . , K − 1 through BUS/target alternation, and commits at BUS. Demotion after K consecutive rejected BUS visits has priority over stage completion. Commitment requires both ML rounds and an Rc,L -acceptance suffix within that stage; its entry clears a positive suffix but retains a negative one. The resets are given by StateUpdate (Algorithm 5); the tests are in Lines 12–25 of CollectionFeedback (Algorithm 6). Work actions and feedback. Each invocation has indices h = 0, . . . , JL − 1 and starts with S = K, no held arm or target, and rejection counter z = 0. After dL parking rounds, WorkAction prioritizes holding, singleton certification, then exploration (Lines 1–8 of Algorithm 7). A held arm persists until deletion. An exploratory target persists until an accepted probe, deletion, or certification, even if it leaves the confidence set. Empty S disables certification and uses Ca (K) for exploration without restoring S. All exploratory requests satisfy the K-round cooldown based on acceptances in every mode (Lines 14–18 of Algorithm 7). A filler exists because the preceding K − 1 rounds contain at most K − 1 acceptances; it cannot be the uncooled target. Only held/probe rejections at hD,L ≤ h < fL extend z. Target creation, certification, fillers, acceptances, deletion, and rounds outside that window reset z. At z = K, the requested arm is deleted and held, target, and z are cleared, even if S is already empty (Lines 3–9 of Algorithm 8). Certification remains allowed at h = fL ; work always continues through h = JL − 1. Actual outputs and replay. After the final work feedback, let v be the actual request. Lines 12– 18 of Algorithm 8 use the old P, ℓ to compute (

r=

HL , ℓ = ⊥, HL + 2(a − ℓ), ℓ = ̸ ⊥,



P + = max P,



3P + r 4



,

(

P + , held ̸= ⊥ and the final request is accepted, HL , otherwise, (P, ℓ, y, q) ← (P + , a, v, a + L). L=

(50) Every actual output updates P, ℓ, including rejected or nonholding outputs; ℓ is unset until the first output. Call the held-and-accepted branch long, even if P + = HL , and the other branch short. Replay starts next round and repeats y. Acceptance retains q; rejection sets q ← max{a + 1, ℓ + HL }.

(51)

Lines 25–26 of Algorithm 4 implement this rejection update; Lines 7–8 enter fresh Seek on expiry, before the current request. Without shortening, replay occupies ages aout + 1, . . . , aout + L − 1; collection starts at aout + L. Output uses no extra round. 31

C.2

Local Algorithms

Algorithm 2 Overview of SC-PC 1: Maintain statistics. Update permanent statistics on every acceptance in every mode. Initialize Pi = HL and leave ℓi unset. 2: Serve locally. Every arm applies the same lease-based eligibility rule and selects the eligible requester with the oldest acceptance timestamp. 3: Collect. After three qualified BUS acceptances, enter work if armed or become a root otherwise. A root clears, scans, and commits through ordinary requests. 4: Work for JL rounds. Park, then keep a held arm or explore a fixed target with cooldown. Certify through h = fL ; delete only for hD,L ≤ h < fL . 5: Record the output. Save the arm requested in the final work round and update Pi , ℓi , qi by (50). 6: Replay and return. Request the saved arm. Rejection can shorten the deadline; expiry starts fresh collection while preserving all permanent records.

Figure 2: Player and Arm State Transitions of SC-PC. (a) The four player-local modes and their transitions. (b) The two service states used by every arm, determined by its local lease counter λ. BUS-AAA denotes three qualified consecutive acceptances at BUS. Player mode transitions triggered by feedback take effect in the next round. Algorithms 3–8 implement section C.1 using (46). In these algorithms, parameter subscripts L are omitted: in particular, χ = χL and J = JL . The registers a, ℓ, q use local ages, P, L are lengths measured in rounds, and h counts completed work rounds; ⊥ denotes an unset register. The player loop in Algorithm 4 orders each round’s transitions, request, statistics update, and feedback. StateUpdate initializes the state on entry; CollectionFeedback and WorkFeedback process the current outcome and schedule any resulting transition for the next round. WorkAction chooses the work request and its action type. The set S is the player’s remaining-arm 32

set. In the analysis of section C.3, the same letter denotes the physical round when common replay begins. During work, the pair (v, k) records both the requested arm and the action type, because probes and fillers have different effects on the target and rejection counter. A/R denotes acceptance or rejection feedback. Figure 2 summarizes the local modes and service states. Lemma 12 establishes the overlap of the work invocations and the common window in (54). Algorithm 3 Identical local service at every arm 1: Upon receiving the first request, set a = e = λ = 0. 2: In that round and every subsequent round, observe the requester set R. Before selection, initialize each

previously unseen handle i ∈ R with Ni = Ui = 0 and last[i] = −∞; leave the records of known handles unchanged. 3: If R = ̸ ∅, set Q = Ca (R) when λ > 0; otherwise set Q = R if a ≡ 0 (mod G), and Q = {min≺ R} if not. 4: If R ̸= ∅, accept requester i = arg minj∈Q (last[j], j in order ≺) and reject every other requester. If R = ∅, accept nobody. 5: After accepting a requester and observing the private reward r, set Ni ← Ni + 1, Ui ← Ui + r, and last[i] ← a. 6: Set e ← e + 1 if R = ∅, and e ← 0 otherwise. 7: Set λ ← τ if e ≥ 2; otherwise set λ ← max{λ − 1, 0}. 8: Set a ← a + 1 and repeat, including during empty rounds.

Algorithm 4 SC-PC: player loop 1: For every v ∈ K, set Nv = Uv = 0

and lastA[v] = −∞. 2: a ← 0; P ← H; ℓ ← ⊥; ν ← none 3: StateUpdate(Seekfresh ) 4: loop 5: if ν ̸= none then 6: StateUpdate(ν); ν ← none 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27:

if m = Replay and a ≥ q then StateUpdate(Seekfresh ) if m = Work then (v, k) ←WorkAction else if m = Replay then v←y else if m = Root, s = Scan, and ¬busNext then v←j else v ← BUS Propose to v once and observe o ∈ {A, R}. if o = A then Observe reward r; Nv ← Nv + 1 Uv ← Uv + r; lastA[v] ← a if m ∈ {Seek, Root} then CollectionFeedback(v, o) else if m = Work then WorkFeedback(v, k, o) else if o = R then q ← max{a + 1, ℓ + H} a←a+1

33

▷ m = Replay.

Algorithm 5 StateUpdate(u) 1: if u ∈ {Seekfresh , Seekarmed } then 2: m ← Seek; x ← 0 3: armed ← (u = Seekarmed ) 4: c ← a + J + χ + 4 5: if armed then b ← a; else b ← a + E 6: else if u = Root then 7: m ← Root; x ← 0 8: if a < c then 9: s ← Clear 10: else 11: s ← Scan; j ← 1 12: busNext ← true 13: else if u = Scan then 14: s ← Scan; j ← 1 15: busNext ← true 16: else if u = Commit then 17: s ← Commit; vC ← a 18: x ← min{x, 0} 19: else if u = Work then 20: m ← Work; h ← 0; S ← K 21: held ← ⊥; target ← ⊥; z ← 0 22: else 23: m ← Replay

▷ Retain c.

▷ u = Replay.

Algorithm 6 CollectionFeedback(v, o) 1: if v = BUS then 2: if o = A then x ← max{x, 0} + 1 3: else x ← min{x, 0} − 1 4: if m = Seek then 5: if x ≤ −3 then c ← a + J + χ + 3 6: if a ≥ b, x < 0, and min{−x, a − b + 1} ≥ K then 7: armed ← true 8: if a ≥ b + 2 and x ≥ 3 then 9: if armed then ν ← Work 10: else ν ← Root 11: return 12: if v = BUS and x = −K then 13: ν ← Seekarmed ; return 14: if s = Clear then 15: if a + 1 ≥ c then ν ← Scan 16: else if s = Scan then 17: if v = BUS then 18: busNext ← false 19: else 20: busNext ← true 21: if o = A then 22: if j = K − 1 then ν ← Commit 23: else j ← j + 1 24: else if a + 1 ≥ vC + M and x ≥ Rc then 25: ν ← Work

▷ s = Commit.

34

Algorithm 7 WorkAction() 1: if h < d then 2: z ← 0; return (PARK, park) 3: if held ̸= ⊥ then 4: return (held, hold) 5: if S ̸= ∅, h ≤ f , and |Ca (S)| = 1 then 6: v ← the unique element of Ca (S) 7: held ← v; target ← ⊥; z ← 0 8: return (v, hold) 9: if target = ⊥ then 10: if S ̸= ∅ then Q ← Ca (S) 11: else Q ← Ca (K) 12: target ← arg minv∈Q (Nv , v) 13: z ← 0 14: if a − lastA[target] ≥ K then 15: return (target, probe) 16: z ← 0 17: v ← min{w ∈ K : a − lastA[w] ≥ K} 18: return (v, filler)

Algorithm 8 WorkFeedback(v, k, o) 1: if k = probe and o = A then 2: target ← ⊥; z ← 0 3: if hD ≤ h < f , k ∈ {hold, probe}, and o = R then 4: z ← z + 1 5: else 6: z ← 0 7: if z = K then 8: S ← S \ {v} 9: held ← ⊥; target ← ⊥; z ← 0 10: if h < J − 1 then 11: h ← h + 1; return

Output: use the previous P, ℓ. 12: if ℓ = ⊥ then r ← H 13: else r ← H + 2(a − ℓ) 14: P + ← max{P, ⌊(3P + r)/4⌋} 15: if held ̸= ⊥ and o = A then L ← P + 16: else L ← H 17: (P, ℓ, y, q) ← (P + , a, v, a + L) 18: ν ← Replay

C.3

Collection and Recovery

We first bound the duration of inherited replay, then establish collection, mature handoff, and recovery. These results hold on every execution from the prescribed initialization, including histories affected by statistical errors. Collection and handoff are analyzed on intervals with a fixed population. Physical round indices translate the players’ local ages; the protocol itself uses only local ages. In collection arguments, “higher” refers to the private handle order at BUS, not to a reward mean.

35

C.3.1

Scale Envelope and Recovery Constants

The output recurrence bounds the lifetime of an inherited replay, including one based on an incorrect statistical decision. This is the scale bound needed for cold recovery. Lemma 10 (Scale envelope under the prescribed initialization). Let a0 < a1 < · · · be one player’s actual output ages and Pm its scale after output m. Then   am − a0 HL ≤ Pm ≤ HL + . (52) 2 An output at physical time O has natural replay deadline at most 3O/2 + HL . Rejections only shorten replay, without allowing collection before local age ℓ + HL . Proof. Initially P0 = HL . Set Xm = Pm − HL and δm = am − am−1 . Equation (50) gives 3Xm−1 + 2δm Xm = max Xm−1 , 4 





δm 0 ≤ Xm − Xm−1 ≤ . 2 

,



Summing proves (52) for all outputs, including short ones. Local-age differences equal physical-time differences, so an output at O, with first output at O0 ≥ 0, has deadline at most 

O + HL +

O − O0 3 ≤ O + HL . 2 2 

Replay feedback occurs only at a < q, hence a + 1 ≤ q. Since q ≥ ℓ + HL at entry, the update (51) preserves this lower bound and never increases q. Constants for collection and recovery.

For the collection and recovery bounds, define

Ls,L = 2K(K − 1)(GL + 1), C0 = 2τL + 2EL + 3JL + 2χL + GL + Rc,L + Ls,L + K + 32 = 39K 3 − 24K 2 + 156K − 26,

(53) VB = τL + KGL + 2 = 5K 3 − 2K 2 + 28K − 7, 5 5 CR = C0 + HL + κL + 16 = C0 + 8K + 12. 2 2 Here Ls,L bounds scan time, C0 a highest collector’s time to output, VB the time to recall BUS replayers, and CR cold recovery. All four are O(K 3 ) analysis bounds, not additional protocol inputs. The proof below derives C0 by adding the time for control service, clearing, scanning, commitment, and work; cold and warm recovery then reuse this one bound. C.3.2

Collection and Mature Handoff

Mature episodes and collection sets. A root entry into Work at round c0 is mature if, after round-start transitions, every other player is in armed Seek, BUS uses control service, every non-BUS arm has started and was empty in the preceding two rounds, and no old work invocation or replay remains. The root’s invocation and those following it form a mature episode. Players do not test maturity. The analysis tracks a growing collection set. At its starting round v, include every present player except those in non-BUS replay; in particular, include old Work players and BUS replayers. Excluded players join when their replays end and remain thereafter. Before the first work entry under consideration, the set contains every BUS requester, giving its highest member priority on ordinary control visits. A higher external join adds a player above that member; it is a collection-set entry by an already present player, not a market arrival. 36

Control service and the work handoff. Lemma 11 (Control service and the highest collector). In control service, a continuous requester is accepted within KGL rounds, and an alternating requester within 2KGL rounds. An old business lease adds at most τL rounds if requests leave no two consecutive empty rounds. Once control service is in effect, the highest member of a collection set containing every actual BUS requester cannot receive K consecutive rejections on its continuous or alternating BUS visits. Its presence also prevents a lower collector from obtaining three consecutive physical-round acceptances at BUS. Proof. Until its first acceptance, the requester’s timestamp stays fixed. Any player accepted ahead of it on a fair round acquires a newer timestamp and cannot precede it again on a fair round. Acceptance thus takes at most K fair rounds on which it requests. These occur every GL rounds for a continuous requester and, since GL is odd, every 2GL rounds for an alternating requester. Either pattern prevents lease renewal, so an old lease expires within τL rounds. The highest collector wins every ordinary control visit. Even with alternating visits, ordinary visits separate successive fair visits, preventing K ≥ 2 consecutive rejections. If a lower collector is accepted at t, the higher collector visits in t + 1 or t + 2. On an ordinary visit priority blocks the lower player; on a fair visit the higher player’s timestamp predates the lower player’s acceptance at t. A higher player joining from an excluded non-BUS replay has no BUS acceptance during collection, so its first request also interrupts any acceptance suffix begun during collection. These arguments use the private order, independently of reward preferences. Lemma 12 (Mature handoff and service intervals). If a mature root enters Work at c0 , each of the n players enters exactly once at ci ∈ [c0 , c0 + κL ], outputs at Oi = ci + JL − 1, and reaches first common replay at S = maxi Oi + 1. Every arm uses business service from the first nonparking work round c0 + dL through S + χL . The common interval I0 = [c0 + κL + hD,L , c0 + fL ) ∩ Z (54) contains WL rounds, throughout which every player is within its deletion window and has not passed its certification cutoff. Every actual deletion window, including those outside I0 , consists entirely of held or cooled exploratory requests by all players, with none parking or replaying. Proof. Bound the entry span. After the root leaves BUS, armed followers enter in its private order: three consecutive ordinary acceptances transfer the highest remaining follower. A fair rejection can break at most two acceptances, delaying entry by at most three rounds; it cannot interrupt the sole remaining follower. Between interruptions, GL − 1 = 2K + 2 ordinary rounds permit at least ⌊(2K + 2)/3⌋ transfers. Three interruptions would require 2⌊(2K + 2)/3⌋ ≥ K − 2 transfers before the third, leaving at most one follower and ruling it out. For K = 2, the sole follower needs at most three rounds. For 3 ≤ K ≤ 5, at most one interruption gives 3K ≤ 4K − 3 rounds. For K ≥ 6, the bound is 3(K − 1) + 6 ≤ 4K − 3 = κL . Maintain business service and identify the common window. Write δ = maxi ci − c0 ≤ κL . Since dL = κL + 2, all players park at both c0 + κL and c0 + κL + 1, refreshing the empty BUS’s lease. Other arms had two empty rounds just before c0 . Even this earlier refresh need cover only JL + κL + χL + 1 = JL + 2χL < τL rounds through S + χL ; later empty pairs can renew it. The identity fL − κL − hD,L = WL proves the claims about I0 . Check deletion and certification endpoints. A deletion at t by player i uses a K-rejection run starting no earlier than ci + hD,L , because the counter clears outside that window. Every other player’s work 37

index throughout the run is at least hD,L − κL = χL + 2 > dL , and t ≤ ci + fL − 1 ≤ c0 + κL + fL − 1 = c0 + JL − 2 < min Oj . j

Thus none is parking or has reached output or replay, and the action rule cools every nonholding request, including fillers. The latest certification is by c0 + κL + fL = c0 + JL − 1 = mini Oi , before that round’s feedback. Also, mini Oi + HL ≥ maxi Oi + 2 = S + 1, so minimum grace prevents fresh entry until every player has completed round S. From collection to mature entry. Clearing places scan acceptances after earlier replays’ minimum grace, allowing recall. Suppose a highest collector enters fresh Seek at w. Another player’s work entry at l ≤ w + 2 outputs at l + JL − 1, with minimum replay deadline l + JL + χL , at least two rounds before the initial clearing deadline w + JL + χL + 4. An entry l ≥ w + 3 before root nomination requires actual BUS acceptances at l − 3, l − 2, l − 1. The continuously requesting collector is rejected in all three rounds; the last rejection sets clearing to at least l + JL + χL + 2, again two rounds after minimum grace. After nomination, Lemma 11 prevents lower players’ work entries. Thus scanning starts after all old work and minimum grace. Old BUS replayers have already entered fresh: of the collector’s last two pre-scan BUS requests, at least one wins ordinary control service and rejects them after grace. If root entry skips clearing, its nomination acceptances suffice. The two-round margin covers a pending transition. At each other arm, the scan acceptance rejects all old replayers after grace, making them fresh next round. Let s be the last non-BUS scan acceptance. All recalled players are fresh by s + 1, and the latest guard occupies s + 1, . . . , s + EL . Commitment starts at s + 1 and lasts at least EL + K rounds, making its final K rounds post-guard; its final acceptance suffix gives every recalled seeker K rejections. An inherited root may start this suffix scanning off BUS, but its Kth rejected BUS visit occurs by suffix round 2K, followed by armed Seek. Thus all players are at BUS in the last two rounds of the Rc,L = 2K + 1 suffix. Every other arm has been started by the scan and is empty in both rounds. Such a suffix is available because GL − 1 = 2K + 2 ≥ Rc,L . This proves maturity when the final highest player completes collection after fresh entry, and will also apply to the first work entry after mature common replay. It need not hold for an arbitrary inherited lower root. Lemma 13 (An output time bound for the highest collector). Fix a population and a history reached from the prescribed initialization. Let z be the highest present player or the highest member of a collection set begun at v. By v + C0 , either z has an actual output or a higher external collector joins. An existing player’s output may be used; existing work has at most JL rounds left. For the highest present player, no higher external join is possible. Proof. Suppose z initially seeks or is a root, and follow it until a higher external join. Until work entry, it covers BUS continuously or alternately. The elapsed-time allowances are summarized below and justified in order. If work starts earlier, only its fixed remaining duration is needed.

38

Stage

Allowance in physical rounds

Expire the BUS lease and establish a root Clear inherited work and minimum replay grace Expire occupied-arm leases and finish the scan Commit and complete work

τ L + EL + 6 2(JL + χL + 4) τL + Ls,L EL + K + GL + Rc,L + JL

Total

C0 − 18

Establish control service. The old BUS lease expires within τL rounds. Set tc = v + τL and t1 = tc + EL + 6. A highest seeker finishes its guard within EL rounds and obtains three consecutive acceptances within six more. An inherited root visits BUS by tc + 1; if its old rejection suffix causes demotion, it enters armed Seek by tc + 2 and work within six further rounds, costing 8 ≤ EL + 6. Otherwise an ordinary acceptance clears the suffix, and fair rejections cannot cause demotion. Hence by t1 , unless already working, z is a root that cannot be demoted while highest, including by old work players in the collection set. Clear old work and finish scanning. The fixed clearing deadline has at most JL + χL + 4 rounds left. Allow another JL + χL + 4 for foreign work and minimum grace: Lemma 11 excludes foreign work entries after tc + 2. By then no foreign work remains; while z collects, no lower player can obtain a new root nomination or work entry. Each can finish at most one inherited root invocation, with at most (K − 1)2 remaining non-BUS scan acceptances in total. Another τL rounds, shared across arms, expire leases still continuously occupied by old replayers; an earlier-ending replay needs no allowance. Put t2 = t1 + 2(JL + χL + 4) + τL . Unless already working, z is then scanning or committing, no foreign work remains, and arms still occupied by old replayers use control service. There, its scan succeeds within 2KGL control rounds. At any other target, each rejection of z is an actual non-BUS scan acceptance by an inherited root. Counting intervening BUS visits and z’s own acceptances gives remaining scan time at most 2KGL (K − 1) + 2 (K − 1)2 + (K − 1) = Ls,L .

This includes roots not yet demoted and each target’s preceding BUS visit, including its first. Target updates take no extra round; the last acceptance starts commitment next round. Commit and output. Commitment takes at most EL + K + GL + Rc,L rounds for its minimum duration and a full ordinary acceptance suffix, then work outputs within JL more. The allowances sum to 2τL + 2EL + 3JL + 2χL + GL + Rc,L + Ls,L + K + 14 = C0 − 18. They count elapsed physical rounds, with next-round transitions and output included in work, leaving eighteen spare rounds in C0 unless a higher external collector joins first. C.3.3

Cold and Warm Recovery

Cold recovery from inherited states. Cold recovery covers every reachable state after stabilization, including those inherited from erroneous comparisons. Lemma 14 (Cold recovery, simultaneously for every starting time). On every execution from the prescribed initialization with a nonempty final population, for each integer v ≥ t∗ + 1 there is a mature episode whose remaining sets are all reset after v and whose common replay begins by 3 T (v) ≤ v + CR . 2 This holds simultaneously for all such v, without statistical correctness. 39

(55)

Proof. Obtain a fresh entry. For the final highest player z at BUS, Lemma 13 gives an output O ≤ v + C0 , possibly its existing replay’s output. Lemma 10 and replay shortening then give a fresh entry w ≥ v with 3 w ≤ (v + C0 ) + HL . 2 For existing replay use its actual expiry, processed at once if already due at v; for collection or work at v, use the next output and ensuing expiry. This output need not be mature: it only supplies fresh entry and discards inherited qualification. Complete a mature collection. Fresh entry erases old armed qualification. Throughout the EL -round guard, z requests BUS continuously, expiring its old lease before qualification. It cannot then receive K consecutive rejected control visits, so its next work follows its own root collection. Clearing, recall, and commitment make this entry mature: all old work and replay have ended, followers are armed, and every non-BUS arm was empty in the preceding two rounds. Lemma 13 from w, followed by Lemma 12, bounds common replay by 5 3 3 w + C 0 + κ L + 1 ≤ v + C0 + H L + κ L + 1 ≤ v + C R . 2 2 2 Every work reset is strictly after w, hence after v. The deterministic argument applies on each realized path to every integer v, simultaneously, even when v is not a stopping time. Warm recovery and consecutive actual outputs. Mature common replay gives bounded collection and identifies each player’s next actual output. Lemma 15 (Warm collection and adjacency of actual outputs). Suppose a mature episode reaches common replay at S and the population stays fixed. Let q0 be the first actual fresh entry after S. The next episode is mature, with common replay S ′ satisfying S ′ − q0 ≤ VB + KC0 + κL + 1.

(56)

Each player has exactly one new work invocation and actual output between these common replays, so that output uses its stored record from the preceding mature episode. This holds regardless of statistical errors or replay correctness. Proof. Recall BUS replayers. Lemma 12 gives q0 ≥ S + 1. The first fresh player requests BUS continuously until accepted, by q0 + τL + KGL under residual business service and control fairness. This rejects every old BUS replayer. Each minimum grace deadline is at most S + χL : rejection before grace sets that deadline by (51), and rejection after grace gives fresh entry next round. In either case every old BUS replayer is fresh by q0 + VB , even if several erroneous outputs replay BUS. Establish maturity of the first new work entry. Until that entry, the growing collection set contains the old BUS replayers, all players already fresh, and hence every BUS requester. Unjoined players repeat fixed non-BUS outputs; no new output has returned anyone to replay. Replayers cannot qualify before becoming fresh, which resets their armed flags. A collector keeps covering BUS, preventing lease renewal, so every fresh guard ends after control service begins. The current highest collector has been highest since joining, as higher members cannot leave. After its guard it cannot become armed, while lower armed seekers cannot obtain three consecutive acceptances in its presence. A still higher join interrupts any such suffix on its joining round through its old BUS timestamp. Thus the first new work entry must follow root collection. That root’s fresh guard and clearing put its scan after all old minimum grace deadlines. Its BUS and scan acceptances recall every old replayer, so all have joined by the round after the last 40

scan acceptance. A higher collector would interrupt the final acceptance suffix; a completing root is therefore highest. Minimum commitment gives the last recalled seeker a full guard and K subsequent rejections; the last 2K + 1 acceptances demote residual roots and give two empty rounds at every other arm. The first work entry is mature. Bound the time and identify adjacent outputs. After the initial VB rounds, divide collection at higher external joins. Each raises the highest collector’s priority, giving at most K segments. In each, Lemma 13 gives an output or higher join within C0 rounds. The last includes root work; Lemma 12 adds at most κL + 1 rounds to common replay. Work beginning during the initial allowance also fits, with its fixed remainder and handoff. This proves (56). No new output preceded the first work entry. Its mature handoff starts exactly one fixed-length invocation per player, and minimum grace prevents another fresh entry before S ′ . Each player thus outputs exactly once; since only actual outputs update its persistent record, it uses exactly the preceding mature output’s record.

C.4

Stable-Edge Protection, Absorption, and Sample Progress

The recovery guarantees above hold regardless of statistical errors. We now use comparison coverage to protect stable edges and identify the POSM, then introduce the sample threshold needed to charge failed episodes to permanent samples. C.4.1

Comparison Coverage and Good Episodes

Writing θx for the true mean of option x, a positive-count comparison is covered when (θbx − θbz ) − (θx − θz ) ≤ βa (x, z).

(57)

Under coverage of all comparisons in a nonempty set, its true best option cannot be excluded. A singleton confidence set therefore certifies that option. An episode is good if all comparisons between each player’s K arms and at each arm between present players are covered from the first remaining-set reset through the end of the first common replay round, including earlier certificates used by later deletion witnesses. It is successful if, at common replay, every player holds an arm and the saved outputs are distinct. Collection remains valid after incorrect statistical decisions. C.4.2

Stable-Edge Protection and POSM Absorption

The POSM benchmark. Player-proposing deferred acceptance yields the POSM in a finite strict market [GS62]. Rejection by all K arms would require K other retained players, impossible for n ≤ K. A first rejection of a stable edge would be caused by a preferred proposer whose own stable partner had not yet rejected it, yielding a blocking pair. Thus no stable edge is rejected. At termination, each player receives its best stable arm: every preferred arm rejected it and retains a better proposer. We use this characterization to identify SC-PC’s absorbing assignment. Lemma 16 (A held witness for every deletion). In a mature good episode, if player i deletes arm a, some other player j whom a prefers to i held and requested a during the K-rejection window. The witness need not have been accepted in that window. Proof. The K rejections of i require K acceptances among at most K − 1 other players. Some player w is accepted twice, at arm ages r < s with s − r ≤ K − 1. Lemma 12 excludes parking and

41

replay; cooldown excludes an exploratory request by w at s. Thus w holds a. If a prefers w to i, it is the required witness. Otherwise let z be a’s best requester at s. If z ̸= i is a holder, it is the required witness. In the remaining cases, z = i has been rejected throughout the window, or z is exploring and has no acceptance at a in the preceding K − 1 rounds. Just before service at s, either case gives last[z] < r ≤ last[w]. Coverage keeps z eligible, so oldest-timestamp service cannot select w, a contradiction. No sample threshold or gap bound is needed. Lemma 17 (Stable-edge protection and absorption). A mature good episode deletes no edge of any stable matching. Every held arm is weakly preferred by its holder to its POSM arm. If all players hold distinct arms, their assignment is the POSM and persists until the next collection. There are at most (n − 1)2 deletions in an n-player episode. Proof. Stable edges. Suppose (i, a) is the first deleted stable edge, and fix a stable matching containing it. Lemma 16 gives a holder j whom a prefers to i. At j’s certification of a, its partner in that matching remained available. Coverage makes a its true best remaining arm, so (j, a) blocks the matching. This also handles simultaneous deletions: all certificates use round-start sets, before feedback deletes any edge. Every stable edge is therefore protected; in particular, every held arm is at least as good for its holder as its still-available POSM arm. Persistent holders and absorption. Before collection resumes, an arm’s best historical holder cannot have deleted it: a deletion witness would be an even better historical holder. Holding otherwise persists, including through output and replay, so every previously held arm retains a holder. If all players hold distinct arms, an arm preferred by a player to its current assignment must have been deleted before certification. Its witness, and hence its best historical holder, is preferred to that player by the arm. No deleted arm can be unoccupied. The assignment is therefore stable and weakly better for every player than the POSM, hence equal to it under strict preferences. With one requester per occupied arm, all subsequent requests are accepted until collection. Deletion count. The first time n distinct arms have been held, their persistent holders account for all n players, giving absorption. Before then, deletions concern at most n − 1 ever-held arms. Each such arm’s best holder over the episode never deletes it, and each of the other players deletes it at most once. Thus there are at most (n − 1)2 deletions. C.4.3

Samples Collected by Failed Episodes

Stable-edge protection uses full coverage alone; the restricted gap quantifies sample progress. For the nonempty final market, use ∆min from (11). For an integer horizon T ≥ 2, define the analysis threshold j k QT = 1 + 40∆−2 log T . (58) min If a ≤ T and both counts are at least QT , then a + 2 ≤ T 2 and log(a + 2) ≤ 2 log T , so s

βa (x, z) ≤

10 log T ∆min < . QT 2

Under coverage, a gap of at least ∆min then excludes the inferior option whenever the superior option is present. Neither QT nor the gap is a protocol input.

42

Fix a mature good episode of the final population with common replay by T ; all relevant ages are at most T . An acceptance is insufficient if its edge count just before acceptance is below QT . Both endpoints have that same count. Recall Ei∗ = {x : µi,x ≥ µi,m∗ (i) }. The sample argument has three steps. A target created before the certification cutoff must still need samples; otherwise the player would certify instead. A block without sample progress must then either delete an arm or reach the POSM. Since an episode permits only finitely many deletions, a failed episode must collect a fixed sample quota. Lemma 18 (Fixed probe targets remain insufficiently sampled in the common window). Every exploratory target maintained in I0 has player count below QT , even if it has left the current confidence set. Proof. Such a target was created before the player’s certification cutoff. Stable-edge protection keeps the remaining set nonempty; its true best arm lies in Ei∗ and remains a candidate. By (11), the player-side gap between that best arm and any inferior candidate is at least ∆min . If all candidates had counts at least QT , coverage and (58) would let that best arm exclude every inferior candidate. The resulting singleton would be certified before target creation. Thus the least-sampled candidate selected as target has count below QT . While retained, the target’s count cannot change: an accepted probe or a new certificate clears it, and a filler cannot request the uncooled target. The conclusion therefore holds even after the target leaves the confidence set. It need not hold for targets created after the certification cutoff. Lemma 19 (A cooled block and the amortized inequality). Consider K consecutive rounds in I0 with no insufficient acceptance in the block or the preceding K − 1 rounds. If the block contains no deletion, absorption at the POSM occurs by its last round. Consequently, every prefix I of I0 ending before absorption satisfies |I| ≤ KDI + (2K − 1)BI + 2K − 2, (59) where DI and BI count deletions and insufficient acceptances in I, respectively, with each accepted edge counted separately. Proof. A block with neither kind of event. At its first action, each player holds an arm, possibly certifying it then, or explores. An explorer’s target is insufficient by Lemma 18. Any acceptance at that target in the preceding K − 1 rounds would also have been insufficient, so the target is cooled. Every subsequent probe acceptance would be insufficient as well. Without acceptance or deletion, the player’s statistics and remaining set stay fixed; increasing age only widens the confidence radii, so a nonsingleton cannot become a singleton. The player therefore probes for K rounds and deletes, a contradiction. All players must hold from their first action. If two fixed holders share an arm, let z be its true best requester, which remains eligible under coverage. If z’s edge is insufficient, its timestamp cannot change without an insufficient acceptance. Each other requester can be served ahead of it at most once, so the arm accepts z within K rounds, a contradiction. If its edge is sufficient, every sufficient inferior holder is excluded: both held edges lie in the respective Ei∗ sets, so their arm-side gap is at least ∆min . The block rules out insufficient acceptances, so the arm accepts only z throughout it. Any inferior holder then deletes after K rejections. Thus all held arms are distinct, and Lemma 17 gives absorption. Charge the rounds before absorption. The block argument charges time either to deletions or to insufficient acceptances and their cooldowns. Mark the first K − 1 rounds of I and each insufficientacceptance round together with its next K − 1 rounds, truncated at the endpoint. There are at most KBI + K − 1 marked rounds and at most BI + 1 unmarked intervals. Every disjoint K-round

43

block in an unmarked interval must contain a deletion; otherwise absorption would persist to the end of I. An interval with d deletions thus has length at most Kd + K − 1. Summing gives |I| ≤ KBI + K − 1 + KDI + (BI + 1)(K − 1), which is (59). The initial marks cover insufficient acceptances before I; subsequent cooldown is charged to insufficient acceptances within it. Lemma 20 (Sample density and the first fresh entry). For the nonempty final market, fix T ≥ 2 and the threshold QT from (58). Every failed mature good episode with common replay by T contains at least bK = 2K 2 insufficient acceptances, and there are at most ⌊QT /2⌋ such episodes. For any mature good episode in a fixed population, let S be its first common replay round. If the episode succeeds, it replays the POSM until the first fresh entry; if it fails, that entry occurs by S + χL . Proof. Sample quota and failure count. Absorption during I0 persists through output and common replay, so a failed episode cannot be absorbed there. If it had at most bK − 1 insufficient acceptances in I0 , Lemma 17 and (59) would give WL ≤ K(K − 1)2 + (2K − 1)(bK − 1) + 2K − 2 = WL − 1, a contradiction. The permanent potential ΦT =

X X

max{0, QT − Ni (a)} ≤ nKQT ≤ K 2 QT

i∈P∞ a∈K

never increases and drops by one at each insufficient acceptance. Distinct mature episodes have disjoint common windows, so at most ⌊K 2 QT /bK ⌋ = ⌊QT /2⌋ can fail, regardless of intervening successes or additional samples. First fresh entry. By Lemma 12, certifications end by the earliest output’s action and deletions end strictly before it. Hence all output holders are already fixed at that action. In a successful episode, these fixed holders request distinct arms in every output round, so every final request is accepted and every output takes the long branch. If all outputs are long and distinct, the players hold the POSM, which persists until collection. Otherwise, either a short output has deadline Oi + HL ≤ S + χL , or two long outputs coincide and at least one is rejected at S. Its shortened deadline satisfies max{S + 1, Oi + HL } ≤ S + χL . Thus a failed episode has a fresh entry by S + χL , while minimum grace places every such entry after S.

C.5

Counting Episodes and Mismatch Cost

The preceding sample bound controls failures. We next bound mismatch between consecutive common replay rounds and use scale growth to count successes. Permanent counts and replay scales persist along the same consecutive chain.

44

Mismatch cost between common replay rounds.

Define the per-interval cost bound

CF = KC0 + VB + κL + χL + 16

(60)

= 39K 4 − 19K 3 + 154K 2 + 10K + 4.

The four terms charge collection, recall of BUS replayers, output misalignment, and the short delay before fresh entry; the remaining constant absorbs endpoints. Thus CF = O(K 4 ) bounds a whole interval between common replay rounds, including its final partial prefix. Lemma 21 (At most CF mismatched rounds in a warm interval). Suppose a mature good episode reaches common replay at S and the population remains fixed. If S ′ is the next mature common replay, then D([S, S ′ ); I) ≤ CF . The bound also holds for every truncation [S, min{S ′ , T }), T > S, including horizons inside the next collection or work invocation. Proof. Let q0 be the first fresh entry after S. By Lemma 20, [S, q0 ) has zero cost after success and length at most χL after failure. Lemma 15 bounds the rest, regardless of the successor’s statistical correctness: D([S, S ′ ); I) ≤ χL + (S ′ − q0 ) ≤ χL + VB + KC0 + κL + 1 ≤ CF . Truncation only reduces cost. Source goodness is essential: an incorrect injective replay may receive no rejection. Cold recovery will account for that case. Scale growth and the number of successes. Lemma 22 (Minimum-scale growth after a successful episode). Consider consecutive mature episodes s, s + 1 in a fixed population, with s good and successful and s + 1 completed. Write Oi,s = Os + δi,s ,

Os = min Oi,s , i

0 ≤ δi,s ≤ κL ,

ps = min Pi,s , i

where scales are measured after output. Even if the successor fails, 

ps+1 ≥

5ps + HL + 2(JL − κL − 1) 5 > ps . 4 4 

(61)

Every individual scale is nondecreasing. Along any consecutive mature good chain, the number NS (T ) of successes with common replay by T satisfies 



NS (T ) ≤ 1 + log5/4 1 +

T 2HL



.

(62)

Proof. Growth. After success, the POSM has one requester per occupied arm until the first fresh entry, even if business leases expire. Every replay request is accepted, so this entry occurs at qs = min(Oi,s + Pi,s ) ≥ Os + ps . i

Each next work invocation starts at or after qs and lasts JL rounds. Warm output adjacency therefore gives ∆i,s+1 := Oi,s+1 − Oi,s ≥ ps + JL − κL − 1.

45

Substituting Pi,s ≥ ps and this interval into (50) proves the first inequality in (61). Since HL + 2(JL − κL − 1) > 4 and ⌊x⌋ > x − 1, the second inequality is strict. Every actual output performs the update, so neither success nor coverage is required of the successor. Count successes. Outputs in a counted episode precede T , so (52) gives HL ≤ ps ≤ HL + T /2. If NS (T ) ≥ 1, each of its first NS (T ) − 1 successes has a completed immediate successor in the counted chain. Growth at those transitions and monotonicity through failures yield (5/4)NS (T )−1 HL ≤ HL + T /2. This proves (62); zero successes are immediate. The additive one allows the last success an unfinished successor. Combining the episode counts. For T ≥ 2, combine Lemma 20 with (62). In a consecutive mature good chain of the final market, QT Nfail (T ) + NS (T ) ≤ 2 





+ 1 + log5/4

T 1+ 2HL





,

(63)

where Nfail (T ) counts failures with common replay by T . Thus the logarithmic maintenance term is paid once over the entire chain.

C.6

Concentration and Recovery from Statistical Errors

The preceding bounds apply to a chain of mature good episodes. We now bound the time until such a chain begins, using concentration and two cold recoveries. A maximal inequality at prescribed sample counts handles both adaptive sampling and random arm startup. C.6.1

Adaptive Concentration

Let Ft−1 contain the history before physical round t, and Ht also contain current requests and acceptance decisions, before rewards. An accepted stream-x reward lies in [0, 1] with conditional mean θx given Ht . Rewards may be dependent across time, edges, and endpoints. Since conditioning on another endpoint’s current reward can change this mean, we analyze each player or arm separately as an owner receiving at most one sample per round, then take a union bound. Lemma 23 (Time-uniform concentration for prescribed sample counts). Fix an owner, two distinct streams, and deterministic positive integers n, r. Weight the first n accepted samples of the first stream by 1/n, the first r of the second by −1/r, and all other physical rounds by zero. Let Xt be the weighted centered sum through round t and Vt the sum of squared weights. For every b > 0, (

2b2 Pr sup |Xt | > b ≤ 2 exp − 1/n + 1/r t 



)

.

(64)

For owner o and a fixed family of at most K streams, let Bado,a mean that some comparison in this family with positive counts is uncovered at the start or end of the round at local age a. Then Pr(Bado,a ) ≤

K(K − 1) a(a + 1) . 2 (a + 2)5

Both conclusions cover random arm startup times.

46

(65)

Proof. A maximal bound at prescribed counts. Let wt be the round-t weight and, when nonzero, let Rt , θt be the selected reward and mean. The weight is fixed by Ht before the reward, and truncation gives Vt ≤ vn,r := 1/n + 1/r. Conditional Hoeffding’s lemma gives h

i

2

2

E eλwt (Rt −θt ) | Ht ≤ eλ wt /8 . Zero weights give zero increments. Conditioning successively on Ht and Ft−1 makes Mt (λ) = exp{λXt − λ2 Vt /8} a nonnegative supermartingale initially equal to one. Ville’s inequality bounds the chance that this process ever exceeds exp{λb − λ2 vn,r /8} by its reciprocal. Choosing λ = 4b/vn,r and repeating for −Xt gives (64), using the ownerwise boundedincrement construction of [HRMS20]. This argument uses the conditional reward assumption, not independence between accepted samples. Union over counts and comparisons. At counts n, r, the truncated sum is the empirical difference error. Thus coverage failure lies in a maximal event from (64), without conditioning on realized counts or assuming conditional IID samples. With s

b=

5 log(a + 2) vn,r , 2

its probability is at most 2 exp{−5 log(a + 2)} = 2(a + 2)−5/ ln 2 ≤ 2(a + 2)−5 . Each age-a snapshot contains
at most a + 1 observations, allowing a(a + 1)/2 positive count pairs n + r ≤ a + 1 and at most K2 unordered stream pairs. Their union proves (65). The same maximal events cover both snapshots without another factor of two. At age zero, two counts cannot both be positive; zero counts give infinite radii. Random startup times. The process uses all physical rounds, with zero weights before startup and whenever no sample arrives. The supremum already includes the random round at each fixed arm age, requiring neither a union over startup times nor conditioning on them. C.6.2

Recovery after the Last Bad Comparison

To bound the expected sum of the last bad local ages, set CY =

K 2 (K − 1) . 4

(66)

Lemma 24 (The last bad age and two cold recoveries). For a nonempty final population, almost surely a mature episode reaches common replay at R∗ with all remaining-set resets and work rounds after every bad comparison among the final players’ arms or between final players at an arm. All subsequent comparisons in these families are covered, and 9 5 3 ER∗ ≤ (t∗ + 1) + CR + (1 + CY ). 4 2 2 The cost before R∗ includes all mismatch during recovery from earlier errors. 47

(67)

Proof. The two recoveries have different purposes. The first bounds every arm’s startup time, converting a bound on bad local ages into a bound on bad physical rounds. The second resets the work states after those bad comparisons. Neither step discards permanent samples. The oblivious schedule fixes the final identities. Comparisons by final players over their K arms and by all K arms over final players involve at most 2K owners, including comparisons outside the restricted gap (11). Departed players’ records persist but leave requester sets after stabilization, so they do not enlarge this union. Bound the last bad local ages. Let Yo be owner o’s last bad local age, or zero if none. It is dominated by X a1{Bado,a }. a≥1

Tonelli’s theorem and (65) give E

X

Yo ≤ K 2 (K − 1)

o

X a2 (a + 1) a≥1

(a + 2)

< 5

K 2 (K − 1) = CY . 4

Indeed, a2 (a + 1)/(a + 2)5 ≤ a/(a + 2)3 , and x/(x + 2)3 is nonincreasing for x ≥ 1, so 4 X a a ≤ + 3 (a + 2) (a + 2)3 a=1 a≥1

X

Z ∞ 4

x 8989 1 dx = < . (x + 2)3 36000 4

Finite expectation makes every last bad age finite almost surely, without independence between owners or errors. First recovery: start every arm clock. Apply Lemma 14 at v = t∗ + 1. Regardless of errors, its root scan starts every arm by 32 (t∗ + 1) + CR ; final players are born by t∗ . Let Z be the maximum of t∗ + 1 and the last physical bad-comparison round in these families, using t∗ + 1 if none. Thus X 3 Yo , Z ≤ (t∗ + 1) + CR + 2 o

3 EZ ≤ (t∗ + 1) + CR + CY . 2

Second recovery: clear inherited work states. Lemma 14 holds pathwise for every integer starting time. Applied at v = Z + 1, it gives a mature episode with all remaining sets reset after Z and common replay at 3 R∗ ≤ (Z + 1) + CR . 2 Choose the least such integer round. Each candidate event is measurable in Z and the execution, so this countable minimum is measurable; set R∗ = 0 on the null event of no candidate. Its certificates and all subsequent comparisons are covered. Taking expectations proves (67). This pathwise substitution needs no stopping-time assumption, restart, or conditioning on Z. Both recoveries retain statistics, scales, and output records. Charging [1, R∗ ) covers erroneous stable-edge deletions, inherited armed or root states, and incorrect injective long replays without rejections.

C.7

Proof of Theorem 4

We combine the episode bounds from Section C.5 with the expected recovery time from Section C.6, including any final incomplete collection or work interval.

48

Proof. Charge the finite prefix. First suppose the final population is nonempty and T ≥ 2. On the probability-one event of Lemma 24, charge every round before R∗ . This covers the prefix if T < R∗ . Otherwise set S0 = R∗ and follow the consecutive mature episodes from warm collection. All are good: remaining sets reset after Z, and later comparisons are covered. Count episodes with common replay round Ss ≤ T : a final output at T − 1 followed by replay at T is counted, whereas an output at T followed by replay at T + 1 is not. Lemma 21 bounds the cost on each interval [Ss , min{Ss+1 , T + 1}). These partition [R∗ , T + 1), including unfinished collection or Work. Equation (63) bounds their number, yielding ∗



D(T ; I) ≤ R + CF

QT 2







+ 1 + log5/4

T 1+ 2HL



.

(68)

Each counted failed episode obtains its sample quota in a completed common work window before T , so QT is applied only at local ages at most T . The scale argument likewise uses only successor outputs recorded before the horizon. Take expectations. Equations (68) and (67), together with D(T ; I) ≤ T , give (

5 3 9 ED(T ; I) ≤ min T, (t∗ + 1) + CR + (1 + CY ) 4 2 2 

+ CF

QT 2





+ 1 + log5/4



T 1+ 2HL

(69)

 )

.

Simplify with uniform constants. For every K ≥ 2, the definitions in (53), (60), and (66) give the following ledger. Each bound is uniform over instances and horizons. Quantity

Elementary upper bound

Bound used below

C0 CY CR CF (5/2)CR + (3/2)(1 + CY )

39K 3 + 156K K 2 (K − 1)/4 (5/2)(78K 3 ) + 8K + 12 39K 4 + 154K 2 + 10K + 4 (5/2)(199K 3 ) + (3/2)(1 + K 3 /4)

78K 3 K 3 /4 199K 3 80K 4 500K 3

Put x = log T ≥ 1 and δ = ∆−2 min ≥ 1. Since QT = 1 + ⌊40δx⌋, we have ⌊QT /2⌋ ≤ 1/2 + 20δx. Also HL ≥ 1, T ≥ 2, and log(5/4) > 1/5 give 1 + T /(2HL ) ≤ T and bound the bracket in (69) by 3 + (20δ + 5)x ≤ 28δx. 2 Since K ≥ 2 and δx ≥ 1, we may charge the recovery constant to the same logarithmic term: 500K 3 ≤ 500K 4 δx. Consequently, 500K 3 + 80K 4 (28δx) ≤ (500 + 80 · 28)K 4 δx = 2740K 4 δx. Finally, 2740 ≤ 4000 and (9/4)(t∗ + 1) ≤ (9/2)t∗ give 9 ED(T ; I) ≤ min T, t∗ + 4000K 4 ∆−2 min log T . 2 



49

(70)

Endpoint horizons. At T = 1, the same bound follows from ED(1; I) ≤ 1 ≤ t∗ . Theorem 4 therefore holds for every integer T ≥ 1, with one constant for all admissible parameters, instances, and reward processes, and no extra log K factor. At T = 0, D(0; I) = 0 separately. Empty final population. Both matchings are empty from round t∗ onward, so D(T ; I) ≤ min{T, t∗ − 1}, without a gap parameter. A permanently empty market has zero cost.

50

D

Proof of Claim 1

Throughout this appendix, log is base two, while ln and the relative entropies KL and kl use natural logarithms. We use independent Bernoulli rewards at both endpoints of every accepted edge, a subclass of the conditional-mean model. The protocol and arm-service rules are fixed before the unknown means are chosen. Rejections supply neither reward observations nor an exogenous ranking oracle. The argument also applies to a central controller that chooses feasible matchings and observes all accepted rewards, and hence can simulate the local protocol. Lemma 25 (Information required by a one-edge alternative). Let θ and λ be static strict Bernoulli instances with the same population, differing only in one endpoint mean on an edge e, from p to q, where p, q ∈ (0, 1). Suppose e is absent from the POSM of θ and present in the POSM of λ. If the protocol is uniformly efficient on both instances, then lim inf T →∞

Eθ Ne (T ) 1 ≥ , ln T kl(p, q)

where Ne (T ) counts acceptances of e, and kl uses natural logarithms. Proof. Let θ and λ denote two static mean instances with the same population and endpoint means µi,x and πx,i , as in Section 2. Let Ni,x (T ) count acceptances of edge (i, x) in the first T rounds. We compare the instances with identical initial local information and private handle orders. The full transcript records all proposals, acceptance/rejection decisions, accepted rewards at both endpoints, and the protocol’s parameter-independent random sources. Write PTθ for its law and Dθ (T ) for the POSM-mismatch cost under θ. Write KL for relative entropy and kl for its Bernoulli specialization. The random sources have the same law in both instances and contribute zero relative entropy. Conditional on these sources and the observed history, action and state-update rules are identical in the two instances. Thus the chain rule gives KL(PTθ , PTλ ) =

X

n

o

θ λ Eθ Ni,x (T ) kl(µθi,x , µλi,x ) + kl(πx,i , πx,i ) .

(71)

i,x

For the one-endpoint change in the lemma, this reduces to KL(PTθ , PTλ ) = Eθ Ne (T ) kl(p, q), because the other endpoint of e and both endpoints of every other edge have unchanged reward laws. Only newly observed rewards contribute divergence; rejections and local state transitions contribute no additional term. Equation (71) specializes the adaptive change-of-measure identity to two observations per accepted edge; see also [KCG16, Lemma 1]. The assumed POSM memberships of e give Ne (T ) ≤ Dθ (T ),

T − Ne (T ) ≤ Dλ (T )

pathwise in their respective instances. For a uniformly efficient protocol and every α ∈ (0, 1), the event AT = {Ne (T ) < T /2} satisfies Pθ (AT ) = 1 − o(T α−1 ),

Pλ (AT ) = o(T α−1 ).

This follows directly from Markov’s inequality and the definition of uniform efficiency. Binary data processing and the bound on binary entropy imply KL(PTθ , PTλ ) ≥ Pθ (AT ) ln 51

1 − ln 2. Pλ (AT )

Divide by ln T , take the lower limit, and then let α ↓ 0. Using (71), we obtain Eθ Ne (T ) 1 ≥ . T →∞ ln T kl(p, q)

lim inf

(72)

Proof of Claim 1. Fix K and ∆ as in Claim 1. Original instance and unique stable matching. Let the players be p0 , . . . , pK−1 and the arms 0, . . . , K − 1. Each player other than p0 will form a mutual first-choice pair with a distinct arm, leaving p0 its last choice. Reversing one arm’s preference between its owner and p0 changes the POSM; learning those comparisons will account for the lower bound. Choose player means 1 µp0 ,j = + (K − 1 − j)∆, 2

(

3/4, j = r − 1, 1/8 + (j + 1)/(8K), j = ̸ r − 1,

µpr ,j =

1 ≤ r < K.

On each arm j < K − 1, set 1 πj,pj+1 = , 2

πj,p0 =

1 − ∆, 2

πj,pr =

1 r + 8 8K

(r ∈ / {0, j + 1}).

On the last arm, set πK−1,p0 = 3/4 and πK−1,pr = 1/8 + r/(8K) for r ≥ 1. All means are interior and all local rankings are strict. In each pair (pr , r − 1), r ≥ 1, the endpoints are mutual first choices, so the pair occurs in every stable matching. The remaining player p0 receives arm K − 1, giving a unique stable matching. The restricted gap. For this instance, Ep∗0 = K,

Ep∗r = {r − 1}

(r ≥ 1).

Among the means of player p0 , the smallest positive difference is ∆. For each other player, the reward gap between its assigned first choice and any other arm is at least 1/2. At each arm j other than the last, the only distinct players whose relevant sets both contain that arm are p0 and pj+1 ; the difference between their means at this arm is ∆. The last arm belongs only to the remaining player’s relevant set. Consequently ∆min = ∆ exactly. Gaps between low-valued options outside these comparison families do not enter the restricted gap. A one-edge alternative. For each j < K − 1, change only πj,p0 to 1/2 + ε, where 0 < ε < 1/8. All player means remain fixed. The endpoints of the other K − 2 owner pairs remain mutual first choices. In the remaining market, p0 prefers j to K − 1 and j prefers p0 to its former owner, so (p0 , j) belongs to every stable matching. The displaced owner receives K − 1, again giving a unique stable matching. The only matching edges that change are {(p0 , K − 1), (pj+1 , j)}

−→

{(p0 , j), (pj+1 , K − 1)}.

For Nj = Np0 ,j , Lemma 25 gives lim inf T →∞

ENj (T ) 1 ≥ . ln T kl(1/2 − ∆, 1/2 + ε)

The bound holds for every fixed 0 < ε < 1/8, with the limit inferior taken first as T → ∞. Since its left-hand side concerns the same original instance for every ε, continuity of kl allows us to let ε ↓ 0 on the right-hand side. 52

From samples to mismatch rounds. Each acceptance of one of these edges in the original instance incurs a mismatch. All these edges share player p0 , so at most one can be accepted in any round. Hence X Nj (T ) ≤ D(T ). j<K−1

For fixed K, the finite sum gives X ED(T ) ENj (T ) K −1 ≥ lim inf ≥ . T →∞ T →∞ ln T ln T kl(1/2 − ∆, 1/2) j<K−1

lim inf

The KL constant and logarithm conversion. For p ∈ [3/8, 1/2], the second derivative of p 7→ kl(p, 1/2) is 1/[p(1 − p)] ≤ 64/15. Its value and first derivative vanish at p = 1/2, so Taylor’s theorem and ∆ ≤ 1/8 give kl(1/2 − ∆, 1/2) ≤

32 2 ∆ < 4(ln 2)∆2 . 15

Converting the normalization in (72) to base two and summing therefore gives ED(T ) (ln 2)(K − 1) K −1 ≥ ≥ . T →∞ log T kl(1/2 − ∆, 1/2) 4∆2

lim inf

All alternatives change only arm means. The construction therefore proves Claim 1 even when all player means are revealed and accepted observations are centralized: the uncertainty responsible for the bound lies entirely on the arm side. Comparison with binary stability. The constructed instance has a unique stable matching, so unstable-round loss and POSM-mismatch loss coincide on this family. In markets with several stable matchings, D(T ) also charges a stable assignment whenever it is not player-optimal; binary-stability loss does not [Bas25]. The comparison in Claim 1 concerns the logarithmic horizon growth and the inverse-square dependence of its asymptotic coefficient on the restricted gap used here: for each fixed K and ∆, the lower limit is taken as T → ∞.

References [Bas25]

Soumya Basu. Competing bandits in matching markets via super stability. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 3226–3250. PMLR, 2025.

[BBB+ 18]

Joffroy Beauquier, Thibault Bernard, Janna Burman, Shay Kutten, and Marie Laveau. Brief announcement: Time efficient self-stabilizing stable marriage. In Stabilization, Safety, and Security of Distributed Systems, volume 11201 of Lecture Notes in Computer Science, pages 387–392. Springer, 2018.

[BCK+ 20]

Robert Bredereck, Jiehua Chen, Dušan Knop, Junjie Luo, and Rolf Niedermeier. Adapting stable matchings to evolving preferences. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 1830–1837, 2020.

[BSS21]

Soumya Basu, Karthik Abinav Sankararaman, and Abishek Sankararaman. Beyond log2 (T ) regret for decentralized bandits in matching markets. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 705–715. PMLR, 2021. 53

[CHDK+ 21] Keren Censor-Hillel, Neta Dafni, Victor I. Kolobov, Ami Paz, and Gregory Schwartzman. Fast deterministic algorithms for highly-dynamic networks. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020), volume 184 of Leibniz International Proceedings in Informatics (LIPIcs), pages 28:1–28:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. [CHK+ 14]

Edith Cohen, Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Danny Raz, and Yoav Tzur. Probe scheduling for efficient detection of silent failures. Performance Evaluation, 79:73–89, 2014.

[DE22]

David Doty and Mahsa Eftekhari. Dynamic size counting in population protocols. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022), volume 221 of Leibniz International Proceedings in Informatics (LIPIcs), pages 13:1–13:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022.

[ES25]

S. Rasoul Etesami and R. Srikant. Decentralized and uncoordinated learning of stable matchings: A game-theoretic approach. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 23160–23167, 2025.

[GS62]

D. Gale and L. S. Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9–15, 1962. doi:10.1080/00029890.1962.11989827.

[GSR+ 24]

Avishek Ghosh, Abishek Sankararaman, Kannan Ramchandran, Tara Javidi, and Arya Mazumdar. Competing bandits in non-stationary matching markets. IEEE Transactions on Information Theory, 70(4):2831–2850, 2024.

[GZL+ 26]

Mengtong Gao, Zhenhe Zhang, Jichen Li, Wentao Zhou, Xuanzhi Xia, and Jing Chen. Decentralized bandits without global clock for dynamic matching market. In Proceedings of the 43rd International Conference on Machine Learning, volume 306 of Proceedings of Machine Learning Research, pages 33879–33924. PMLR, 2026.

[HRMS20]

Steven R. Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform Chernoff bounds via nonnegative supermartingales. Probability Surveys, 17:257–317, 2020. doi:10.1214/18-PS321.

[KCG16]

Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best-arm identification in multi-armed bandit models. Journal of Machine Learning Research, 17(1):1–42, 2016.

[KL23]

Fang Kong and Shuai Li. Player-optimal stable regret for bandit learning in matching markets. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1512–1522. SIAM, 2023.

[KL24]

Dominik Kaaser and Maximilian Lohmann. Dynamic size counting in the population protocol model: Counting (on) agents to drive a phase clock. In Proceedings of the 2024 ACM Symposium on Principles of Distributed Computing, pages 50–60. Association for Computing Machinery, 2024.

[KLM16]

Varun Kanade, Nikos Leonardos, and Frédéric Magniez. Stable matching with evolving preferences. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016), volume 60 of 54

Leibniz International Proceedings in Informatics, pages 36:1–36:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016. [KWL24]

Fang Kong, Zilong Wang, and Shuai Li. Improved analysis for bandit learning in matching markets. In Advances in Neural Information Processing Systems, volume 37, pages 91904–91929, 2024.

[LMB+ 17]

Marie Laveau, George Manoussakis, Joffroy Beauquier, Thibault Bernard, Janna Burman, Johanne Cohen, and Laurence Pilard. Self-stabilizing distributed stable marriage. In Stabilization, Safety, and Security of Distributed Systems, volume 10616 of Lecture Notes in Computer Science, pages 46–61. Springer, 2017.

[LMJ20]

Lydia T. Liu, Horia Mania, and Michael Jordan. Competing bandits in matching markets. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 1618–1628. PMLR, 2020.

[LRMJ21]

Lydia T. Liu, Feng Ruan, Horia Mania, and Michael I. Jordan. Bandit learning in decentralized matching markets. Journal of Machine Learning Research, 22(211):1–34, 2021.

[MMKS23] Deepan Muthirayan, Chinmay Maheshwari, Pramod Khargonekar, and Shankar Sastry. Competing bandits in time varying matching markets. In Proceedings of The 5th Annual Learning for Dynamics and Control Conference, volume 211 of Proceedings of Machine Learning Research, pages 1020–1031. PMLR, 2023. [MSM22]

Chinmay Maheshwari, Shankar Sastry, and Eric Mazumdar. Decentralized, communication- and coordination-free learning in structured matching markets. In Advances in Neural Information Processing Systems, volume 35, pages 15081–15092, 2022.

[PG24]

Tejas Pagare and Avishek Ghosh. Explore-then-commit algorithms for decentralized two-sided matching markets. In 2024 IEEE International Symposium on Information Theory (ISIT), pages 2092–2097. IEEE, 2024.

[SEIM21]

Yuichi Sudo, Ryota Eguchi, Taisuke Izumi, and Toshimitsu Masuzawa. Time-optimal loosely-stabilizing leader election in population protocols. In 35th International Symposium on Distributed Computing (DISC 2021), volume 209 of Leibniz International Proceedings in Informatics (LIPIcs), pages 40:1–40:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021.

[SFM25]

Vade Shah, Bryce L. Ferguson, and Jason R. Marden. Trial-and-error learning in decentralized matching markets. In 2025 IEEE 64th Conference on Decision and Control (CDC), pages 4936–4941. IEEE, 2025.

[ZF24]

Yirui Zhang and Zhixuan Fang. Decentralized two-sided bandit learning in matching market. In Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, volume 244 of Proceedings of Machine Learning Research, pages 4173–4191. PMLR, 2024.

[ZWF22]

Yirui Zhang, Siwei Wang, and Zhixuan Fang. Matching in multi-arm bandit with collision. In Advances in Neural Information Processing Systems, volume 35, pages 9552–9563, 2022. 55

Related documents

• A Matroid Generalization of Weighted Popular Matching: Characterization and Algorithm#1342953
• Reserve Systems with Match-Specific Beneficiaries#1069696
• Stable matching under regulation#1457566
• A minority-proof cheap-talk protocol#1277630
• The Power of Simple Mechanisms: A Tight $e$-Approximation for Gains from Trade in Matching Markets#1142298