Weakly-Popular and Super-Popular Matchings with Ties and Their Connection to Stable Matchings

• Published in: arXiv.org 2024-06
• Main Author: Csáji, Gergely
• Format: Article
• Language: English
• Subjects: Approximation; Matching; Mathematical analysis; Polynomials; Popularity
• ISSN: 2331-8422

In this paper, we study a slightly different definition of popularity in bipartite graphs \(G=(U,W,E)\) with two-sided preferences, when ties are present in the preference lists. This is motivated by the observation that if an agent \(u\) is indifferent between his original partner \(w\) in matching \(M\) and his new partner \(w'\ne w\) in matching \(N\), then he may probably still prefer to stay with his original partner, as change requires effort, so he votes for \(M\) in this case, instead of being indifferent. We show that this alternative definition of popularity, which we call weak-popularity allows us to guarantee the existence of such a matching and also to find a weakly-popular matching in polynomial-time that has size at least \(\frac{3}{4}\) the size of the maximum weakly popular matching. We also show that this matching is at least \(\frac{4}{5}\) times the size of the maximum (weakly) stable matching, so may provide a more desirable solution than the current best (and tight under certain assumptions) \(\frac{2}{3}\)-approximation for such a stable matching. We also show that unfortunately, finding a maximum size weakly popular matching is NP-hard, even with one-sided ties and that assuming some complexity theoretic assumptions, the \(\frac{3}{4}\)-approximation bound is tight. Then, we study a more general model than weak-popularity, where for each edge, we can specify independently for both endpoints the size of improvement the endpoint needs to vote in favor of a new matching \(N\). We show that even in this more general model, a so-called \(\gamma\)-popular matching always exists and that the same positive results still hold. Finally, we define an other, stronger variant of popularity, called super-popularity, where even a weak improvement is enough to vote in favor of a new matching. We show that for this case, even the existence problem is NP-hard.