Your Hiring Algorithm Isn't as Stable as You Think — A New Paper Reveals the Breaking Point

In many real-world matching markets—from athlete recruitment to academic admissions—one side evaluates candidates using attribute vectors (e.g., test scores, skills) while weighting those attributes with personal salience vectors (e.g., valuing test scores over experience). These salience vectors are known to shift over time, raising a critical question: how robust is a stable matching to such changes?

A new paper by Amit Ronen, S.S. Ravi, and Sarit Kraus, accepted to AAMAS 2026, provides the first formal framework for answering that question. The authors define robustness as a radius within which a stable matching remains immune to blocking pairs under any admissible perturbation of normalized salience vectors. They develop a polynomial-time algorithm to check whether a given matching stays stable within a specified radius, and another polynomial-time algorithm to compute the exact maximum robustness radius of any stable matching.

Beyond verification, the team introduces an anytime search algorithm that uses certified lower and upper bounds to approximate the most robust stable matching. They also characterize the tradeoff between robustness and cost (e.g., match quality) through efficiently computable bounds. Finally, they show that for each stable matching, the set of salience profiles preserving its stability forms a product of low-dimensional polytopes within the simplex—a geometric structure whose volume can be computed efficiently or approximated as dimensions grow. This work brings tools from convex geometry into matching market analysis.