Tie-Safe Stable Learning for Two-Sided Unknown Matching Markets

This paper characterizes, up to universal constants, the class-wise asymptotic logarithmic regret of two-sided matching markets with unknown preferences and possible exact ties. Under aggregate regret against the coordinate-wise lowest player payoffs among weakly stable matchings, learning is governed by comparisons that certify stability or rule out unstable outcomes, rather than complete preference recovery. A signed certificate view isolates two complementary structural margins. The certificate margin $\Delta$ measures how strongly some stable matching rejects every deviation, while, when $\Delta =0$, the preservation margin ${\Delta }_{\mathrm{pres}}$ measures the smallest blocking strength of any unstable matching. For $N$ players and $K\ge N$ arms, both regimes obey the same core–tail complexity law $\Psi (h)=\frac{N^2}{h^2}+\frac{N(K-N)}{h}$, where the two terms correspond to resolving core comparisons and screening outside arms. Upper and policy-uniform lower bounds match, establishing the sharp class-wise rate $\Theta (\Psi (h)\log T)$, with $h=\Delta$ when $\Delta >0$ and $h={\Delta }_{\mathrm{pres}}$ at the zero-certificate boundary. Neither the leading logarithmic term nor the horizon-independent remainder depends on the global minimum positive preference gap. Aggregate Core–Tail Learning (ACTL) attains both guarantees without knowing either margin, the tie pattern, or the underlying regime. A communication-aware decentralized variant preserves the same class-wise $O(\Psi (h)\log T)$ order over connected bounded-bandwidth local networks when communication consumes physical time.