1 Introduction↩︎

Two-sided matching markets model situations in which two distinct sets of agents aim to match with each other based on their preferences [1]. Classic examples include students applying to universities, workers matching with firms, and organ donors paired with patients [2]. A fundamental solution concept in this setting is stable matching [3], a notion of equilibrium in the market, where no pair of agents has an incentive to deviate from the proposed assignment.

Classical models typically assume that preferences are known in advance. In contrast, modern applications such as ride-sharing systems and online labor markets motivate sequential learning formulations, where agents’ preferences are initially unknown and must be learned over time through repeated interactions.

A growing body of literature casts this learning scenario within the Multi-Armed Bandit (MAB) framework, a direction initiated by [4]. In the centralized version of the problem, a platform matches the agents and receives noisy feedback reflecting their underlying preferences. This setting creates an inherent tension between exploration and exploitation: the platform must decide whether to exploit current estimates of a stable matching or continue exploring to learn the agents’ preferences.

The problem is typically studied within a regret-minimization framework. In this work, we instead adopt a pure exploration perspective, aiming to efficiently identify an optimal stable matching with high probability.

1.1 Related work↩︎

In their foundational work, [4] introduce this learning problem and empirically evaluate the performance of MAB algorithms across several preference structures. A follow-up by [5] introduced the notions of Player-Optimal and Player-Pessimal stable regret. Focusing on a setting where only one side of the market has unknown preferences, they analyzed an Explore-Then-Commit algorithm, proving sublinear bounds for both regret notions. They also examined an Upper Confidence Bound approach, establishing sublinear bounds for Player-Pessimal stable regret; however, they proved an impossibility result for bounding Player-Optimal regret.

Later studies closed this gap by achieving sublinear player-optimal stable regret [6]–[8], though they primarily focused on one-sided uncertainty and specific market structures. More recent studies have begun to consider settings where both sides of the market have uncertain preferences [9], [10]. However, these works employ Explore-Then-Commit type algorithms. In contrast, this work adopts a pure exploration framework that is more naturally suited to the analysis of such algorithms and enables refined results on regret with respect to the optimal stable matching.

The pure exploration objective of identifying an optimal stable matching with high probability was introduced by [11], while the work of [12] focuses on identifying any stable matching. Both of these studies propose elimination-based algorithms restricted to one-sided uncertainty. We extend this literature by tackling a two-sided learning environment, providing refined arguments for the analysis of elimination algorithms.

A core component of our approach is utilizing the agents’ partial preference rankings to identify an optimal stable matching, thereby circumventing the need to learn their full preference orderings. This approach is motivated by the concept of pervasive stable matching, introduced by [13] to reason about optimal stable matchings under partial information in non-learning scenarios. Specifically, a partial preference profile of the agents admits a pervasive stable matching if that matching remains optimally stable under every possible full refinement of the given preferences. A closely related notion is that of a super stable matching, initially introduced to address stability in instances with indifferent preferences [14]. While super stability was recently leveraged by [15] to bound regret in sequential learning scenarios, our work specifically relies on pervasive stable matchings. This distinction is crucial, as our objective is to identify the optimal stable matching, rather than any stable matching.

Appendix 9 contains an extended review of related literature, along with a comprehensive discussion on metrics.

1.2 Contributions↩︎

In this work, we demonstrate how partial preferences and the concepts of pervasive stable matching can be applied in a learning scenario to identify the optimal stable matching with high probability under two-sided market uncertainty.

Our specific contributions are structured as follows:

• Uniform Strategies: We present two variants of uniform exploration strategies that assume additional information about the reward structure. We show that reasoning about partial preferences significantly reduces the overall sample complexity compared to approaches that learn the full rankings, thereby avoiding the traditional dependence on the minimum reward gap.

• Elimination Algorithm & Technical Contribution: We propose an adaptive elimination algorithm that requires no prior knowledge of reward gaps, utilizing a stopping rule based on partial preferences. Furthermore, we provide a refined complexity bound based on edge-coloring arguments on bipartite graphs.

• Extended Elimination Rule: We also present an extension of the elimination algorithm that further eliminates pairs upon identifying a super stable matching.

• Regret Minimization: Beyond our primary objective of pure exploration, we propose a meta-algorithm for the regret minimization setting. To the best of our knowledge, this provides the first regret bound with respect to the optimal stable matching under two-sided uncertainty that avoids a dependence on the minimum reward gap \(\Delta_{min}\).

• Theoretical Lower Bounds: Finally, we conclude our analysis by establishing a lower bound on the sample complexity, utilizing known results from the combinatorial MAB literature [16].

The remainder of the paper is organized as follows. Section 2 introduces the necessary notation and background regarding the stable matching problem and partial preferences. Section 3 then formally defines our learning problem and explains how we utilize the concept of pervasive stable matching. In Section 4, we analyze uniform sampling strategies, discussing the impact of utilizing partial preferences. Section 5 presents our elimination-based algorithm, followed by an extension of the elimination procedure and a discussion on a meta-algorithm for the regret minimization setting. Next, Section 6 establishes a lower bound on the sample complexity. In Section 7, we evaluate our algorithms through simulation on random instances. Further discussion and omitted proofs are provided in the Appendix.

2 Background↩︎

We consider a learning problem in a two-sided matching market, consisting of two distinct, non-empty sets of agents, \(\mathcal{P}\) and \(\mathcal{A}\), with \(K = |\mathcal{P}|\) and \(N = |\mathcal{A}|\) denoting the number of agents on each side, with arbitrary \(K, N\)¹.

The agents \(\mathfrak{A}= \mathcal{P}\cup \mathcal{A}\) are matched one-to-one according to a matching \(\mathbb{M}\subseteq \mathcal{P}\times \mathcal{A}\), i.e., pairs in \(\mathbb{M}\) are pairwise disjoint. For convenience, we use the functional representation of a matching, where \(\mathfrak{m}(p) = a\) and \(\mathfrak{m}(a) = p\) for every \((p, a) \in \mathbb{M}\), and \(\mathfrak{m}(\mathrm{a}) = \bot\) for any unmatched agent \(\mathrm{a}\in \mathfrak{A}\). We define \(OS(\mathrm{a})\) as the opposite side of agent \(\mathrm{a}\), i.e., \(OS(\mathrm{a}) = \mathcal{A}\) if \(\mathrm{a}\in \mathcal{P}\), and \(OS(\mathrm{a}) = \mathcal{P}\) if \(\mathrm{a}\in \mathcal{A}\).

Each agent \(\mathrm{a}\in \mathfrak{A}\) has an underlying true preference over the agents on the opposite side, represented by a strict preference ranking \(F_{\mathrm{a}}\). These preferences are derived from utility functions \(\mu_{\mathrm{a}} : OS(\mathrm{a}) \cup \{\bot\} \rightarrow \mathbb{R}\), where \(\mu_{\mathrm{a}, \mathfrak{m}(\mathrm{a})}\) denotes the utility that agent \(\mathrm{a}\) obtains when matched with \(\mathfrak{m}(\mathrm{a}) \in OS(\mathrm{a})\), and \(\mu_{\mathrm{a}, \bot}\) is the utility of being unmatched. We assume that for every agent \(\mathrm{a}\in \mathfrak{A}\), the utility values \(\{\mu_{\mathrm{a}, i}\}_{i \in OS(\mathrm{a}) \cup \{\bot\}}\) are distinct, thereby ensuring no ties in preferences. The preference ranking is then uniquely constructed by sorting these utilities: \(F_{\mathrm{a}} = \mathop{\mathrm{arg\,sort}}_{i \in OS(\mathrm{a}) \cup \{\bot\}} \mu_{\mathrm{a}, i}\). We denote by \(\succ_{F_{\mathrm{a}}}\) the corresponding strict order relation over \(OS(\mathrm{a}) \cup \{\bot\}\), where \(i \succ_{F_{\mathrm{a}}} j\) if and only if \(\mu_{\mathrm{a}, i} > \mu_{\mathrm{a}, j}\) for \(i, j \in OS(\mathrm{a}) \cup \{\bot\}\)

In order for a matching \(\mathfrak{m}\) to align with the agents’ preferences, [3] introduced the concept of stable matching, a notion of equilibrium in which no two agents have an incentive to deviate. Formally:

[3] proved that the set of stable matchings \(\mathcal{S}\) is always non-empty by introducing the Gale–Shapley (GS) algorithm, which is based on sequential proposals from one side of the market to the other. The algorithm returns the (unique) optimal stable matching \(m^\star\) for the proposing side, in the sense that every proposer receives the best partner they can obtain in any stable matching. Conversely, the resulting matching is pessimal for the side receiving the proposals, providing each agent on that side with their least-preferred partner among all stable matchings. In the remainder of the paper we concentrate on \(\mathcal{P}\)-optimal stable matchings \(m^\star\), simply referred to as optimal.

2.1 Stable Matching from Partial Preferences↩︎

