Non-uniformly Stable Common Independent Sets
Abstract
In this paper, we consider a matroid generalization of the stable matching problem. In particular, we consider the setting where preferences may contain ties. For this generalization, we propose a polynomial-time algorithm for the problem of checking the existence of a common independent set satisfying non-uniform stability, which is a common generalization of super-stability and strong stability.
Fields of Study & Subjects
Game Theory and Voting Systems
Complexity and Algorithms in Graphs
Constraint Satisfaction and Optimization
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 16 January 2026
- Document type
- Preprint