2023/10/18 by Csáji, Gergely
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2310.12269
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'≠ 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 (3)/(4) the size of the maximum weakly popular matching. We also show that this matching is at least (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) (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 (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 γ-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.