If we correctly estimate the full preference rankings of the agents, we can identify the optimal stable matching using the GS algorithm. However, learning the complete preference orders is not necessary: the optimal stable matching can be identified using only a correct partial preference order, as described by [13]. Stable matchings under certain types of partial preferences form the basis of our proposed algorithms. We begin with the definition of a partial ranking.

Note that all partial rankings are asymmetric and transitive, and that a full ranking is a special case of a partial ranking.

We now define when a partial ranking \(P_a\) is compatible with \(P'_a\), in the sense that \(P'_a\) is a refinement of \(P_a\).

Given a partial preference profile \(P_{A}\), we can describe the set of full ranking profiles \(F_{A} = \{F_a\}_{a \in \mathfrak{A}}\) that refine \(P_{A}\) as \(\mathcal{F}(P_{A}) = \{F_{A} \mid P_{A} \mapsto F_{A}\}\). This motivates the following definition of a super stable matching [14], a concept originally proposed for preferences with indifferences: we say that a matching \(\mathfrak{m}\) is super stable w.r.t. the preference profile \(P_A\) if it is stable w.r.t. every full ranking profile \(F_A \in \mathcal{F}(P_A)\).

The work of [13] introduce a similar definition of pervasive stable matching (PSM), for a matching that is stable and optimal with respect to every full refinement of the partial preferences \(F_A \in \mathcal{F}(P_A)\).

Previous work shows that the set of super stable matchings may be empty, and whenever it is non-empty, it forms a distributive lattice [18]. In this case, there exists a unique optimal super stable matching for each side. In the following example we highlight that an optimal super stable matching is not necessarily the same as the pervasive stable matching [13].

3 Learning Problem↩︎

We consider a learning problem where agents are initially unaware of their preferences and must learn them through repeated interactions. We focus on the centralized setting, where an algorithm selects a matching at each time step and observes stochastic rewards for the matched pairs ².

More formally, the algorithm interacts with an instance \(\nu = \{ \nu_{a,i} \}_{(a, i) \in \mathcal{P}\times\mathcal{A}} \in \mathcal{I}\), where each \(\nu_{a,i}\) corresponds to the reward distribution of agent \(a \in \mathfrak{A}\) when matched with agent \(i \in OS(a)\), and has mean \(\mu_{a,i} = \mathbb{E}_{X \sim \nu_{a,i}}[X].\)

At each time step \(t \ge 1\), the algorithm selects a matching \(m_t \in \mathcal{M}\) out of the set of all matchings \(\mathcal{M}\), and observes stochastic rewards \(X_{a,m_t(a)} \sim \nu_{a,m_t(a)}\) for each matched pair \((a, m_t(a))\) for all \(a \in \mathfrak{A}\). Specifically, the feedback at time \(t\) is represented by the vector \(X_t = (X_{a,m_t(a)} \mathbb{I}\{a \in m_t(a)\})_{a \in \mathfrak{A}} \in \mathbb{R}^{K \times N}\). The filtration \(\mathcal{F}_t := \sigma(m_1, X_1, \dots, m_t, X_t)\) contains all the information available at step \(t+1\), where \(\sigma(\cdot)\) denotes the \(\sigma\)-algebra generated by its arguments.

The algorithm is defined by:

1. A Sampling Rule: A rule determining which matching to sample at each step \(t\), formally a sequence \((m_t)_{t \in \mathbb{N}}\) where each \(m_t\) is \(\mathcal{F}_{t-1}\)-measurable.

2. A Stopping Rule: A stopping time \(\tau\) with respect to the filtration \((\mathcal{F}_t)_{t \in \mathbb{N}}\), which determines when the exploration phase ends.

3. A Recommendation Rule: An \(\mathcal{F}_{\tau}\)-measurable rule that selects a final matching \(m_\tau\) to be returned upon termination.

We consider the fixed-confidence setting, where the objective is to design an algorithm that terminates and outputs the correct optimal stable matching with high probability.

3.0.0.1 Learning with Partial Preferences.

Our previous discussion in Section 2.1 indicates that an algorithm only needs to learn a valid partial preference profile \(P_A\) that admits a pervasive stable matching. This insight motivates the design of our algorithms in the subsequent sections.

We denote the set of valid preference profiles by \(\mathcal{P}_{\text{valid}}(F_{A}^{\nu})\), which is never empty as it always contains the true profile \(F_{A}\). While the work of [19] proves that identifying the set of valid preference profiles is NP-hard, their follow-up research provides a polynomial-time algorithm to return the pervasive stable matching whenever it exists, given a partial ranking [13].

To analyze the sample complexity of our algorithms, we introduce an admissible gap \(\Delta_{F}\) associated with an instance and the set of valid partial preference profiles \(\mathcal{P}_{\mathrm{valid}}(F_A^{\nu})\).

We define the minimum gap induced by a partial ranking \(P_a\) as \(\Delta_{\min}(P_a) = \min_{(i,j) \in P_a} \lvert \mu_{a,i} - \mu_{a,j} \rvert .\) Thus \(\Delta_{\min}(P_a)\) indicates how hard it is for agent \(a\) to learn their preference between pair \((i,j)\in P_a\) in the worst case. For a preference profile \(P_A = \{P_a\}_{a \in \mathfrak{A}}\), we extend this to \(\Delta_{\min}(P_A) = \min_{a \in \mathfrak{A}} \Delta_{\min}(P_a)\). Finally, the admissible gap of an instance is defined as the maximum such minimum gaps over all valid profiles, i.e., \[\Delta_{F} = \max_{P_A \in \mathcal{P}_{\mathrm{valid}}(F_A^{\nu})} \Delta_{\min}(P_A).\]

Relation to the minimum gap: Previous work typically characterizes the performance of an algorithm in terms of the minimum reward gap \(\Delta_{\min} = \min_{\mathrm{a}\in \mathfrak{A}} \Delta_{\min}(F_a)\) [5]. In contrast, our admissible gap \(\Delta_F\), defined with respect to the minimum valid partial profile, satisfies \(\Delta_F \geq \Delta_{\min}\) by definition.

4 Uniform strategies↩︎

Our first contribution using partial preferences is the analysis of a uniform strategy that samples matchings covering all possible pairs \(\mathcal{P} \times \mathcal{A}\) uniformly for a fixed number of \(h\) exploration rounds. We analyze this algorithm for two cases, where the number of exploration rounds \(h\) uses \(\Delta_{min}\) or \(\Delta_F\), to ensure the identification of the correct optimal stable matching with high probability.

After uniformly sampling pairs in \(\mathcal{P} \times \mathcal{A}\) for \(h\) rounds, Algorithm 1 commits to a matching by executing GS on the estimated preferences, \(m_{\tau} = \text{GS}(\{\hat{F}_\mathrm{a}\}_{\mathrm{a}\in \mathfrak{A}})\). Here the preference ranking for an agent \(\mathrm{a}\in \mathfrak{A}\) is determined by sorting the empirical mean rewards, i.e., \(\hat{F}_{\mathrm{a}} = \mathop{\mathrm{arg\,sort}}_{i \in OS(\mathrm{a})} \hat{\mu}_{\mathrm{a},i}(t)\), where \(\hat{\mu}_{\mathrm{a},i}(t) = \frac{1}{N_{\mathrm{a},i}(t)} \sum_{s=1}^{t} \mathbb{I}(m_s(\mathrm{a}) = i ) X_{\mathrm{a},i}(s)\) and \(N_{\mathrm{a},i}(t)\) denotes the number of times the pair \((\mathrm{a},i)\) has been sampled up to time \(t\).

4.0.0.1 Sampling from Minimal Matching Covers:

To sample all pairs in a set \(X \subseteq \mathcal{P} \times \mathcal{A}\), we sample matchings from a minimal matching cover \(\mathfrak{M}(X)\) — the smallest set of matchings such that \(X \subseteq \bigcup_{m \in \mathfrak{M}(X)} m\). For a bipartite graph, finding this cover is equivalent to a minimum edge coloring problem, where the edges of each color correspond to a matching in the cover [20]. According to Kőnig’s Theorem, the minimal number of matchings in a cover is equal to the maximum degree \(deg(G(X))\) of the bipartite graph \(G(X)\) with edges \(X\). Thus, in our setting, a full exploration of all pairs \(\mathcal{P} \times \mathcal{A}\) requires \(\max\{K, N\}\) matchings in each exploration round \(h\). Sampling from a matching cover is essential for our later elimination algorithms, where only a specific subset of pairs needs to be sampled in each step. It relaxes the requirement for round-robin strategies and extends the analysis beyond the usual assumption of \(N < K\).

We can now bound the sample complexity of the uniform strategy where the number of exploration rounds is defined as a function of \(\Delta_{\min}\). This algorithm samples pairs until all agents complete preference rankings can be determined.

