A popular matching is a matching that loses no pairwise majority vote against another matching under prescribed
vertex preferences. Each graph vertex strictly orders
its neighbors and prefers any neighbor to being unmatched. A graph
vertex votes for 
over 
when it prefers its partner in 
to its partner in 
; it abstains if its partner is unchanged. Popularity means
that, for every competing matching 
, at least as many vertices
prefer 
to 
as prefer 
to 
(Bérczi-Kovács and Szabó 2026).
Every stable matching is popular under strict preferences, but a popular matching need not be stable. Stability requires the absence of a blocking pair of adjacent vertices that each prefer the other to their assigned partner, as in the stable marriage problem. A blocking pair does not by itself guarantee a competing matching that wins the majority comparison. The inverse popular matching problem minimizes the cost of changing preferences to make a prescribed matching popular.
