Robustness of Stable Matchings When Attributes and Salience Determine Preferences

In many matching markets--such as athlete recruitment or academic admissions--participants on one side are evaluated by attribute vectors known to the other side, which in turn applies individual salience vectors to assign relative importance to these attributes. Since saliences are known to change in practice, a central question arises: how robust is a stable matching to such perturbations? First, we formalize robustness as a radius within which a stable matching remains immune to blocking pairs under any admissible perturbation of salience vectors (which are assumed to be normalized). Given a stable matching and a radius, we present a polynomial-time algorithm to verify whether the matching is stable within the specified radius. We also give a polynomial-time algorithm for computing the maximum robustness radius of a given stable matching. Further, we design an anytime search algorithm that uses certified lower and upper bounds to approximate the most robust stable matching, and we characterize the robustness-cost relationship through efficiently computable bounds that delineate the achievable tradeoff between robustness and cost. Finally, for each stable matching, we show that the salience profiles preserving its stability form a product of low-dimensional polytopes within the simplex. This characterization enables efficient volume computation, with approximations available in higher dimensions, linking robustness analysis in matching markets to convex geometry.