Next, we introduce a variant where \(h\) depends on \(\Delta_F\). In this version, the algorithm samples each pair often enough to correctly identify a valid preference profile \(P_A \in \mathcal{P}_{\text{valid}}(F_{A}^{\nu})\), with \(\Delta_F= \max_{P_A \in \mathcal{P}_{\mathrm{valid}}(F_A^{\nu})} \Delta_{\min}(P_A)\).

Example 2. Consider an instance with two agents on each side, with the following true preference rankings:

\(p_1\)	\(p_2\)	\(a_1\)	\(a_2\)
\(a_1 \succ a_2\)	\(a_1 \succ a_2\)	\(p_1 \succ p_2\)	\(p_1 \succ p_2\)

For this instance, the partial preference profile \(P_A=\{P_{p_1}=\{a_1 \succ a_2\},P_{p_2}=\emptyset,P_{a_1}=\{p_1 \succ p_2\}, P_{a_2}=\emptyset\}\) is valid, i.e., the algorithm does not need to estimate the preferences of \(p_2\) and \(a_2\). So the difficulty of the learning task does not depend on the gaps associated with these agents.

To illustrate, consider the following mean rewards:

Agent	Mean rewards \(\mu\)
\(p_1\)	\(\mu_{p_1,a_1} = 1\)	\(\mu_{p_1,a_2} = 1-\Delta_F\)
\(a_1\)	\(\mu_{a_1,p_1} = 1\)	\(\mu_{a_1,p_2} = 1-\Delta_F\)
\(p_2\)	\(\mu_{p_2,a_1} = 1\)	\(\mu_{p_2,a_2} = 1-\Delta_{\min}\)
\(a_2\)	\(\mu_{a_2,p_1} = 1\)	\(\mu_{a_2,p_2} = 1-\Delta_{\min}\)

Figure 2 fixes \(\Delta_F = 0.5\) and varies \(\Delta_{\min}\), comparing the sample complexity of the algorithms with exploration time \(h\) defined in Theorem 1 and Theorem 2, and shows that the resulting differences in the sample complexities can become arbitrarily large as \(\Delta_{\min}\) goes to zero.

5 Elimination Algorithm↩︎

We now turn our attention to elimination algorithms: these have improved sample complexity and do not require prior knowledge of gaps \(\Delta\).

5.1 Simple Elimination Algorithm↩︎

The key idea of Algorithm 3 is to (i) update partial preferences once pairwise orderings are inferred with high probability, (ii) eliminate pairs from sampling, and (iii) stop when a PSM is found. High-probability correctness of the partial preferences implies identification of the optimal matching \(m^{\star}\) with high probability.

5.1.0.1 Sampling:

The elimination algorithm operates in rounds \(t\) and keeps track of active (non-eliminated) agents \(\mathcal{S}_a(t) \subseteq OS(a)\) – those for which the relative ordering in \(a\)’s preferences is not determined with high probability yet. We initialise \(\mathcal{S}_a(0) = OS(a)\) for all agents \(a\in \mathfrak{A}\). Then in each round \(t\), we sample the matchings from a minimal matching cover \(\mathfrak{M}(S_t)\), where \(S_t\) is the set of all non-eliminated pairs: \[S_t = \left\{ (p, a) \in \mathcal{P}\times \mathcal{A}\mid a \in S_p(t) \lor p \in S_a(t) \right\}\] So at each round \(t\), we sample \(n_t\) matchings, with \(n_t\) defined as the maximum degree of the underling graph of the non-eliminated pairs \(G(S_t)\), i.e., \(n_t = \text{deg}(G(S_t))\).

5.1.0.2 Partial Preferences:

To eliminate pairs and form the partial preferences of the agents, we employ confidence intervals. Specifically, at each round \(t\), every agent \(a \in \mathfrak{A}\) maintains a confidence interval for the mean reward associated with each agent \(i \in OS(a)\). The corresponding confidence radius is defined as: \[\label{eq:ci} c_{a,i}(t) = \sqrt{\frac{2\ln{(8KNt^2/\delta)}}{t}}.\tag{1}\] Using this radius, we define the Upper Confidence Bound (UCB) and Lower Confidence Bound (LCB) as: \[\begin{align} \mathrm{UCB}_{a,i}(t) &= \hat{\mu}_{a,i}(t) + c_{a,i}(t), \\ \mathrm{LCB}_{a,i}(t) &= \hat{\mu}_{a,i}(t) - c_{a,i}(t). \end{align}\]

We construct the partial ranking \(P_a\) by adding a directed edge from \(i\) to \(j\) for any distinct pair \(i, j \in OS(a)\) whenever the confidence intervals are disjoint. Formally, at round \(t\), we update the edge set of \(P_a\) according to: \[\label{eq:update95pref} P_a \leftarrow P_a \cup \{(i, j)\} \quad \text{if} \quad \mathrm{LCB}_{a,i}(t) > \mathrm{UCB}_{a,j}(t).\tag{2}\]

5.1.0.3 Elimination Rule:

We remove an agent \(i\) from a set of active agents \(S_a\) if \(i\)’s confidence interval is strictly disjoint from that of every other active agent \(j \in S_a \setminus \{i\}\). Formally, we update \(S_a \leftarrow S_a \setminus \{i\}\) if \(\forall j \in S_a \setminus \{i\}\): \[\label{eq:elim} \mathrm{LCB}_{a,i}(t) > \mathrm{UCB}_{a,j}(t) \; \lor \; \mathrm{UCB}_{a,i}(t) < \mathrm{LCB}_{a,j}(t).\tag{3}\] This implies that the relative order between \(i\) and every other active agent \(j\) has been established with high probability, rendering further sampling of \(i\) unnecessary for agent \(a\).

5.1.0.4 Stopping Condition:

We stop sampling either when all available pairs have been eliminated or when the agents’ partial preference profile admits a PSM. By construction, the partial preferences are consistent with the true underlying preferences with high probability; thus, the matching is the optimal stable matching with high probability. To compute a PSM, we use the POSM algorithm [13] (line 3 of Algorithm 3) , which returns a PSM for the given partial preference profile if one exists, and None otherwise, in polynomial time.

To analyse the sample complexity of Algorithm 3, we define the following reward gaps: For an agent \(a \in \mathfrak{A}\) and \(i \in OS(a)\). Let \(\Delta_{a,i} = \min_{j \in OS(a) \setminus \{i\}} |\mu_{a,i} - \mu_{a,j}|\) denote the minimum reward gap separating \(i\) from all other candidates, and define \(\Delta_{a,i}^{\min} = \min\{\Delta_{a,i}, \Delta_{i,a}\}\) and \(\Delta_{a,i}^{F} = \max(\Delta_{F}, \Delta_{a,i}^{\min})\).

5.2 Regret Analysis↩︎

As previously discussed, almost all results bounding regret w.r.t. the optimal stable matching are based on the ETC framework. More specifically, in our setting we can employ an meta-algorithm that runs the E-PSM algorithm (Algorithm 3) during the exploration phase, and subsequently commits to the identified matching for all remaining rounds. We provide a bound for the following notion of regret: \[\label{eq:regret} R(T) = \sum_{t=1}^T \mathbb{I}\{m_t \neq m^*\} \text{.}\tag{4}\] [15] uses a similar binary regret for a matching to be stable. In addition, our metric upper-bounds the player-optimal stable regret defined by [5], a metric that reflects market stability only when it is sublinear for every agent in the market.

Note that this minimum over the horizon cannot be avoided by any algorithm employing the Explore-Then-Commit framework. To our knowledge, this is the first regret bound with respect to the optimal stable matching under two-sided uncertainty that avoids a dependence on \(\Delta_{min}\).

5.3 Extended Elimination Rule↩︎

We now present an extended version of our previous algorithm, which further eliminates pairs upon the identification of a super stable matching (see Algorithm 7 in the Appendix). Specifically, if at some time step the partial preference profile \(\{P_a\}_{a \in \mathfrak{A}}\) admits a super stable matching \(m_{\mathrm{ss}}\), we use the following elimination rule: \[\begin{align} \label{eq:ext95elim95rule} S_p \leftarrow S_p \setminus \{a\} \quad \text{if} \quad m_{ss}(p) \succ_{P_p} a \quad \forall \; p \in \mathcal{P}. \\ S_a \leftarrow S_a \setminus \{p\} \quad \text{if} \quad p \succ_{P_a} m_{ss}(a) \quad \forall \; a \in \mathcal{A}. \end{align}\tag{5}\] To show that this elimination still allows the identification of a valid profile, and thus a pervasive stable matching, we first show that one specific profile dependant on the optimal stable matching is always valid.

Now any partial profile compatible with profile \(P\) as specified in Proposition 7 is again a valid profile. In particular, for a partial profile \(P' = \{P'_a\}_{a \in \mathfrak{A}}\) that is compatible with full ranking profile \(F\), \(P^* = P \cup P' = \{P_a \cup P'_a\}_{a \in \mathfrak{A}}\) is a valid profile. Assume that \(P'\) admits a super stable matching \(\mathfrak{m}\) that is not the PSM. Then \(P^*\) does not contain:

• \(a \succ_{P^*_p} a'\) for \(a, a' \in \mathcal{A}\) and \(p \in \mathcal{P}\) with \(\mathfrak{m}(p) \succ_{F_p} a,a'\), unless \(a \succ_{P'_p} a'\):
  For optimal stable matching \(\mathfrak{m}^*\) in \(F\), we have \(\mathfrak{m}^*(p) \succ_{F_p} \mathfrak{m}(p) \succ_{F_p} a,a'\). Thus \((a,a') \notin P_p\).

