论文标题
与单方面偏见的热门比赛
Popular Matchings with One-Sided Bias
论文作者
论文摘要
令$ g =（a \ cup b，e）$是两部分图，其中集合$ a $由代理商或主要玩家组成，集合$ b $由工作或次要玩家组成。每个顶点都有严格的邻居排名。匹配的$ m $如果对于任何匹配的$ n $，那么偏爱$ m $而不是$ n $的顶点的数量至少是偏爱$ n $而不是$ m $的数量。由于每种稳定的匹配都是受欢迎的，因此始终存在流行的匹配。 匹配的$ m $是$ a $ a-popular，如果对于任何匹配的$ n $，则偏爱$ m $而不是$ n $的代理商数（即，$ a $中的顶点）至少是偏爱$ n $而不是$ m $的代理数。与流行的比赛不同，在给定的实例$ g $中不必存在$ a-apopular的匹配，并且有一个简单的线性时间算法来决定$ g $是否允许$ a $ a $ a-apopular匹配并计算一个。 我们考虑确定$ g $是否承认既流行和$ a-poppular并找到一个匹配的问题。我们称这种比赛完全流行。当$ a $是更重要的一面时，完全受欢迎的匹配非常有用 - 因此，随着整体知名度，我们希望保持``在套装$ a $''中的普及。完全受欢迎的匹配不一定是最小/最大尺寸的流行匹配和所有已知的多项式时间算法，用于流行的匹配问题计算最小或最大尺寸的流行匹配。在这里，我们显示了一个完全流行的匹配问题的线性时间算法，因此我们的结果显示了一个新的流行匹配项。
Let $G = (A \cup B,E)$ be a bipartite graph where the set $A$ consists of agents or main players and the set $B$ consists of jobs or secondary players. Every vertex has a strict ranking of its neighbors. A matching $M$ is popular if for any matching $N$, the number of vertices that prefer $M$ to $N$ is at least the number that prefer $N$ to $M$. Popular matchings always exist in $G$ since every stable matching is popular. A matching $M$ is $A$-popular if for any matching $N$, the number of agents (i.e., vertices in $A$) that prefer $M$ to $N$ is at least the number of agents that prefer $N$ to $M$. Unlike popular matchings, $A$-popular matchings need not exist in a given instance $G$ and there is a simple linear time algorithm to decide if $G$ admits an $A$-popular matching and compute one, if so. We consider the problem of deciding if $G$ admits a matching that is both popular and $A$-popular and finding one, if so. We call such matchings fully popular. A fully popular matching is useful when $A$ is the more important side -- so along with overall popularity, we would like to maintain ``popularity within the set $A$''. A fully popular matching is not necessarily a min-size/max-size popular matching and all known polynomial-time algorithms for popular matching problems compute either min-size or max-size popular matchings. Here we show a linear time algorithm for the fully popular matching problem, thus our result shows a new tractable subclass of popular matchings.
