Non-uniformly Stable Matchings
<|reference_start|>Non-uniformly Stable Matchings: Super-stability and strong stability are properties of a matching in the stable matching problem with ties. In this paper, we introduce a common generalization of super-stability and strong stability, which we call non-uniform stability. First, we prove that we can determine the existence of a non-uniformly stable matching in polynomial time. Next, we give a polyhedral characterization of the set of non-uniformly stable matchings. Finally, we prove that the set of non-uniformly stable matchings forms a distributive lattice.<|reference_end|>
@article{kamiyama2024non-uniformly,
    title={Non-uniformly Stable Matchings},
    author={Naoyuki Kamiyama},
    journal={arXiv preprint arXiv:2408.16271},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.16271},
    primaryClass={cs.GT}
}