• \(p \prec_{P^*_a} p'\) for \(p, p' \in \mathcal{P}\) and \(a \in \mathcal{A}\) with \(\mathfrak{m}(a) \prec_{F_a} p,p'\), unless \(p \prec_{P'_a} p'\):
  We have \(\mathfrak{m}^*(a) \prec_{F_a} \mathfrak{m}(a) \prec_{F_a} p,p'\) and thus \((p,p') \notin P_a\).

As these relations are not known in \(P^*\), and \(P^*\) is valid, we can eliminate agents as described above.

Note that just because Proposition 7 guarantees that a valid profile (specifically \(P^*\)) can still be identified after eliminating agents form active pairs, this does not mean that the valid profiles that are still learnable attain the best-case gap \(\Delta_{a,i}^{F}= \max(\Delta^{F},\Delta_{a,i}^{\min})\). We can therefore not transfer the sample complexity bound from Theorem 5. However, a super stable matching might be identifiable very fast, leading to early elimination of pairs and hence decreased sample complexity. We explore the sample complexity in our experiments to identify whether this trade-off between early elimination and restriction to valid profiles is beneficial.

6 Lower bound↩︎

We now establish a non-explicit lower bound on sample complexity by adapting the analysis of [16].

For an instance \(\nu \in \mathcal{I}\), we denote with \(\mathfrak{m}^{\star}_{\nu}\) the optimal stable matching. To provide a lower bounds on the sample complexity, we define the set of alternative environments \(\mathcal{I}_{\text{alt}}(\nu)\) as the collection of all environments in \(\mathcal{I}\) where the optimal stable matching is different from that in \(\nu\): \[\mathcal{I}_{\text{alt}}(\nu) = \{ \nu' \in \mathcal{I} : \mathfrak{m}^{\star}_{\nu'} \neq \mathfrak{m}^{\star}_{\nu} \}\] Now we can define the transformed simplex \(\mathcal{S}_{\mid \mathcal{M}\mid} = \{ \sum_{m \in \mathcal{M}} I_{m} w_m : w_m \in \Delta_\mathcal{M} \} \subset \mathbb{R}^{\mathcal{P}\times \mathcal{A}}\), where \(I_{m} \subset \{0,1\}^{\mathcal{P}\times \mathcal{A}}\) represents the binary indicator vector of active pairs in matching \(m\), and \(w_m \in \Delta_\mathcal{M}\) denotes the proportion of rounds in which that specific matching is sampled.

Although the bound is not explicit, it characterizes the intrinsic difficulty of the problem. In the MAB literature, this type of lower bound typically guides the design of optimal algorithms [22]. However, because solving the associated optimization problem is computationally hard, standard Track-and-Stop methods [23] cannot be directly adapted. Developing efficient approximations, such as adapting the methods of [16], is an interesting direction that remains open.

To provide a more concrete analysis, we establish an explicit lower bound for instances with global preferences in Appendix 15, similar to the approach of [24], using arguments based on minimum valid preference profile.

7 Simulations↩︎

In this section, we present simulations to empirically evaluate the proposed algorithms on random instances for varying market sizes \(n\), fixing \(n=N=K\) agents on each side. The code to reproduce the presented results is provided online³.

Settings: We perform two sets of experiments, covering both pure exploration and regret minimization, which we present in the following subsections.

Instances: To generate instances, we first construct the agents’ preferences using random perturbations. We then assign the rewards for each agent \(a \in \mathfrak{A}\) by sampling the reward gaps \(\Delta_{a, i, i+1}\) between consecutive agents from a uniform distribution over \([\Delta_{min}, 1]\), where we set \(\Delta_{min}= 0.2\).

Algorithms: To isolate the individual effects of the elimination strategy and the PSM-based stopping rule, we compare:

1. U-\(\Delta\): The uniform sampling strategy of Section 4 with known \(\Delta_{\min}\).

2. U: Uniform sampling of all pairs, stopping only when all confidence intervals separate (without \(\Delta_{\min}\) knowledge).

3. U-PSM: Uniform sampling of all pairs, terminating when a pervasive stable matching is identified.

4. E-NS: The elimination algorithm without stopping rule, terminating only once all pairs are eliminated.

5. E-PSM: The elimination algorithm of Section 5, terminating when a pervasive stable matching is identified.

6. EE-PSM (Extended PSM): The extended elimination algorithm that further eliminates pairs after identifying a super stable matching as discussed in Section 5.3.

7.1 Pure Exploration↩︎

In Figure 4, we illustrate the sample complexity of the different approaches, averaged over 100 random instances, along with their standard deviations. For these experiments, we set the confidence parameter to \(\delta=0.1\). Notably, all algorithms successfully identified the optimal stable matching in every run; this empirical correctness aligns with standard observations in the MAB literature [25].

Regarding sample complexity, we observe that the proposed algorithms, E-PSM and EE-PSM, significantly outperform all other baselines. Interestingly, we observe only a slight performance difference between these two specific algorithms on random instances. More specifically, upon further examining their behavior, we found that although the extended algorithm eliminated a large number of pairs, the size of the minimum matching cover did not decrease significantly, leading to near-identical sample complexities.

Finally, the results demonstrate clear, independent benefits from both the elimination strategy and the early stopping rule. For example, comparing U-PSM to E-PSM isolates the positive effect of pair elimination, while comparing E-NS to E-PSM highlights the drastic impact of the stopping rule. Furthermore, E-NS outperforms U-PSM in \(n=20\), demonstrating that the effect of the elimination rule is relatively larger on average as the market grows. To conclude, the results show that U-PSM exhibits larger variability across the random instances, suggesting a high sensitivity to specific reward structures. In contrast, the effect of the elimination rule in E-NS is much more stable.

Appendix 16 presents a similar experiment with different numbers of agents on each side, further demonstrating the effectiveness of our approach.

7.2 Regret Minimization↩︎

We further provide an ablation study for regret minimization. We measure regret using the cumulative market instability defined in Section 5.2, Eq. 4 , which counts the number of rounds in which the selected matching differs from the optimal stable matching [4], [15].

To clearly demonstrate the performance of our method against existing benchmarks, we focus on the more extensively studied one-sided uncertainty setting. This allows us to compare with prior regret-minimization algorithms, while our method naturally applies to the two-sided uncertainty setting considered in this paper.

Additional benchmark: We specifically compare our approach with AETGSE, the algorithm of [26], which combines adaptive elimination with the logic of GS algorithm. In the centralized setting, agents explore their currently valid partners in a coordinated round-robin manner, eliminating partners that are certified to be suboptimal. Once an agent identifies its most preferred valid partner, it stop exploring and temporarily commits to it. If this partner becomes unavailable (due to a higher-priority agent), the agent restarts the exploration process.

Figure 5 presents the results over \(50\) independent experiments for each algorithm, using random market instances with the number of agents on each side fixed to \(K=N=20\). The results show that our elimination-based approach with a stopping rule based on pervasive stable matching (E-PSM) achieves lower regret in this one-sided uncertainty setting. Moreover, the uniform-sampling approach (U-PSM) interpolates between AETGS-E and E-PSM, suggesting that both the elimination procedure and our stopping rule contribute to improved learning performance.

Beyond the experimental comparison, our theoretical result yields a tighter upper bound than the analysis of AETGS-E, since the relevant gap depends on the minimum valid partial profile (see Section 3). Nevertheless, we highlight that AETGS-E may perform better on specific instances where agents do not need to restart exploration, due to its adaptive sampling approach. However, in more general instances, where exploration restarts, our algorithm achieves better performance, as demonstrated by our simulations.

8 Conclusion↩︎

In this work, we investigated a sequential learning problem in matching markets where both sides are initially unaware of their true preferences. Focusing on the pure exploration setting, our objective was to identify the optimal stable matching with high probability. Our primary contribution lies in leveraging partial knowledge of agents’ preferences to stop exploration once a pervasive stable matching is found. We first demonstrated the performance gains of this approach on uniform exploration strategies, and subsequently introduced practical elimination algorithms along with a refined sample complexity analysis. Further, we extended our insights to the regret minimization setting and established theoretical lower bounds on the sample complexity.

For future work, it is worth proving theoretical sample-complexity guarantees for the extended algorithm from Section 5.3, and investigating whether we can further eliminate pairs after identifying a super stable matching, specifically by removing pairs that are not part of an exposed rotation [1]. In addition, adaptive algorithms, as in [11], [26], that do not uniformly sample active pairs are also a promising approach. Finally, designing optimal algorithms that match the lower bound established in our analysis remains an open problem.

