Alternating Path's influence on Popularity in Graph Matching Problem

Question

Assume we have a Matching M in a Bipartite Graph and an Alternating Path P with respect to M , that has a (1,1) Edge in it (both the end points of this edge prefer to be matched together other than their partners in M) will M $\oplus$ P = M' always result a More Popular Matching than M ? ( not the most popular , just a little bit more popular than what it was )

ps : We know that if a Matching is Popular then it doesn't have such a path

Answer 1

I'm assuming that you're referring to the same notion of a "popular matching" as in your previous question, the one defined in this paper: the graph is bipartite, all vertices rank their neighbors by preference, and a popular matching $M$ is one such that there is no matching $M'$ such that more vertices prefer $M'$ to $M$ than $M$ to $M'$.

The answer to your question is no: the resulting matching is not "more popular". We are guaranteed that the endpoints of the $(1,1)$ edge are happier in $M \oplus P$ than in $M$. Also, each endpoint of $P$ that is unsaturated in $M$ becomes saturated in $M \oplus P$, so it is better off. (Usually, we consider augmenting paths, such that both endpoints of $P$ are unsaturated in $M$, so this gives us four vertices that are happier with $M \oplus P$ than with $M$.) But if $P$ is long enough, there could be plenty of other vertices in $P$ that were happier in $M$ than in $M \oplus P$.

Two warnings about this:

1. In Theorem 1 of the linked paper, we look for alternating paths in $G_M$: the graph in which all edges that are $(-1,-1)$ with respect to $M$ - that is, all edges that would make both endpoints worse off - are deleted. If $P$ is an alternating path in $G_M$, not just in $G$, and $|M \oplus P| \ge |M|$ (so that at least one endpoint of $P$ becomes happier) then the condition you want does hold, since for every new edge, at least one endpoint is happier with it than in its previous edge.

2. Calling a matching "more popular" than another is slightly misleading because it suggests that you're certain to have a sequence of more popular matchings until you get to a popular one. In fact, it's possible to have a sequence of matchings $M_1, M_2, \dots, M_k$ such that more vertices prefer $M_{i+1}$ to $M_i$ than the reverse ($M_{i+1}$ is more popular than $M_i$) and yet more vertices prefer $M_1$ to $M_k$ than the reverse ($M_1$ is more popular than $M_k$).