Non-uniformly Stable Common Independent Sets
By: Naoyuki Kamiyama
Potential Business Impact:
Finds fair matches even with tricky choices.
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.
Similar Papers
Robust Stable Matchings: Dealing with Changes in Preferences
CS and Game Theory
Finds stable pairings even when people change their minds.
The Strongly Stable Roommates Problem and Linear Programming
CS and Game Theory
Finds fair room assignments when people have preferences.
Persuading Stable Matching
CS and Game Theory
Helps people find best matches by shaping beliefs.