论文标题
在稳定婚姻的多层直径上
On the diameter of the polytope of the stable marriage with ties
论文作者
论文摘要
与领带的稳定婚姻问题是游戏理论中一个充分且有趣的问题。我们有一组男人和一组女人。每个人都在相对组上有一个偏好顺序，可能包含纽带。男人和女人之间的匹配是没有阻塞对的，即，在匹配中严格彼此偏爱彼此的男人和女人。 在本文中，我们研究了稳定婚姻的特征向量凸面给出的多元体的直径。我们证明了$ \ lfloor \ frac {n} {3} \ rfloor $在直径上的上限，其中$ n $是男人和女人的总数，并给出了一个实例，并给予了一个界限紧密的实例。我们的结果概括了标准稳定婚姻多层的直径（即描述无领带的众所周知的多层），这是文献中先前在文献中开发的。
The stable marriage problem with ties is a well-studied and interesting problem in game theory. We are given a set of men and a set of women. Each individual has a preference ordering on the opposite group, which can possibly contain ties. A stable marriage is given by a matching between men and women for which there is no blocking pair, i.e., a men and a women who strictly prefer each other to their current partner in the matching. In this paper, we study the diameter of the polytope given by the convex hull of characteristic vectors of stable marriages, in the setting with ties. We prove an upper bound of $\lfloor \frac{n}{3}\rfloor$ on the diameter, where $n$ is the total number of men and women, and give a family of instances for which the bound holds tight. Our result generalizes the bound on the diameter of the standard stable marriage polytope (i.e., the well-known polytope that describes the setting without ties), developed previously in the literature.
