70稳定婚姻问题中的成对偏好0ÁGNES CSEH，匈牙利经济与区域研究中心，经济研究所，匈牙利和哈索∙普拉特纳研究所，波茨坦大学，德国ATTILA JUHOS，布达佩斯科技与经济大学计算机科学与信息理论系，匈牙利0我们研究了经典的双边稳定婚姻问题，其中存在成对偏好。在最一般的情况下，允许代理以比较他们的任意两条边的方式表达他们的偏好，并且他们也有权宣布平局甚至退出这样的比较。然后，随着我们在偏好中指定六个有序性阶段，这种自由逐渐受到限制，最终以严格有序列表的经典情况结束。我们研究了在结合了三种已知稳定性概念—弱稳定性、强稳定性和超稳定性—的情况下出现的所有情况，假设双边市场的每一方都获得了六种有序性中的一种。通过设计三种多项式算法和两个NP-完全性证明，我们确定了所有尚未知道的情况的复杂性，从而在偏好结构方面给出了可处理和不可处理情况的确切边界。0CCS概念：• 计算的数学 → 组合算法；0附加关键词和短语：稳定婚姻，不传递性，无环偏好，偏序，弱稳定匹配，强稳定匹配，超稳定匹配0ACM参考格式：Ágnes Cseh和Attila Juhos. 2020. 稳定婚姻问题中的成对偏好. ACM Trans. Econ. Comput. 9,1, Article 7（2020年12月），28页。https://doi.org/10.1145/343442701 引言0在2016年美国总统选举中，民主党总统候选人伯尼∙桑德斯毫无疑问比共和党候选人唐纳德∙特朗普更受欢迎[38,39]。然而，桑德斯在他们自己党的初选周期中被希拉里∙克林顿击败，因此2016年民主党全国代表大会支持克林顿成为民主党的候选人。在总统选举中，特朗普击败了克林顿。这个最近的例子很好地展示了成对偏好是多么不一致。0ÁgnesCseh得到了匈牙利科学院的支持，该支持是在其动量计划（LP2016-3/2020）、OTKA基金K128611和COST行动CA16228欧洲博弈论网络下获得的。作者地址：Á. Cseh，经济与区域研究中心，经济研究所，匈牙利布达佩斯Tóth Kálmán utca4号，以及哈索∙普拉特纳研究所，波茨坦大学，Prof.-Dr.-Helmert-Str.2-3号，波茨坦，14482，德国；电子邮件：cseh.agnes@krtk.mta.hu；A.Juhos，布达佩斯科技与经济大学计算机科学与信息理论系，Magyar tudósok körútja2号，布达佩斯，1117，匈牙利；电子邮件：juhosattila@cs.bme.hu。未经费用许可，允许将本作品的全部或部分以数字或纸质形式用于个人或课堂使用，但不得用于牟利或商业用途，并且复制件上必须标明本通知和第一页的完整引用。必须尊重本作品中作者之外的其他组成部分的版权。允许带有信用的摘要。未经许可，不得复制，或再版，或发布在服务器上，或分发到列表上，需要事先特定的许可和/或费用。请从permissions@acm.org请求权限。©2020版权由所有者/作者所有。出版权利由ACM许可。2167-8375/2020/12-ART7 $15.00 https://doi.org/10.1145/34344270ACM经济与计算交易，第9卷，第1期，第7篇文章。出版日期：2020年12月。07:2 Á. Cseh 和 A. Juhos0偏好在稳定婚姻问题及其扩展中起着至关重要的作用。在经典的0在Gale和Shapley[14]定义的模型中，每个男人和女人都通过提供一个严格排序的列表来表达他们对异性的偏好。如果没有一对代理阻塞了一组婚姻，那么这组婚姻就是稳定的。如果一个男人和一个女人相互更喜欢对方而0在稳定婚姻问题中要求严格的偏好顺序是一个强假设，0很少适用于现实场景[6]。对不太严格的偏好结构的研究已经兴盛了数十年[3，11，19，22，25，31]。一旦允许在偏好列表中存在并列，就需要重新审视阻塞边的定义。在文献中，使用了三种直观的定义，每种定义都定义了弱稳定、强稳定和超稳定匹配。根据弱稳定性，如果代理u和w都严格地更喜欢彼此而不是他们在匹配中的伴侣，那么匹配就被边uw阻塞。强阻塞边被一端顶点严格地更喜欢，而在另一端顶点不严格比匹配边更差。在超稳定情况下，阻塞边对于两个端顶点至少和匹配边一样好。超稳定匹配根据定义是强稳定的，强稳定匹配根据定义是弱稳定的。0弱稳定性是一个直观的概念，它与经典的阻塞边定义最为一致0Gale和Shapley[14]定义的模型中的初始。然而，在许多应用中，达到强稳定性是目标，比如大学入学计划。在大多数国家，学生需要在申请程序中提交严格的排序，但学院无法严格排名所有申请者，因此他们的名单中会出现大量的并列。根据智利和匈牙利使用的平等待遇政策，例如，可能不会发生一个学生被他或她喜欢的学院拒绝，即使其他分数相同的学生被录取[7，34]。其他国家，如爱尔兰[9]，通过抽签来打破并列，这导致了一个弱稳定的解决方案。超稳定匹配在应用中确实不太相关；然而，如果关于代理偏好的信息不确定，它们代表了最坏情况的情形。如果两条边由于来自代理的不完整信息而无法相互比较，那么正是超稳定匹配的概念保证了稳定性，无论代理的真实偏好是什么。0我们目前的工作目标是在0比关系更一般的偏好结构。01.1 相关工作0循环和非传递偏好在广泛的选举和代表主题中经常出现，如果选民的集合在一些成对比较[2]中不同，比如我们之前关于克林顿-桑德斯-特朗普之战的民意调查的例子。偏好聚合是另一个经常产生非传递群体偏好的领域，正如著名的Condorcet悖论[10]所示。0也许不太为人所知的是，在偏好0个体的偏好也是如此。对个人的循环和非传递偏好的研究已经激发了多个领域的科学家数十年。Blavatsky[8]证明了在风险选择情况下，绝大多数个体表达了非传递选择和违反标准一致性要求。Humphrey[17]发现即使在选择三元组重复第二次时，循环偏好仍然存在。神经科学家使用MRI扫描仪确定了编码“局部欲望”的大脑区域，这导致了实验参与者清晰、系统和可预测的非传递选择[24]。循环和非传递偏好在多属性比较中自然发生[12，33]。May[33]研究了对未来伴侣的选择，并发现了一部分参与者表达了相同的循环偏好关系，如果候选人缺少三个中的一个0ACM经济与计算交易，第9卷，第1篇文章7。出版日期：2020年12月。These are denoted by colored cells in Table 1. We fill all gaps, providing two NP-completenessproofs and three polynomial time algorithms. Interestingly, the three tables have the border be-tween polynomial time and NP-complete cases at very different places. As a byproduct of ournew proofs, we are able to answer all analogous complexity questions in the non-bipartite stableroommates problem as well (see Table 2 in Section 6).ACM Transactions on Economics and Computation, Vol. 9, No. 1, Article 7. Publication date: December 2020.0稳定婚姻问题中的成对偏好 7:30特性智力、外貌和财富被提出进行成对比较。在本文中，我们调查了配对偏好的稳定婚姻问题，这些偏好可能是不传递或循环的普遍和深入研究的偏好结构。0关于稳定婚姻问题，所有三种稳定性概念都已经彻底0如果偏好以部分有序集、带有并列关系的列表或严格列表的形式给出，就会进行调查[14，19，22，25，31，32]。弱稳定匹配总是存在的，并且可以在多项式时间内找到[31]，超稳定匹配或其不存在的证明也可以在多项式时间内产生[19，32]。在强稳定性的情况下需要最复杂的想法，如果双方都有并列偏好，则结果是可以在多项式时间内解决的[19]。Irving[19]指出“我们描述的算法可以轻松扩展到更一般的问题，其中每个人的偏好都表示为部分顺序。这仅涉及将每个人（当前）偏序的“头”解释为源节点的集合，将“尾”解释为相应有向无环图中的汇节点的集合。”他和他的合著者一起驳斥了这一说法，表明用偏序代替并列实际上使得强稳定婚姻问题成为 NP-完全[22]。我们在本文中表明了中间情况，即一方有并列，而另一方有偏序，可以在多项式时间内解决。0除了偏序集，对于具有一般偏好的稳定婚姻问题的研究偶尔发生0这些我们包括在表1中，以便对它们进行结构化概述。亚伯拉罕[1]允许不传递但无环的偏好列表，他将稳定室友问题与具有不传递、无环偏好列表的最大规模弱稳定婚姻问题联系起来，以得出结构化的观点。Aziz等人[3]讨论了不确定成对偏好下的稳定婚姻问题。他们还考虑了确定但循环的偏好情况，并表明决定是否存在弱稳定匹配如果双方都可以在他们的偏好中有循环，则是 NP-完全的。Farczadi等人[11]讨论了强稳定和超稳定匹配。在他们的文章中，他们假设一方有严格的偏好，并证明了如果另一方有循环列表，则可以在多项式时间内找到强稳定匹配或超稳定匹配（或证明不存在），其中允许长度至少为3的循环出现，但是一旦允许长度为2的循环，问题就变得 NP-完全。01.2 我们的贡献0本文旨在为各种偏好结构下的稳定婚姻问题的复杂性提供一个连贯的框架。我们考虑了已知的三种稳定性概念：弱稳定、强稳定和超稳定。在我们的分析中，我们区分了偏好列表中的六个熵阶段：严格列表、带有并列关系的列表、偏序、无环成对偏好、非对称成对偏好和任意成对偏好。所有这些都在早期的论文中已经定义，并附有一些关于它们的结果。在这里，我们收集和组织了这些已知结果在所有三种稳定性概念中的所有六种有序性情况，考虑了双部图的每一侧的六种情况。表1总结了这些结果。行和列区分了图的两侧考虑的偏好关系。单元格本身显示了确定指定问题是否存在稳定匹配的复杂性类。7:4Á. Cseh and A. JuhosTable 1. The Complexity Tables for Weak, Strong, and Super-stabilityWEAKstricttiesposetacyclicasymmetric or arbitrarystrictO (m) [14]O (m) [19]O (m) [31]O (m)NPCtiesO (m) [19]O (m) [31]O (m)NPCposetO (m) [31]O (m)NPCacyclicO (m)NPCasymmetric or arbitraryNPC [3]STRONGstricttiesposetacyclicasymmetricarbitrarystrictO (m) [14]O (m) [19, 25]O (m) [11]O (m) [11]O (m) [11]NPC [11]tiesO (nm) [19, 25]O(m2)O(m2)O(m2)NPC [11]posetNPC [22]NPC [22]NPC [22]NPC [22]acyclicNPC [22]NPC [22]NPC [22]asymmetricNPC [22]NPC [22]arbitraryNPC [22]SUPERstricttiesposetacyclicasymm.arbitrarystrictO (m) [14]O (m) [19]O (m) [19, 32]O (m) [11]O (m) [11]NPC [11]tiesO (m) [19]O (m) [19, 32]O(m2)O(m2)NPC [11]posetO (m) [19, 32]O(m2)O(m2)NPC [11]acyclicNPCNPCNPC [11]asymmetricNPCNPC [11]arbitraryNPC [11]For the sake of conciseness, NP-completeness is shortened to NPC. The number of agents in the input is denoted by n,while m stands for the number of acceptable pairs. Each blank cell under the diagonal of the table represents the samecase—and thus has the same complexity—as the cell mirrored to the diagonal. All of our positive results also deliver astable matching or a proof for its nonexistence.Structure of the article. We define the problem variants formally in Section 2. Weak, strong,and super stable matchings are then discussed in Sections 3, 4, and 5, respectively. In Section 6, wefocus on non-bipartite instances and then conclude with an open problem in Section 7.2PRELIMINARIESIn the stable marriage problem, we are given a not necessarily complete bipartite graph G = (U ∪W , E), where vertices in U represent men, vertices in W represent women and edges mark theacceptable relationships between them. Each person v ∈ U ∪W specifies a set Rv of pairwisecomparisons on the vertices adjacent to them. These comparisons as ordered pairs define fourpossible relations between two vertices a and b in the neighborhood of v.(1) a is preferred to b, while b is not preferred to a by v: a ≺v b;(2) a is not preferred to b, while b is preferred to a by v: a ≻v b;(3) a is not preferred to b, neither is b preferred to a by v: a||vb;(4) a is preferred to b, so is b preferred to a by v: a ∼v b.0第三个选项被解释为不可比较或两个代理之间尚未知的关系。最后一个关系表示v确定这两个选项是同样好的。例如，如果v是一个考虑向球员a和b中的一个提供合同的体育赞助商，那么0ACM Transactions on Economics and Computation，第9卷，第1期，文章7。出版日期：2020年12月。0稳定婚姻问题中的成对偏好7:50在以下情景中，v的偏好由这四种关系描述：a击败了b，b击败了a，a和b尚未互相比赛，最后，a和b打成平局。四种关系的更精确的数学解释基于成对比较的集合Rv：第一种等价于(a，b)∈Rv，但(b，a)�Rv。第二种恰好相反：(a，b)�Rv，但(b，a)∈Rv。第三种表示(a，b)�Rv和(b，a)�Rv，最后一种是(a，b)∈Rv，且(b，a)∈Rv。0我们说边va严格优先于边vb，如果a�v b。如果a�v b或a||v b，则b不0优先于a。当且仅当(b，a)�Rv时才会发生这种情况。对于我们之前关于球员a和b的例子，这种关系提供了这样的信息：要么a击败了b，要么他们尚未比赛。在这种程度上的一些不确定信息，体育赞助商没有理由选择b，但选择a也涉及风险，因为可能仍然存在这样的情况，即这两名球员尚未互相比赛，b可能会击败a。对于三种稳定性概念中的两种，我们将基于这种风险定义阻塞。另一种选择是在上述定义中用a�v b代替a||vb，这将等同于(a，b)∈Rv。虽然这会导致一个同样正确的模型，但我们有意选择了不可比较而不是同样好。一些早期的论文[19，20]没有区分两个代理之间的不可比较和同样好，而一些更近期的文献[3，11]则用不确定的信息来推动强稳定性和超稳定性。我们的定义符合更近期的框架。0匹配M中顶点v的伙伴用M(v)表示。图G中v的邻域0用NG(v)表示，它包括所有与v在G中相邻的顶点。类似地，NG(X)表示顶点集X�V的邻域，它包括所有与G中至少一个顶点x∈X相邻的顶点。为了简化表示，我们引入空集作为每个顶点的可能伙伴，表示在匹配M中保持不匹配的顶点（M(v)=�）。通常，与任何可接受的顶点匹配被优先于完全不匹配：对于每个a∈N(v)，a�v�。不存在与不可接受伙伴的边，因此它们之间或与与v关联的边之间不存在成对关系。0我们在研究中区分了六种偏好排序程度。0（1）最严格的、经典的双边模型[14]要求每个顶点对其所有邻居进行排名0对于每个顶点，这转化为顶点v的所有相邻顶点之间的传递性、反对称性和完全的一致的一组成对关系(a，b)∈Rv。0（2）这个模型很早就被放宽到允许有关系的列表[19]。成对的偏好0顶点v的邻居形成偏好列表，如果v的邻居可以被聚类成一些集合N1，N2，...，Nk，使得同一集合中的顶点是不可比较的，而对于不同集合中的任意两个顶点，集合索引较低的顶点严格优先于另一个顶点。0（3）遵循传统[13,20,22,31]，我们定义的有序性的第三程度是当0偏好被表达为偏序集。任何一组反对称和传递的成对关系(a,b)∈Rv根据定义形成一个偏序集。0（4）通过放弃(a, b)∈Rv的传递性，但仍保持结构无环，我们得到0对无环偏好[1]。例如，这个类别允许a||vc，如果a�vb�vc，但它排除了a�vc和a�vc。0（5）不对称偏好[11]可能包含长度至少为3的循环。这相当于0从前一个集群中删除无环性，但仍禁止不确定关系a�vb，这本质上是一个2-环形式(a,b)∈Rv，(b, a)∈Rv。0（6）最后，任意一组成对偏好也可以被允许[3,11]。0如果一个匹配是稳定的，那么它就不会有阻塞边。对于严格的偏好，阻塞边是0在Gale和Shapley的开创性论文中定义：如果uv�M，那么边uv阻止匹配M，如果两者都0《ACM Transactions on Economics and Computation》，第9卷，第1期，第7篇文章。出版日期：2020年12月。07:6 Á. Cseh and A. Juhos0u和v彼此更喜欢彼此而不是他们的M中的伙伴，或者他们没有匹配。当将这个概念扩展到带有并列关系的偏好列表时，就需要指定如何处理不可比性。Irving[19]定义了三种稳定性概念。我们将它们扩展到接下来的三个部分的成对偏好中。在没有关于所讨论的稳定性类型的歧义的情况下，我们省略了weakly、strongly和super这些形容词。0我们在这里定义NP-完全[4]可满足性问题(2,2)-e3-sat，因为它将被用于0在稍后的定理3.4和5.5的证明中。它的输入是一个布尔公式B，以合取范式形式出现，其中每个子句包括确切的3个文字，每个变量正好以正和否定形式各出现两次。决策问题是是否存在一个满足B的真值赋值。03 弱稳定性0在弱稳定性中，如果一条边在M之外，它被它的两个端点严格优先于匹配边，则会阻塞M。根据这个定义，w�uw′和w||uw′在弱稳定性中是可交换的，因为阻塞只发生在非匹配边在两个端点严格优先于匹配边的情况下。因此，可以假定具有任意成对偏好的实例是不对称的。0定义3.1（弱稳定性的阻塞边）。如果边uw阻止M，则0（1）uw �M；（2）w � uM(u)；（3）u �0对于弱稳定性，偏好结构一直到偏序集都已经被研究，见表1。0在这些情况下保证存在稳定解[19,31]。在这里，我们将这个结果扩展到无环列表，并用一个难度证明来补充所有出现不对称列表的情况，即使它们只出现在一侧。0定理3.2. 对于具有无环成对偏好的稳定婚姻问题的任何实例0所有顶点都有一个弱稳定匹配，并且有一个多项式时间算法来确定这样的匹配。0证明。我们利用一个广泛使用的论证[19]来证明这一点。无环0在有限集合V = (v1, v2, ..., vn)上的一组成对关系R的集合是V的一个全序π = π1, π2, ..., πn，使得只要vi � vj出现在R中，就有πi <πj。对于无环关系Rv，存在一个线性扩展R′0v存在。具有线性偏好的扩展实例有保证地0以接受一个稳定匹配[14]。与Rv相比，R'中的关系0v对0稳定解的原始集合。如果双方都有无环列表，那么稳定匹配就有保证存在，并且在扩展实例上的一次Gale-Shapley算法运行可以得到一个。0Gale-Shapley算法在具有扩展偏好的实例中的时间复杂度0是O(m)。在每个顶点上构建一组无环关系的线性扩展是预处理阶段的一部分，就像[31]中一样。这个阶段的复杂性严重依赖于R'的格式0v在输入中，O(n^3)作为整个图的上界[23]。□0只要偏好中出现循环，稳定匹配就不能保证存在，0例3.3展示了。定理3.4表明，从那时起，决策问题实际上是困难的。0例3.3.在下面的实例中找不到稳定的匹配，其中一侧有严格的列表0一侧和另一侧有非对称的列表。有三个男人u1，u2，u3与一个女人w相邻。0ACM Transactions on Economics and Computation，第9卷，第1期，第7篇文章。出版日期：2020年12月。0稳定婚姻问题中的成对偏好7:70图1.左侧是一个变量小工具，右侧是一个子句小工具。严格的列表应该在t，f和u顶点找到，而其余的顶点具有非对称的关系。列表中的u和x/¯x代表相应的ui和x或¯x顶点。互连边是虚线。这些互连边建立的连接表示确切的子句。箭头指向严格优先的边，而虚线表示不可比性。0女性的成对偏好是循环的：u1 � u2，u2 � u3，u3 �u1。任何稳定匹配M必须由一条边组成。由于男性的偏好是相同的，我们可以假设M={u1w}而不失一般性。然后u3w阻止了M。0定理3.4. 如果一侧有严格的列表，而另一侧有非对称的成对偏好，0然后确定是否存在弱稳定匹配是NP完全的，即使每个代理最多只接受其他四个代理。0证明。我们要将我们的问题归约到的NP完全问题是(2,2)-e3-sat [4]，在第0tion2.在构建图G到给定的布尔公式B时，我们跟踪每个子句中的三个文字和每个变量的两个正出现和两个否定出现。每个出现由一个互连边表示，它在相应的变量和子句小工具之间运行。我们的小工具下面的图表明了我们的构造，特别是其中的偏好关系。0对于B中的每个变量x，我们创建四个顶点：t，¯x，f和x。对于B中的每个子句，我们创建六个0顶点：u1，u2，u3，w1，w2和w3。0在每个变量小工具中，x代表变量的两个正出现，而¯x代表0对于两个否定出现。每个变量小工具的边集包括一个4-循环t，¯x，f，x和四个互连边，其中两个与x相邻，其余两个与¯x相邻。这四个互连边负责子句和变量小工具之间的通信，并且它们将顶点x和¯x连接到子句小工具中的u顶点。0ACM经济与计算交易，第9卷，第1期，文章7。出版日期：2020年12月。07:8 Á. Cseh and A. Juhos0子句小工具由六个顶点 u 1，u 2，u 3，w 1，w 2 和 w 3 组成的完全双部图0其中，每个 u侧的顶点都配备有一条连接边。这一侧代表子句中的三个文字。每条连接边从文字的变量小工具中的 u 顶点到顶点 x 或 ¯ x 。如果文字是正的，那么这条边的另一端顶点是对应变量小工具中的 x，0双边图的两侧将由所有小工具中的顶点 t，f，u 1，u 2，u 3 形成0一侧是所有小工具中的 t，f 的顶点，u 1，u 2，u 3，另一侧是所有小工具中的 x，¯ x，w 1，w2，w 3 的顶点。小工具内部的边连接 t，f 与 x，¯ x 的顶点，子句小工具内部的边连接 u 1，u2，u 3 与 w 1，w 2，w 3 的顶点，最后，连接边连接 u 1，u 2，u 3 与 x，¯ x的顶点。这保证了构造图的双边性质。0声明1. 如果图 G 中存在一个弱稳定匹配 M ，那么存在一个满足的真值赋值0fies B .0稳定匹配包括每个变量小工具的� tx，f ¯ x�或� f x，t ¯ x�。可能出现两种情况。0• 如果 tx ∈ M，则 f ¯ x ∈ M；否则， f x 阻止 M。• 如果 tx � M，则 f x ∈M；否则， tx 阻止 M。此外， t ¯ x ∈ M；否则， t ¯ x0阻止 M。0我们知道，根据定义，所有弱稳定匹配都是包含关系上的最大值。从这0事实和我们上面的论点表明，限制在任意子句小工具上的 M必须是一个完美匹配。子句小工具中的偏好设置为，从三条连接边中，恰好有一条在子句小工具上严格优先于 M，即与匹配到 w 1 的顶点 u i 相匹配的边。我们知道 M是稳定的，因此，这条连接边 xu i 或 ¯ xu i 不能在其另一端顶点 x 或 ¯ x处严格优先于匹配边。只有当顶点 u i 所代表的变量被设置为0• 如果文字在 u i 所属的子句中是正的，则为 true，并且上面的结束顶点0是 x；0• 如果文字在 u i 所属的子句中以否定形式出现，则为 false，并且结束顶点0上面是 ¯ x。0因此，我们在每个子句中找到了一个满足的文字。□0声明2. 如果存在一个满足 B 的真值赋值，那么图 G 中存在一个稳定匹配 M。0证明。在属于真变量的每个变量小工具中，选择� tx，f ¯ x�，而所有0与 false 变量对应的小工具贡献了边� f x，t ¯x�。在每个子句中，至少有一个真文字。我们将代表满足该文字的顶点匹配到 w 1，并将 w 2 和 w3 任意匹配。0在每个小工具内部没有边阻止 M，因为它在每个小工具内部都是完美匹配0偏好要么形成一个循环（变量小工具），要么一侧是不确定的（子句小工具）。在子句小工具中，连接边只有在严格优先于 M时才被选择。我们的规则确切地设置了在变量小工具中满足的文字，即，这个文字被匹配到t，这是严格优先于对应的连接边。□0有了这个，我们已经完成了我们的难度证明。□0ACM经济与计算交易，第9卷，第1期，文章7。出版日期：2020年12月。0稳定婚姻问题中的成对偏好7:904 强稳定性0在强稳定中，如果边在M之外，它被一个端点严格优先于匹配边，而另一个端点不优先于它的匹配边，那么它会阻止M。0定义4.1（强稳定性的阻塞边）。如果uw阻止M，那么0(1) uw∈M; (2)w�uM(u)或w||uM(u); (3)u�wM(w)，0或0(1) uw∈M; (2) w�uM(u); (3)u�wM(w)或u||wM(w)。0最大数量的相关出版物出现在强稳定性上，但仍然存在差距0在复杂性表中，参见表1。在本节中，我们提出了一个多项式算法，适用于尚未解决的所有情况。我们假设男性具有带有并列关系的偏好列表，而女性具有非对称关系。我们的算法返回一个强稳定匹配或其不存在的证明。它可以看作是Irving算法的扩展版本，用于具有双方都有并列关系的强稳定匹配实例。我们的贡献是一个复杂的拒绝例程，在这里是必要的，因为女性偏好的不传递性。[11]中的算法解决了男性偏好列表严格的情况，比我们的简单得多。它是为超稳定匹配设计的，但是如果一方有严格的偏好列表，强稳定和超稳定没有区别。一旦我们允许男性偏好列表上的并列而不是严格的列表，这两组匹配就会有所不同，因此将不足以应用为超稳定设计的算法。04.1 我们的算法0直观地，我们的算法在两个阶段之间交替进行，这两个阶段都会迭代消除不能出现在强稳定匹配中的边。在第一阶段，进行Gale-Shapley的提议和拒绝，而第二阶段专注于在指定子图中找到违反Hall条件的顶点集。最后，如果没有边可以再被消除，那么我们将证明每个最大匹配要么是稳定的，要么是不存在稳定匹配的证明。算法1及其下面的子例程算法2提供了伪代码。0算法的第二阶段依赖于二部图中关键集的概念0也在[19]中使用，我们在这里概述。对于详尽的描述，我们建议读者参考[29]。众所周知的Hall条件[16]表明，如果且仅当对于每个X�U，|N(X)|≥|X|时，存在覆盖整个顶点集U的匹配。直观地，没有匹配能够覆盖U中的所有顶点的原因是其中的一个子集X在W中的邻居太少，无法覆盖X。差值δ(X)=|X|−|N(X)|被称为X的缺陷。很明显，对于任何X�U，如果δ(X)>0，则X中至少有δ(X)个顶点无法被G中的任何匹配覆盖。让δ(G)表示U的所有子集中的最大缺陷。由于δ(�)=0，我们知道δ(G)≥0。此外，可以证明最大匹配的大小为ν(G)=|U|−δ(G)。如果我们让Z1，Z2是U的两个任意子集，实现最大缺陷，那么Z1∩Z2也具有最大缺陷（参见[29，引理1.3.2和1.3.3]）。因此，U的所有最大缺陷子集的交集是具有最大缺陷的唯一集合，具有以下属性：它具有最小的基数，并且包含在所有其他具有最大缺陷的子集中。这个集合被称为G的关键集。最后，计算关键集是很容易的，因为对于G中的任何最大匹配M，关键集由U中未被M覆盖的顶点和通过交替路径从未覆盖的顶点到达的U中的顶点组成。0我们现在准备陈述我们算法的定理。0ACM经济与计算交易，第9卷，第1期，文章7。出版日期：2020年12月。07:10 Á. Cseh and A. Juhos0定理4.2. 如果一方有并列偏好，而另一方有非对称的两两偏好0然后，决定实例是否存在强稳定匹配（如果存在，则输出一个）可以在O(m2)时间内完成。0算法1: 具有关系和非对称关系的强稳定匹配0输入：I0初始化1: 对于每个u∈U，在他的列表末尾添加一个额外的女人wu；wu只对u可接受2:将所有边设置为非活跃状态0阶段1 3: 当存在没有活跃边的男人时，进行4:在他的列表中没有活跃边的每个u上的所有边上提出下一个提议05: 对于每条新的提议边uw06: 拒绝所有边u'w，使得u�wu'07: 结束for循环08: 调用strong_reject09: 结束循环0阶段2010: 让GA成为具有VA(GA)=U∪W的活跃边图11:让U'�U成为相对于GA的关键男人集12: 如果U' ≠ �则013: 拒绝U'中每个u的所有活跃边014: 调用strong_reject015: 转到阶段1016: 结束如果0输出17: 让M成为GA中的最大匹配18:如果M覆盖了曾经有活跃边的所有女人，则19:停止，输出M∩E和“存在强稳定匹配。”020: 否则021: 停止，输出“不存在强稳定匹配。”022: 结束如果0算法2: strong_reject023: 让R成为没有活跃边的男人集合024: 当R有一个元素u时，拒绝所有u'w，使得w在u的提议中，并且u' ||026: 如果u'w是活跃的，并且u'已经没有活跃的边了，则让R：= R∪{u'}027: 让R：= R\{u}028: 结束循环0初始化。我们假设男人有并列的列表，而女人提供非对称的两两偏好0偏好。为了证明在第4.2节中的清晰度，我们在每个男人u的列表底部添加一个虚拟伴侣wu，其中wu对任何其他男人都不可接受（第1行）。我们称修改后的实例为I'。这种标准的技术修改是为了确保所有男人在所有稳定的情况下都能匹配0ACM经济与计算交易，第9卷，第1期，文章7。出版日期：2020年12月。matchings. At start, all edges are inactive (line 2). The possible states of an edge and the transitionsbetween them are illustrated in Figure 2.First phase. The first phase of our algorithm (lines 3–9) imitates the classical Gale-Shapleydeferred acceptance procedure. In the first round each unmatched man simultaneously proposesto all women in his top tie (line 4). The so-far-inactive edges that now carry a proposal are calledactive proposal edges or just active edges. Active edges stay active as long as they are accepted bythe woman they run to, and they become rejected proposal edges as soon as they are rejected byher. The tie that a man has just proposed along is called the man’s proposal tie. If all edges in theproposal tie are rejected (or more precisely, they become rejected proposal edges), then the mansteps down on his list and proposes along all edges in the tie following the rejected tie in the man’spreference order (lines 3 and 4).Proposals cause two types of rejections in the graph (lines 5, 6, and 8), based on the rules below.Notice that these rules are more sophisticated than in the Gale-Shapley or Irving algorithms [14,19]. The most striking difference may be that rejected edges are not deleted from the graph, sincethey can very well carry a proposal later, which proposal then affects the state of other edges bytriggering rejections. To be fully ac
我的内容管理
展开