Appendix Outline↩︎

In this appendix, we provide the detailed proofs and discussion omitted from the main text.

• Appendix 9: Provides an extended related work section along with a discussion on different learning objectives.

• Appendix 10: Contains the analysis of Theorems 2 and 3 from Section 4.

• Appendix 11: Contains the proof of Theorem 5 from Section 5.1.

• Appendix 12: Contains the proof of Theorem 6 from Section 5.2.

• Appendix 13: Contains the proof of Proposition 7 from Section 5.3.

• Appendix 14: Contains the proof of Theorem 8 from Section 6.

• Appendix 15: Contains the analysis of the lower bound for specific instance and the proof of Lemma 4.

9 Extended Related Work↩︎

This section provides additional discussion on related work, expanding upon the overview presented in the main text.

9.0.0.1 MAB and pure exploration:

The stochastic MAB problem, introduced by [27], has been extensively studied in the past few decades, becoming a fundamental tool for analyzing online decision-making problems under uncertainty. A learner selects one action (or arm) in each round and receives a numeric reward drawn from an unknown distribution that reflects the utility of the action. In the classic version of regret minimization, the learner aims to maximize cumulative rewards by balancing exploration and exploitation: searching for optimal actions versus pulling known high-reward arms. Another popular setting is the pure exploration problem, where the learner’s objective is to identify a good action regardless of the cost incurred in the learning process. This problem is usually studied in the fixed-confidence setting, where the learner aims to identify an optimal action with high probability using as few samples as possible [28]. Initial research in the field explored uniform exploration and elimination-based strategies [29], [30], focusing on their correctness and sample complexity. More recent studies [23], [24] establish a lower bound on sample complexity, motivating the Track-and-Stop algorithm which achieves asymptotic optimality. In this paper, we study identifying the optimal stable matching in the fixed-confidence setting. For a comprehensive overview of MAB, we refer to the book by [31].

9.0.0.2 Stable matching problem:

Two-sided matching markets model situations in which two distinct sets of agents aim to match with each other based on individual preferences [1], [32], [33]. Classic examples include students applying to universities, workers matching with firms, and organ donors paired with patients [2].

In their fundamental work, [3] introduced the concept of stable matching, a notion of equilibrium in which no two agents have an incentive to deviate. [3] proved that the set of stable matchings \(\mathcal{S}\) is always non-empty by introducing the Gale–Shapley (GS) algorithm, which is based on sequential proposals from one side of the market to the other. The algorithm returns the (unique) optimal stable matching \(m^\star\) for the proposing side, in the sense that every proposer receives the best partner they can obtain in any stable matching. Conversely, the resulting matching is pessimal for the side receiving the proposals, providing each agent on that side with their least-preferred partner among all stable matchings.

A core component of our approach is utilizing the agents’ partial preference rankings to identify an optimal stable matching, thereby circumventing the need to learn their full preference orderings. This approach is motivated by the concept of pervasive stable matching, introduced by [13] to reason about optimal stable matchings under partial information in non-learning scenarios. Specifically, a partial preference profile of the agents admits a pervasive stable matching if that matching remains optimally stable under every possible full refinement of the given preferences. A closely related notion is that of a super stable matching, initially introduced to address stability in instances with indifferent preferences [14].

9.0.0.3 Leaning in matching markets:

The problem of two-sided markets with unknown preferences has recently attracted considerable attention in various settings. [4] were the first to introduce the marriage problem with unknown preferences on both sides of the market, framing it as a MAB problem. In their work [4], they empirically studied several algorithms in specific preference settings. A follow-up by [5] introduced the notions of Player-Optimal and Player-Pessimal stable regret. Focusing on a setting where only one side of the market has unknown preferences, they analyzed an Explore-Then-Commit algorithm, proving sublinear bounds for both regret notions. They also examined an Upper Confidence Bound approach, establishing sublinear bounds for Player-Pessimal stable regret; however, they proved an impossibility result for bounding Player-Optimal regret.

Later studies closed this gap by achieving sublinear player-optimal stable regret [6]–[8], though they primarily focused on one-sided uncertainty and specific market structures. More recent studies have begun to consider settings where both sides of the market have uncertain preferences [9], [10]. However, these works employ Explore-Then-Commit type algorithms. In contrast, this work adopts a pure exploration framework that is more naturally suited to the analysis of such algorithms and enables refined results on regret with respect to the optimal stable matching.

The pure exploration objective of identifying an optimal stable matching with high probability was introduced by [11], while the work of [12] focuses on identifying any stable matching. Both of these studies propose elimination-based algorithms restricted to one-sided uncertainty. We extend this literature by tackling a two-sided learning environment, providing refined arguments for the analysis of elimination algorithms.

Conceptually, the closest work to ours is [15], where the authors leverage partial preferences and the concept of super stability to bound regret in sequential learning scenarios. In contrast, our approach specifically relies on pervasive stable matchings, instead of the super stable matching. This distinction is crucial, as our objective is to identify the optimal stable matching, rather than any stable matching.

Prior work also considers decentralized settings [6], [7], [9], [10], [17], [34], models with transferable-utilities [15], [35], [36], and the setting with many-to-one matchings [26], [37], [38].

9.0.0.4 Discussion on alternative objectives:

Related work typically characterizes algorithmic performance based on the cumulative rewards collected by individual agents. In particular, most existing approaches follow the notion of agent-optimal (or pessimal) stable regret, which compares accumulated rewards against a baseline that always selects the optimal stable matching, following the definitions in the seminal work of [5]. This cumulative metric reflects stability only if the regret is sublinear for every agent in the market. Furthermore, this objective can be satisfied by a composition of unstable matchings over the time horizon—similar to the concept of fractional stability over probabilistic matchings that may individually be unstable [39]. Another notion of regret, more compatible with our objective, is binary stable regret, which evaluates the stability of the matching at each discrete time step [4], [15]. Current studies in this area typically consider a matching to be stable without specifically requiring the identification of the optimal stable matching. Additionally, algorithms addressing these different objectives often rely on the Explore-then-Commit (ETC) framework, bounding the probability of error through sufficient exploration [5], [8], [9], [15]. Notable exceptions to these ETC-based approaches include analyses of UCB-style algorithms [5], [40] and Thompson sampling [34], which do not guarantee sublinear regret with respect to the optimal stable matching. Ultimately, different objectives prioritize different criteria; we emphasize that our framework is specifically designed for applications where the primary goal is to learn the optimal stable matching itself, rather than merely achieving stability in a cumulative or general sense.

10 Analysis of Section 4↩︎

In this section, we provide the proofs for the sample complexity of our uniform exploration strategies.

10.1 Proof of Theorem 2↩︎

10.2 Proof of Theorem 3↩︎

11 Analysis of Section 5↩︎

11.1 Proof of Theorem 5↩︎

Proof.
Correctness argument
We first present a formal argument that the elimination algorithm identifies the optimal stable matching with probability at least \(1-\delta\).

To begin, the algorithm is guaranteed to terminate because the confidence radius \(c_{a,i}(t)\) shrinks toward zero as the number of samples \(t\) increases. Since the algorithm continues to sample every non-eliminated pair in each round, the confidence intervals will eventually shrink enough to resolve the relative ordering of every pair. Consequently, the algorithm will eventually eliminate all pairs satisfying the stopping condition.

Now, let \(\mathcal{E}\) be the event that the true means \(\mu_{a,i}\) lie within the confidence intervals for all estimates \(\hat{\mu}_{a,i}(t)\) at all times \(t\). Formally, \(\mathcal{E}\) is the intersection of all individual events \(\mathcal{E}_{t,a,i}\): \[\mathcal{E} = \bigcap_{t=1}^{\infty} \bigcap_{a\in \mathfrak{A}} \bigcap_{i \in OS(a)} \mathcal{E}_{t,a,i},\] where \(\mathcal{E}_{t,a,i}\) denotes the event that the true mean \(\mu_{a,i}\) lies within the confidence interval at time \(t\): \[\mathcal{E}_{t,a,i} = \left\{ \left| \hat{\mu}_{a,i}(t) - \mu_{a,i} \right| \leq c_{a,i}(t) \right\}.\]

In Lemma 1 we prove that the event \(\mathcal{E}\) holds with probability at least \(1-\delta\), i.e. \(\Pr(\mathcal{E}) \geq 1- \delta\).

Under event \(\mathcal{E}\), the algorithm only adds correct preference relations to \(P_a\) because \(LCB_{a,i}(t) > UCB_{a,j}(t)\) implies \(\mu_{a,i} > \mu_{a,j}\). Since the algorithm terminates with a valid preference profile \(\hat{P}_A \in \mathcal{P}_{\mathrm{valid}}(F_A)\), it returns the correct optimal stable matching \(m^\star\)

To conclude, under the good event \(\mathcal{E}\), which holds with probability at least \(1-\delta\), the algorithm returns the optimal stable matching.

