Robust Popular Matchings

We study popularity for matchings under preferences. This solution concept captures matchings that do not lose against any other matching in a majority vote by the agents. A popular matching is said to be robust if it is popular among multiple instances. We present a polynomial-time algorithm for deciding whether there exists a robust popular matching if instances only differ with respect to the preferences of a single agent while obtaining NP-completeness if two instances differ only by a downward shift of one alternative by four agents. Moreover, we find a complexity dichotomy based on preference completeness for the case where instances differ by making some options unavailable.

Authors

• Martin Bullinger University of Bristol
• Rohith Reddy Gangam University of California, Irvine
• Parnian Shahkar University of California, Irvine

Keywords

• Matchings under preferences
• popularity
• robustness