Abstract: We consider a generalization of stability called "popularity" and the problem is to find a min-cost popular matching in a stable marriage instance G, when there is a cost function on the edge set. While a max-size (or min-size) popular matching can be computed in linear time, there is no polynomial time algorithm currently known to find a min-cost popular matching in G.
However a min-cost popular "mixed matching" in G, i.e. a probability distribution over matchings, can be computed in polynomial time. We show that this mixed matching has a simple structure: it is of the form {(M, 0.5), (M',0.5)} where M and M' are matchings in G. This structure is due to the self-duality of the linear program that gives rise to the polytope of popular fractional matchings in G.