11.2 Sample complexity↩︎

We now continue the analysis on sample complexity in terms of matching samples. Recall that in each round \(t\), we sample every non-eliminated pair \(S_t\) by sampling \(n_t\) matchings from a minimum matching cover \(\mathfrak{M}(S_t)\).

Let \(\tau_{a,i}\) denote the number of rounds required to eliminate agent \(i \in OS(a)\) from the active set \(S_{a}\) of agent \(a\in \mathfrak{A}\). To eliminate agent \(i\), we must successfully distinguish it from every other agent \(j \in OS(a)\setminus \{i\}\). Therefore, the elimination time is dominated by the time required to separate \(i\) from its closest competitor, which corresponds to the minimum reward gap \(\Delta_{a,i} = \min_{j \in OS(a) \setminus \{i\}} |\mu_{a,i} - \mu_{a,j}|\). By applying Lemma 2 we have that: \[\label{eq:tai} \tau_{a,i} \leq \frac{32 \log(8KN/(\delta\Delta_{a,i}))}{\Delta_{a,i}^2} \text{.}\tag{6}\]

Since eliminating a pair \((p,a)\in \mathcal{P}\times\mathcal{A}\) requires removing \(p\) from \(S_a\) and \(a\) from \(S_p\), the maximal number of rounds is \(t_{p,a} = \max\{\tau_{p,a}, \tau_{a,p}\} \leq \frac{32 \log(8KN/(\delta\Delta_{p,a}^{\min}))}{(\Delta_{p,a}^{\min})^2}\), where \(\Delta_{p,a}^{\min} = \min\{\Delta_{p,a}, \Delta_{a,p}\}\).

11.2.0.1 A. Sample complexity Without Stopping Rule

Next, we give the sample complexity ignoring the stopping rule where the algorithm terminates if the partial preferences admit a pervasive stable matching.

Given the sampling requirements \(t_{p,a}\) for each pair of agents \((p,a) \in \mathcal{P}\times \mathcal{A}\) (where \(t_{p,a} = t_{a,p}\)) , we construct a bipartite multigraph \(G_M = (V = \mathcal{P}\cup \mathcal{A}, E = \mathcal{P}\times \mathcal{A})\) illustrated in Figure 6, where \(t_{p,a}\) denotes the edge multiplicity for the pair \((p,a)\). By Kőnig’s Theorem, there exists a decomposition of these edges into \(deg(G_M)\) matchings, where \(deg(G_M)\) is the maximum degree of the multigraph. Consequently, the number of matchings is at most: \[O(\max_{a \in \mathfrak{A}} \sum_{i \in OS(a)} t_{a,i})\] since \(\sum_{i \in OS(a)} t_{a,i}\) denotes the degree of agent \(a\) in the multigraph.

As a note, we use this variant of the algorithm to demonstrate the isolated effect of the elimination rule in the experiments section.

11.2.0.2 B. Sample complexity With Stopping Rule

We now perform the analysis considering the stopping rule. The algorithm terminates once it correctly estimates a partial preference profile \(\hat{P}_A\) that admits a pervasive stable matching, i.e., \(\hat{P}_A \in \mathcal{P}_{\mathrm{valid}}(F_A)\). By definition, there exists at least one valid preference profile \(P_A^F \in \mathcal{P}_{\mathrm{valid}}(F_A)\) that admits the maximum possible minimum gap \(\Delta_{F}\)

Since the algorithm uniformly samples every non-eliminated pair in each round, it is guaranteed to correctly estimate all preference relations in this optimal target profile \(P_A^F\) once all reward gaps of size at least \(\Delta_F\) are resolved. By applying Lemma 2, this requires at most \(\tau^F\) rounds, where \[\tau^{F} \leq \frac{32 \log(8KN/(\delta\Delta_{F}))}{\Delta_{F}^2} \text{.}\]

Consequently, any pair \((a,i)\) is sampled only until it is individually eliminated from the active sets, or until the algorithm successfully identifies \(P_A^F\) and terminates globally. Thus, the number of times pair \((a,i)\) is sampled is strictly bounded by \(t^{F}_{a,i} = \min(t_{a,i}, \tau^{F})\). Using the individual elimination bound for \(t_{a,i}\) (Eq. 6 ) and the global termination bound \(\tau^F\), we have: \[t^{F}_{a,i} \leq \frac{32 \log(8KN/(\delta\Delta_{a,i}^{F}))}{(\Delta_{a,i}^{F})^2},\] where \(\Delta_{a,i}^{F} = \max(\Delta_{F}, \Delta_{a,i}^{\min})\).

Following the logic of the previous analysis, we consider the bipartite multigraph \(G_M\) with edge multiplicities \(t^{F}_{a,i}\). By Kőnig’s Theorem, there exists a decomposition of these edges into \(deg(G_M)\) matchings, where \(deg(G_M)\) is the maximum degree. Therefore, the total number of matching samples is at most: \[O\left(\max_{a \in \mathfrak{A}} \sum_{i \in OS(a)} t^{F}_{a,i}\right)\]

To conclude, we prove that with probability at least \(1-\delta\), the algorithm terminates with the correct optimal stable matching, and that with probability at least \(1-\delta\), the sample complexity is at most: \[O\left(\max_{a \in \mathfrak{A}} \sum_{i \in OS(a)} \frac{32 \log(8KN/(\delta\Delta_{a,i}^{F}))}{(\Delta_{a,i}^{F})^2},\right)\] where \(\Delta_{a,i}^{F} = \max(\Delta_{F}, \Delta_{a,i}^{\min})\). ◻

11.3 useful lemmas↩︎

12 Proof of Theorem 6↩︎

13 Extended Elimination Algorithm↩︎

Now we provide a proof of our Proposition 7 that we restate bellow:

14 Lower bound↩︎

We consider a matching problem consisting of two disjoint sets of agents, \(\mathcal{P}\) and \(\mathcal{A}\), with \(K=|\mathcal{P}|\) and \(N=|\mathcal{A}|\) number of agents in each set. Let \(\mathfrak{A}= \mathcal{P}\cup \mathcal{A}\) denote the set of all agents. For any agent \(a \in \mathfrak{A}\), we define \(OS(a)\) as the set of agents on the opposite side of the market i.e., \(OS(\mathrm{a}) = \mathcal{A}\) if \(\mathrm{a}\in \mathcal{P}\), and \(OS(\mathrm{a}) = \mathcal{P}\) if \(\mathrm{a}\in \mathcal{A}\).

Let \(\mathcal{I}\) be a class of matching environments, where we define a matching instance \(\nu = \{ \nu_{a,i} \}_{a \in \mathfrak{A}, i \in OS(a)} \in \mathcal{I}\) as a collection of probability distributions, where each \(\nu_{a,i}\) is associated with the agent-partner pair \((a, i)\). For every pair, the observed reward \(X_{a,i}\) is a random variable drawn from \(\nu_{a,i}\) with a true underlying mean reward \(\mu_{a,i} = \mathbb{E}_{X \sim \nu_{a,i}}[X]\), representing the utility agent \(a\) derives from being matched with \(i\).

For an instance \(\nu \in \mathcal{I}\), we denote with \(\mathfrak{m}^{\star}_{\nu}\) the optimal stable matching. To provide a lower bounds on the sample complexity, we define the set of alternative environments \(\mathcal{I}_{\text{alt}}(\nu)\) as the collection of all environments in \(\mathcal{I}\) where the optimal stable matching is different from that in \(\nu\): \[\mathcal{I}_{\text{alt}}(\nu) = \{ \nu' \in \mathcal{I} : \mathfrak{m}^{\star}_{\nu'} \neq \mathfrak{m}^{\star}_{\nu} \}\] We denote with \(P_\nu(\mathcal{E})\) the probability of an event \(\mathcal{E} \in \mathcal{F}_t\) under the environment \(\nu\).

14.1 Proof of Lower bound↩︎

14.2 Change of Distribution Lemma↩︎

At each time step \(t \geq 1\) we sample a matching \(m_t \in \mathcal{M}\), and the platform observers the rewards of each agent that is matched \(X_t = (X_{a,m_t(a)} I\{a \in m_t(a)\})_{\forall a \in \mathfrak{A}} \subset \mathbb{R}^{K \times N}\) similar to the semi-bandit feedback, where \(X_{a,m_t(a)}\) is distributed according to \(\nu_{a,m_t(a)}\).

Given a history \(\mathcal{F}_{t} = \sigma(m_1, X_{1,m_1}, \cdots, m_t, X_{t,m_t} )\) up to time \(t\), we can define the log-likelihood of the observation for the two different matching instances \(\nu\) and \(\nu'\): \[\mathcal{L}_t(m_1, X_{1,m_1}, \cdots, m_t, X_{t,m_t} ) = \sum_{a\in \mathfrak{A}} \sum_{i \in OS(a)} \sum_{s=1}^{t} I\{ (a,i) \in m_t\} \ln \frac{p_{a,i}(X_{s,a,i})}{p'_{a,i}(X_{s,a,i})}\] where \(p_{i,j}\) denotes the density of the distribution \(\nu_{i,j}\).

