标题： 关于图结构和基于优化的流行匹配表征的等价性 显示英文标题

标题： On the Equivalence of the Graph-Structural and Optimization-Based Characterizations of Popular Matchings

摘要： 流行匹配提供了一个在偏好下的匹配模型，其中解对应于投票系统中的孔多塞赢家。 在一个顶点对其邻居有偏好的二分图中，如果一个匹配在多数投票中不输给任何其他匹配，则定义该匹配为流行的。 在本文中，我们研究以下三个主要问题：仅有一侧的顶点有偏好；允许偏好中存在并列的该问题的推广；两侧的顶点都有偏好。 在流行匹配的算法方面的一个主要问题是如何确定匹配的流行性，因为如果直接应用定义，则需要指数时间。 在文献中，我们有两种类型的表征：图结构表征；以及通过最大权匹配描述的基于优化的表征。 图结构表征是专门为每个问题设计的，并提供了流行匹配的组合结构。 基于优化的表征在所有问题中以相同的方式工作，但它们不揭示流行匹配的结构。 本文的主要贡献是为这三个问题提供上述两种类型表征之间的直接联系。 具体来说，我们证明了每种表征都可以从另一种推导出来，而无需依赖于它们表征流行匹配的事实。 我们的证明提供了对两种类型表征等价性的全面理解，并提出了基于最大权匹配问题的对偶最优解对图结构表征的新解释。 显示英文摘要

摘要： Popular matchings provide a model of matching under preferences in which a solution corresponds to a Condorcet winner in voting systems. In a bipartite graph in which the vertices have preferences over their neighbours, a matching is defined to be popular if it does not lose in a majority vote against any matching. In this paper, we study the following three primary problems: only the vertices on one side have preferences; a generalization of this problem allowing ties in the preferences; and the vertices on both sides have preferences. A principal issue in the algorithmic aspects of popular matchings is how to determine the popularity of a matching, because it requires exponential time if the definition is simply applied. In the literature, we have the following two types of characterizations: a graph-structural characterization; and an optimization-based characterization described by maximum-weight matchings. The graph-structural characterizations are specifically designed for each problem and provide a combinatorial structure of the popular matchings. The optimization-based characterizations work in the same manner for all problems, while they do not reveal the structure of the popular matchings. A main contribution of this paper is to provide a direct connection of the above two types of characterizations for all of the three problems. Specifically, we prove that each characterization can be derived from the other, without relying on the fact that they characterize popular matchings. Our proofs offer a comprehensive understanding of the equivalence of the two types of characterizations, and suggest a new interpretation of the graph-structural characterization in terms of the dual optimal solution for the maximum-weight matching problem.