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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Popular Solutions for Optimal Matchings

  • Telikepalli Kavitha

摘要

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.