Now, we present a transportation lemma for two-sided matching problems, adapted from Lemma 1 originally proposed in [24].

15 Lower bounds on specific instances↩︎

We can now continue by providing a lower bound based on specific instances.

Similar to the work of [24] we will perform an analysis changing the distribution of one pair of agents, under the identifiable class of environments: \[\mathcal{I}_{\text{class}} = \{ \nu = (\nu_{p,a})_{\forall (p,a) \in \mathcal{P} \times \mathcal{A}} : \nu_{p,a} \in \mathcal{P}_m \text{ and } m^{\star}(\nu) \ne \emptyset \}\]

such that the probability measure \(\mathcal{P}_m\) satisfies the following continuity assumption:

15.1 Global preferences↩︎

We study instances with global preferences similar to Example 7 in [5].

Proof. We consider an instance \(\nu\) with equal umber of agents on both sides and global preference profile \(F\) where for all \(p_i \in \mathcal{P}\), \(a_1 \succ a_2 \succ \dots \succ a_n\), and for all \(a_i \in \mathcal{A}\), \(p_1 \succ p_2 \succ \dots \succ p_n\), such that the optimal stable matching \(\mathfrak{m}\) is given by \(\mathfrak{m}(p_i)=a_i\) for all \(i\).

Figure 8 illustrates the case of three agents on each side.

