Scholarlink

<p>Let <i>G</i> 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 <i>N</i> is more <i>popular</i> than matching <i>M</i> if the vertices that prefer <i>N</i> to <i>M</i> outnumber those that prefer <i>M</i> to <i>N</i>. A matching <i>M</i> is popular if there is no matching more popular than <i>M</i>. Every stable matching is popular, thus popular matchings always exist in <i>G</i> and can be efficiently computed. We consider the following problem: edges in&#xa0;<i>G</i> have utilities and it is only max-utility matchings that are relevant. Our goal is to find a <i>popular max-utility matching</i>, i.e., a max-utility matching <i>M</i> such that there is no max-utility matching more popular than <i>M</i>. We show there always exists a popular max-utility matching; furthermore, such a matching can be efficiently computed. The popular <i>critical</i> matching algorithm is the key subroutine in our algorithm. Given a set of prioritized or critical vertices in <i>G</i>, we are interested in only those matchings that match as many critical vertices as possible. We call such matchings “critical” and seek a <i>popular critical matching</i>, i.e., a critical matching <i>M</i> such that there is no critical matching more popular than <i>M</i>. We show popular critical matchings always exist in <i>G</i> and a min-size/max-size such matching can be efficiently computed. We focus on max-size critical matchings and show a compact extended formulation for the <i>popular max-critical</i> matching polytope, i.e., the polytope of max-size critical matchings that are popular within the set of all max-size critical matchings. Thus we can efficiently solve linear optimization problems over the set of popular max-size critical matchings.</p>

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

Max-Utility Matchings with Popularity via Critical Vertices

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年3月19日

查看全文
  • 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 N is more popular than matching M if the vertices that prefer N to M outnumber those that prefer M to N. A matching M is popular if there is no matching more popular than M. Every stable matching is popular, thus popular matchings always exist in G and can be efficiently computed. We consider the following problem: edges in G have utilities and it is only max-utility matchings that are relevant. Our goal is to find a popular max-utility matching, i.e., a max-utility matching M such that there is no max-utility matching more popular than M. We show there always exists a popular max-utility matching; furthermore, such a matching can be efficiently computed. The popular critical matching algorithm is the key subroutine in our algorithm. Given a set of prioritized or critical vertices in G, we are interested in only those matchings that match as many critical vertices as possible. We call such matchings “critical” and seek a popular critical matching, i.e., a critical matching M such that there is no critical matching more popular than M. We show popular critical matchings always exist in G and a min-size/max-size such matching can be efficiently computed. We focus on max-size critical matchings and show a compact extended formulation for the popular max-critical matching polytope, i.e., the polytope of max-size critical matchings that are popular within the set of all max-size critical matchings. Thus we can efficiently solve linear optimization problems over the set of popular max-size critical matchings.