Probably Correct Optimal Stable Matching under Two-Sided Uncertainty

• URL: http://arxiv.org/abs/2607.04824v1
• Date: Mon, 06 Jul 2026 08:57:30 GMT
• Title: Probably Correct Optimal Stable Matching under Two-Sided Uncertainty
• Abstract summary: We study a sequential learning problem for stable matchings in two-sided markets where preferences on both sides are unknown.<n>We adopt a pure exploration perspective, aiming to efficiently identify the optimal stable matching with high probability.<n>We propose elimination-based algorithms whose stopping criteria exploit the structure of the learned partial preferences.
• Score: 10.205814220900981
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study a sequential learning problem for stable matchings in two-sided markets where preferences on both sides are initially unknown. We focus on a centralized setting where an algorithm matches agents at each time step and receives noisy rewards that reflect the preferences of the matched agents, following a semi-bandit feedback structure. We adopt a pure exploration perspective, aiming to efficiently identify the optimal stable matching with high probability. Our work extends prior results by handling \emph{two-sided uncertainty} and by exploiting \emph{partial preference} information. A central ingredient is the notion of \textbf{pervasive stable matching}, which enables the identification of optimal stable matchings under partial preferences. We propose elimination-based algorithms whose stopping criteria exploit the structure of the learned partial preferences, and provide a refined sample-complexity analysis. Beyond pure exploration, we extend our approach to regret minimization and establish regret bounds with respect to the \emph{optimal} stable matching that avoid dependence on the minimum reward gap $Δ_{\min}$.

Related papers

• Active Bipartite Ranking with Smooth Posterior Distributions [1.9838140219494644]
  Bipartite ranking is a statistical learning problem involved in many applications and widely studied in the passive context.<n>We propose a novel algorithm, referred to as smooth-rank and designed for the continuous setting, which aims to minimise the distance between the ROC curve of the estimated ranking rule and the optimal one w.r.t. the $sup$ norm.<n>We provide a problem dependent upper bound on the expected sampling time of smooth-rank and establish a problem dependent lower bound on the expected sampling time of any PAC$(,)$ algorithm.
  arXiv  Detail & Related papers  (2026-02-27T18:32:08Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  We analyze $f$-divergence-regularized offline policy learning.<n>For reverse Kullback-Leibler (KL) divergence, we give the first $tildeO(epsilon-1)$ sample complexity under single-policy concentrability.<n>We extend our analysis to dueling bandits, and we believe these results take a significant step toward a comprehensive understanding of $f$-divergence-regularized policy learning.
  arXiv  Detail & Related papers  (2025-02-09T22:14:45Z)
• Probably Correct Optimal Stable Matching for Two-Sided Markets Under Uncertainty [5.250288418639076]
  We consider a learning problem for the stable marriage model under unknown preferences for the left side of the market.<n>Our aim is to quickly identify the stable matching that is left-side optimal, rendering this a pure exploration problem with bandit feedback.
  arXiv  Detail & Related papers  (2025-01-06T13:59:57Z)
• Stable Matching with Ties: Approximation Ratios and Learning [34.58046942241621]
  We study matching markets with ties, where workers on one side of the market may have tied preferences over jobs, determined by their matching utilities.<n>Unlike classical two-sided markets with strict preferences, no single stable matching exists that is utility-maximizing for all workers.
  arXiv  Detail & Related papers  (2024-11-05T17:14:46Z)
• Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning [14.448192914855674]
  Two-sided matching markets describe a class of problems wherein participants from one side of the market must be matched to those from the other side according to their preferences. We exploit the structure of stable solutions to devise algorithms that improve the likelihood of finding stable solutions.
  arXiv  Detail & Related papers  (2024-10-06T06:47:53Z)
• Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems [62.83783246648714]
  We propose a sequential quadratic programming algorithm (TR-StoSQP) to solve nonlinear optimization problems with objectives and deterministic equality constraints. The algorithm adaptively selects the trust-region radius and, compared to the existing line-search StoSQP schemes, allows us to utilize indefinite Hessian matrices.
  arXiv  Detail & Related papers  (2022-11-29T05:52:17Z)
• Learning Equilibria in Matching Markets from Bandit Feedback [139.29934476625488]
  We develop a framework and algorithms for learning stable market outcomes under uncertainty. Our work takes a first step toward elucidating when and how stable matchings arise in large, data-driven marketplaces.
  arXiv  Detail & Related papers  (2021-08-19T17:59:28Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  We investigate the active pure exploration problem in Markov Decision Processes. Agent sequentially selects actions and, from the resulting system trajectory, aims at the best as fast as possible.
  arXiv  Detail & Related papers  (2021-06-05T09:16:28Z)
• Consensus-Guided Correspondence Denoising [67.35345850146393]
  We propose to denoise correspondences with a local-to-global consensus learning framework to robustly identify correspondence. A novel "pruning" block is introduced to distill reliable candidates from initial matches according to their consensus scores estimated by dynamic graphs from local to global regions. Our method outperforms state-of-the-arts on robust line fitting, wide-baseline image matching and image localization benchmarks by noticeable margins.
  arXiv  Detail & Related papers  (2021-01-03T09:10:00Z)
• SetRank: A Setwise Bayesian Approach for Collaborative Ranking from Implicit Feedback [50.13745601531148]
  We propose a novel setwise Bayesian approach for collaborative ranking, namely SetRank, to accommodate the characteristics of implicit feedback in recommender system. Specifically, SetRank aims at maximizing the posterior probability of novel setwise preference comparisons. We also present the theoretical analysis of SetRank to show that the bound of excess risk can be proportional to $sqrtM/N$.
  arXiv  Detail & Related papers  (2020-02-23T06:40:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.