We first present a valid preference profile \(P\) for this instance that is minimal, in the sense that \(P\) is a subset of every other valid partial profile \(P'\) for \(F\), i.e., \(\forall P' \in \mathcal{P}_{\mathrm{valid}}(F)\), it holds that \(P_a \subseteq P'_a\) for all \(a \in \mathfrak{A}\). This profile \(P\) is defined as follows: Each agent \(p_i \in \mathcal{P}\) has partial preferences \(P_{p_i}= \{a_i \succ a_j \mid j>i\}\), i.e., \(p_i\) prefers their optimal matching partner \(a_i\) over all higher-indexed agents in \(\mathcal{A}\). Similarly, for each agent \(a_i \in \mathcal{A}\), \(P_{a_i} = \{p_i \succ p_j \mid j>i\}\).

15.1.0.1 Validity of \(P\)

By definition, \(P\) is compliant with \(F\). To prove that \(P \in \mathcal{P}_{\mathrm{valid}}(F)\), we first show that \(\mathfrak{m}\) is a super stable matching in \(P\), and then show that \(\mathfrak{m}\) is optimal in every completion of \(P\), i.e., any full ranking profile compatible with \(P\).

To verify that \(\mathfrak{m}(p_i)=a_i\) is super stable under the partial preference profile \(P\), consider any pair \((p_i,a_j)\) with \(j\neq i\). If \(i>j\), then \(a_j\) prefers their match \(p_j\) to \(p_i\) in \(P\), since \(p_j = \mathfrak{m}(a_j)\succ_{P_{a_j}} p_i\). Thus, \((p_i,a_j)\) is not a blocking pair in any completion of \(P\). If \(j>i\), then \(p_i\) prefers their match \(a_i\) to \(a_j\) in \(P\), since \(a_i = \mathfrak{m}(p_i)\succ_{P_{p_i}} a_j\), and again \((p_i,a_j)\) is not blocking \(\mathfrak{m}\) in any completion of \(P\). Hence, no pair blocks \(\mathfrak{m}\) in any completion of \(P\), and \(\mathfrak{m}\) is super stable.

We now show that \(\mathfrak{m}\) is also the optimal stable matching in any completion of \(P\), i.e., a pervasive stable matching. For contradiction, assume that this is not the case, and that there exists a full ranking profile \(F'\) compatible with \(P\) that admits an optimal stable matching \(\mathfrak{m}' \neq \mathfrak{m}\). Because \(\mathfrak{m}\) is super stable, it is also a stable matching in \(F'\). Now consider some edge \((p_i,a_j)\) in \(\mathfrak{m}'\setminus\mathfrak{m}\). Because \(\mathfrak{m}'\) is assumed to be optimal in \(F'\), we have that \(p_i\) is better off under \(\mathfrak{m}'\) than \(\mathfrak{m}\) and vice versa for \(a_j\), i.e., \(a_j = \mathfrak{m}'(p_i) \succ_{F'_{p_i}} \mathfrak{m}(p_i) = a_i\) and \(p_j = \mathfrak{m}(a_j) \prec_{F'_{a_j}} \mathfrak{m}'(a_j) = p_i\). If \(i > j\) this is not compliant with preferences \(p_j \succ_{P_{a_j}} p_i\) in \(P\). Similarly, if \(j>i\) this is not compliant with preferences \(a_i \succ_{P_{p_j}} a_j\) in \(P\). Thus, there cannot exist any edge \((p_i,a_j)\) in \(\mathfrak{m}'\setminus\mathfrak{m}\). This is a contradiction to our choice of \(F'\) and \(\mathfrak{m}'\). Hence \(\mathfrak{m}\) is optimal in any full ranking profile compatible with \(P\).

15.1.0.2 Minimality of \(P\)

We now prove that \(P\) is minimal in the sense that it is a subset of every other valid partial profile \(P'\) for \(F\), i.e., \(\forall P' \in \mathcal{P}_{\mathrm{valid}}(F)\), it holds that \(P_a \subseteq P'_a\) for all \(a\in\mathfrak{A}\).

To see this, consider that for any valid profile \(P' \in \mathcal{P}_{\mathrm{valid}}(F)\), in order for an edge \((p_i, a_j)\) not to block the stable matching \(\mathfrak{m}\) in any completion of \(P'\), we require that either \(a_i \succ_{P'_{p_i}} a_j\) or \(p_j \succ_{P'_{a_j}} p_i\) (not necessarily both). According to \(F\), the former holds only when \(i < j\), and the latter holds only when \(j < i\). Thus:

• For all pairs \((p_i, a_j)\) with \(i < j\), a valid profile must specify \(a_i \succ_{p_i} a_j\).

• For all pairs \((p_i, a_j)\) with \(i > j\), a valid profile must specify \(p_j \succ_{a_j} p_i\).

These are exactly the relations specified in \(P\). Therefore, \(P\) is both valid and minimal with respect to ensuring stability and optimality of \(\mathfrak{m}\) across all completions.

15.1.0.3 Lower bound on the expected number of pair samples \(\mathbb{E}_\nu[N_{p_i,a_j}(\tau)]\)

Following [24], we construct alternative environments to provide lower bounds on the sample counts \(N_{p_i,a_i}\) and \(N_{a_i,p_i}\) for any agent pair \((p_i,a_i)\).

We construct our alternative environments based on the preference profile \(P = \{P_a\}_{a \in \mathfrak{A}}\) defined above. Specifically, since we proved that \(P\) is valid and minimal, any completion (or alternative environment) compatible with \(P\) will yield the exact same optimal stable matching. Therefore, to create an alternative environment \(\nu'\) where the optimal stable matching is different, we must construct an environment that is not consistent with \(P\). We achieve this by minimally modifying the reward distribution of only a single pair.

We specifically consider alternative instances \(\nu'\) where the distribution of one agent \(p_i \in \mathcal{P}\) is modified in only one agent \(a_j \in \mathcal{A}\): \[\begin{align} \nu' = (&\nu_{p_1}, \cdots, \nu'_{p_i}, \cdots, \nu_{p_K} \\ &\nu_{a_1}, \cdots, \nu_{a_i}, \cdots, \nu_{a_N} ) \end{align}\] where \[\nu'_{p_i} = (\nu_{{p_{i},a_{1}}}, \cdots, \nu'_{p_{i},a_{j}}, \cdots, \nu_{p_{i},a_{N}} )\] with (using Assumption 2):

• if \(j=i\) then: \(\mu'_{p_{i}, a_{i}} < \mu_{p_{i}, a_{i+1}}\) and \(KL(\nu_{p_{i}, a_{i}},\nu_{p_{i}, a_{i+1}}) < KL(\nu_{p_{i}, a_{i}},\nu'_{p_{i}, a_{i}}) < KL(\nu_{p_{i}, a_{i}},\nu_{p_{i}, a_{i+1}}) +\alpha\)

• if \(j>i\) then: \(\mu'_{p_{i}, a_{j}} > \mu_{p_{i}, a_{i}}\) and \(KL(\nu_{p_{i}, a_{j}}, \nu_{p_{i}, a_{i}}) < KL(\nu_{p_{i}, a_{j}}, \nu'_{p_{i}, a_{j}}) < KL(\nu_{p_{i}, a_{j}}, \nu_{p_{i}, a_{i}}) + \alpha\)

Note that in every of those alternative instances we have a different optimal stable matching, i.e., \(m^{\star}_{\nu} \neq m^{\star}_{\nu'}\). Thus, introducing the event \(\mathcal{E} = \{m_{\tau} = m^{\star}_{\nu}\}\), any \(\delta\)-PAC algorithm stopping at time \(\tau\) with matching \(m_\tau\) satisfies \(\Pr_{\nu}(\mathcal{E})\geq 1 - \delta\) and \(\Pr_{\nu'}(\mathcal{E}) \leq \delta\) .

Applying Lemma 3 on the stopping time \(\tau\) for the two matching instances \(\nu\) and \(\nu'\) we have that: \[\sum_{a \in \mathfrak{A}} \sum_{i \in OS(a)} \mathbb{E}_\nu[N_{a,i}(\tau)] KL(\nu_{a,i}, \nu'_{a,i}) \ge d(P_\nu(\mathcal{E}), P_{\nu'}(\mathcal{E})) \ge d(1-\delta, \delta)\] where \(N_{a,i}(\tau)\) is the number of samples of pair \((a,i)\in \mathcal{P}\times\mathcal{A}\) until stopping time \(\tau\).

Using the lower bound on the binary relative entropy \(d(1-\delta, \delta) \ge \ln \frac{1}{2.4 \delta}\) for \(\delta \in (0, 1/2)\) [24], and the fact that the two different instances \(\nu\) and \(\nu'\) differ only in the distribution of one pair, we obtain: \[\mathbb{E}_\nu[N_{p_i,a_j}(\tau)] \ge \log(\frac{1}{2.4 \delta}) \frac{1}{KL(\nu_{p_i,a_j}, \nu'_{p_i,a_j})}\] Now from the definition of the alternative instances, for \(i=j\): \[\mathbb{E}_\nu[N_{p_i,a_i}(\tau)] \ge \log(\frac{1}{2.4 \delta}) \frac{1}{KL(\nu_{p_i,a_i}, \nu_{p_i,a_{i+1}}) + \alpha}\] and for \(j>i\) : \[\mathbb{E}_\nu[N_{p_i,a_j}(\tau)] \ge \log(\frac{1}{2.4 \delta}) \frac{1}{KL(\nu_{p_i,a_j}, \nu_{p_i,a_i})+ \alpha}\] Furthermore, for \(j < i\), the definition of \(P\) and the construction of the alternative environments imply that \(p_i\) does not require samples from \(a_j\). Consequently: \[\label{eq:case95395p} \mathbb{E}_\nu[N_{p_i,a_j}(\tau)] = 0\tag{7}\]

Now following the same reasoning for the agents \(a_i \in \mathcal{A}\), by symmetry of the partial preferences \(P\) we have that for \(i=j\): \[\mathbb{E}_\nu[N_{a_i,p_i}(\tau)] \ge \log(\frac{1}{2.4 \delta}) \frac{1}{KL(\nu_{a_i,p_i}, \nu_{a_i,p_{i+1}}) + \alpha}\] and for \(j>i\) : \[\mathbb{E}_\nu[N_{a_i,p_j}(\tau)] \ge \log(\frac{1}{2.4 \delta}) \frac{1}{KL(\nu_{a_i,p_j}, \nu_{a_i,p_i})+ \alpha}\] and for \(j<i\) : \[\label{eq:case95395a} \mathbb{E}_\nu[N_{a_i,p_j}(\tau)] = 0\tag{8}\]

Lower bound on the number of matchings \(\mathbb{E}_{\nu}[\tau]\)
Finally, we lower bound the number of matchings \(\tau\) by analyzing the associated bipartite multigraph \(G\) with edge multiplicities \(t_{i,j}\), as illustrated in Figure 9.

To define the edge multiplicities \(t_{k,l}\), we observe that each pair \((p_k, a_l)\) must be sampled at least \(\max(\mathbb{E}_{\nu}[N_{p_k,a_l}(\tau)], \mathbb{E}_{\nu}[N_{a_k,p_l}(\tau)])\). Letting parameter \(\alpha \to 0\), we have that for \(k=l\): \[t_{k,k} = \max( \mathbb{E}_\nu[N_{p_k,a_k}(\tau)], \mathbb{E}_\nu[N_{a_k,p_k}(\tau)]) \geq \log(\frac{1}{2.4 \delta}) \max\Bigr( \frac{1}{KL(\nu_{p_k,a_k}, \nu_{p_k,a_{k+1}})}, \frac{1}{KL(\nu_{a_k,p_k}, \nu_{a_k,p_{k+1}}) } \Bigl)\] and for \(k<l\), Eq. 8 implies that \(\mathbb{E}_\nu[N_{a_l,p_k}] = 0\) and thus: \[t_{k,l} = \mathbb{E}_\nu[N_{p_k,a_l}(\tau)] \geq \log(\frac{1}{2.4 \delta}) \frac{1}{KL(\nu_{p_k,a_l}, \nu_{p_k,a_k})}\] and for \(l<k\), Eq. 7 implies that \(\mathbb{E}_\nu[N_{p_k,a_l}] = 0\) and thus: \[t_{k,l} = \mathbb{E}_\nu[N_{a_l,p_k}(\tau)] \geq \frac{1}{KL(\nu_{a_l,p_k}, \nu_{a_l,p_l})}\]

Now according to Kőnig’s Theorem, the number of matchings required to cover the edges of the bipartite multigraph \(G\), is equal to the maximum degree: \[\mathbb{E}_{\nu}[\tau] = def(G) = \max(\max_{p_i \in \mathcal{P}} deg(p_i),\max_{a_i \in \mathcal{A}} deg(a_i))\] where the degree for agents \(p_i \in \mathcal{P}\) is: \[\begin{align} &deg(p_i) = \sum^{n}_{j=1} t_{i,j} = t_{i,i} + \sum_{j<i} t_{i,j} + \sum_{j>i} t_{i,j} \\ &\geq \log\left(\frac{1}{2.4 \delta}\right) \left[ \max\left( \frac{1}{KL(\nu_{p_i,a_i}, \nu_{p_i,a_{i+1}})}, \frac{1}{KL(\nu_{a_i,p_i}, \nu_{a_i,p_{i+1}}) } \right) + \sum_{j<i} \frac{1}{KL(\nu_{a_j,p_i}, \nu_{a_j,p_j})} + \sum_{j>i} \frac{1}{KL(\nu_{p_i,a_j}, \nu_{p_i,a_i})} \right] \end{align}\] and the degree for agents for \(a_i \in \mathcal{A}\): \[\begin{align} &deg(a_i) = \sum^{n}_{j=1} t_{j,i} = t_{i,i} + \sum_{j<i} t_{j,i} + \sum_{j>i} t_{j,i} \\ &\geq \log\left(\frac{1}{2.4 \delta}\right) \left[ \max\Bigr( \frac{1}{KL(\nu_{p_i,a_i}, \nu_{p_i,a_{i+1}})}, \frac{1}{KL(\nu_{a_i,p_i}, \nu_{a_i,p_{i+1}}) } \Bigl) + \sum_{j<i} \frac{1}{KL(\nu_{p_j,a_i}, \nu_{p_j ,a_j}) } + \sum_{j>i} \frac{1}{KL(\nu_{a_i,p_j}, \nu_{a_i,p_i})} \right] \end{align}\]

To conclude we have that: \[\begin{align} \mathbb{E}_{\nu}[\tau] \geq \log\left(\frac{1}{2.4 \delta}\right) \max(\max_{p_i \in \mathcal{P}}A_i, \max_{a_i \in \mathcal{A}}B_i) \end{align}\] where, \[\begin{align} A_i = \max\Bigr( \frac{1}{KL(\nu_{p_i,a_i}, \nu_{p_i,a_{i+1}})}, \frac{1}{KL(\nu_{a_i,p_i}, \nu_{a_i,p_{i+1}}) } \Bigl) + \sum_{j<i} \frac{1}{KL(\nu_{a_j,p_i}, \nu_{a_j,p_j})} + \sum_{j>i} \frac{1}{KL(\nu_{p_i,a_j}, \nu_{p_i,a_i})} \end{align}\] and \[\begin{align} B_i = \max\Bigr( \frac{1}{KL(\nu_{p_i,a_i}, \nu_{p_i,a_{i+1}})}, \frac{1}{KL(\nu_{a_i,p_i}, \nu_{a_i,p_{i+1}}) } \Bigl) + \sum_{j<i} \frac{1}{KL(\nu_{p_j,a_i}, \nu_{p_j ,a_j}) } + \sum_{j>i} \frac{1}{KL(\nu_{a_i,p_j}, \nu_{a_i,p_i})} \end{align}\] ◻

16 Additional Experiments↩︎

We present additional results for the pure exploration setting in markets with different numbers of agents on the two sides. Specifically, we fix the number of arms to \(K=10\) and vary the number of agents \(N\) from \(2\) to \(50\). For each value of \(N\), we run \(20\) independent instances generated as in the main experiment. As shown in Figure 10, the observations from Section 7.1 continue to hold across different market sizes.

References↩︎