Popular Solutions for Optimal Matchings
摘要
Let G be a bipartite graph where every vertex has a strict preference order over its neighbors. The preferences of a vertex over its neighbors extend naturally to preferences over matchings. A matching M is popular in G if there is no matching N such that vertices that prefer N outnumber those that prefer M. Every stable matching is popular. We consider the following variant: edges in G have utilities and it is only max-utility matchings that are relevant for us. We show there always exists a max-utility matching that is popular within the set of all max-utility matchings; moreover, such a matching can be efficiently computed. We focus on largest max-utility matchings and show a compact extended formulation for the polytope of largest max-utility matchings that are popular within the set of all largest max-utility matchings.