饱和稳定匹配 - 外文文献专区

636

收藏 2022-04-20

摘要翻译：
我将二部图匹配与稳定匹配联系起来。对于所有可能的偏好，我证明了饱和稳定匹配存在的充要条件，其中一方的每个主体都是匹配的。我将我的分析扩展到完美的稳定匹配，其中双方的每个代理都是匹配的。
---
英文标题：
《Saturating stable matchings》
---
作者：
Muhammad Maaz
---
最新提交年份：
2021
---
分类信息：

一级分类：Computer Science 计算机科学
二级分类：Computer Science and Game Theory 计算机科学与博弈论
分类描述：Covers all theoretical and applied aspects at the intersection of computer science and game theory, including work in mechanism design, learning in games (which may overlap with Learning), foundations of agent modeling in games (which may overlap with Multiagent systems), coordination, specification and formal methods for non-cooperative computational environments. The area also deals with applications of game theory to areas such as electronic commerce.
涵盖计算机科学和博弈论交叉的所有理论和应用方面，包括机制设计的工作，游戏中的学习（可能与学习重叠），游戏中的agent建模的基础（可能与多agent系统重叠），非合作计算环境的协调、规范和形式化方法。该领域还涉及博弈论在电子商务等领域的应用。
--
一级分类：Economics 经济学
二级分类：Theoretical Economics 理论经济学
分类描述：Includes theoretical contributions to Contract Theory, Decision Theory, Game Theory, General Equilibrium, Growth, Learning and Evolution, Macroeconomics, Market and Mechanism Design, and Social Choice.
包括对契约理论、决策理论、博弈论、一般均衡、增长、学习与进化、宏观经济学、市场与机制设计、社会选择的理论贡献。
--
一级分类：Mathematics 数学
二级分类：Combinatorics 组合学
分类描述：Discrete mathematics, graph theory, enumeration, combinatorial optimization, Ramsey theory, combinatorial game theory
离散数学，图论，计数，组合优化，拉姆齐理论，组合对策论
--

---
英文摘要：
I relate bipartite graph matchings to stable matchings. I prove a necessary and sufficient condition for the existence of a saturating stable matching, where every agent on one side is matched, for all possible preferences. I extend my analysis to perfect stable matchings, where every agent on both sides is matched.
---
PDF下载：
-->

English_Paper.pdf
大小:(122.77 KB)

马上下载

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

全部回复

能者818

2022-4-20 21:31:59

饱和稳定匹配gsmuhammad maazm.maaz@mail.utoronto.caUniversity of Toronto*abstracti将二部g raph匹配与稳定匹配联系起来。对于所有可能的偏好，I证明存在饱和稳定匹配的必要条件，其中一方的每个主体都是匹配的。我把我的分析推广到每一个稳定匹配，其中两边的每个agent都是ma tched.1引言二部图是一个具有两个disj oint顶点集X an d Y,andan边集E的图G，使得s ameset中没有连接两个顶点的边。在二分图中，一个常见的目标是将这两个集合以amatching的形式连接起来，并将其定义为E的子集，使得没有两个边共享一个顶点。Ifa顶点是M中一条边的端点，我们说它是匹配的；否则是无与伦比的。[West,1996]Hall[1935]给出了二部图具有x饱和匹配的一个必要条件，其中每个顶点x∈x都是匹配的。当我们把顶点想象成代理，并允许它们比另一边有优先性时，我们得到了Gale和Shapley[1962]的经典稳定婚姻问题。如果在该匹配中不存在一个不匹配的顶点对(x，y)∈x×y，但它们彼此偏好（注意它们的伙伴可能不是任何人--即它们是不匹配的），则匹配是稳定的；Gale和Shapley[1962]证明了总存在一个稳定的匹配，并通过发展他们著名的延迟接受算法给出了一个构造性p顶。自从他们发表这篇论文以来，加拿大多伦多King\'s College Circle M5S1A8Economics以一种比图论更直接的方式对匹配进行了研究，侧重于稳定性而不是组合学[Roth和Sotomayor，1992]。因此，我们有两个主要的经典定理从两个直接的角度来看待匹配。Hall[1935]给出了一个存在饱和匹配的定理（不一定是稳定的），而Gale和Shapley[1962]给出了一个定理f或存在稳定的m atching（不一定是饱和的）。随着匹配应用的激增，从社会的角度来看，可能希望每个代理都匹配（例如，将每个人都匹配到疫苗接种者，将每个医学生匹配到住院医师）。因此，问题出现了：我们能满足饱和稳定匹配吗？2主要结果考虑一个二分图G=(X+Y,E）。avertex x的邻域d N(x)是与x相邻或共享边的顶点的set，一个顶点集的邻域是每个顶点邻域的并。度deg(x)是相邻顶点的个数，或N(x)。如果P是P个参考关系集，则w hich的元素是每个顶点对其邻域顶点的严格偏好关系（它是可接受的伙伴）。如果Xprefered yto y，我们wr ite x：y y。每个顶点都喜欢一个可接受的顶点而不是不可匹配的顶点，p指的是不可匹配的顶点。所有可能的优先实例的集合是P。SM表示稳定匹配。对某个顶点x定义以下两个条件:N(N(x))≤N(x)(1)πy∈N(x)(deg(y)=1)(2)引理1。如果某个x∈x满足条件（1）或（2）（或两者都满足），则在所有偏好情况下，所有SMs中的itis都匹配。证明。为了矛盾起见，假设这个x在某些方面是不可比的。根据假设，这个x满足N(N(x))≤N(x)或[x](deg(y)=1)，或者其他。情况1:[y](deg(y)=1)观察到这个y是不可匹配的，因为它只有一个可接受的顶点，这就是不匹配的x，它的顶点是x，它的顶点是x，它的顶点是x，它的顶点是x，它的顶点是x，它的顶点是x，它的顶点是x，它的顶点是x，它的顶点是x，它的顶点是x，它的顶点是x，它的顶点是x，它的顶点是N(x)≤N(x)。这个x和y形成一个块对，所以这种匹配是不稳定的，因此是矛盾的。情况2:y∈N(x)(deg(y)=1)x必须满足N(N(x))≤N(x)。如果N(x)中的所有顶点都已经匹配，则观察到x在ly上是不匹配的。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

何人来此

2022-4-20 21:32:06

由于顶点N(x)只能与N（N(x)）中的顶点匹配，所以th是指N（N(x)）-1（N（N(x)）中的顶点数不包括x本身）顶点与N(x)个顶点匹配。根据鸽子洞原理，这是一个矛盾。这耗尽了所有的情况。引理2。如果某个x∈x既不满足条件(1)，也不满足条件(2)，则存在某个偏好实例P∈P，在该实例下它在任何证明中都是不可匹配的。观察这个x是N(N(x))>N(x)和(λy∈N(x))(deg(y)>1)。通过算式，存在满足N(N(x))>N(x)和λy∈N(x)(deg(y)>1)的some x∈x。它显示存在一个使x未匹配的PH。考虑以下首选项实例P:othe a∈N(x):i x,其中i∈N(N(x))-xoπb∈N(N(x))-x:j k,其中j∈N(x)和k∈N(b)-N(x)o所有其他偏好关系都允许不同程度地。粗略地说，P表示x的所有选项都偏好于其其他可接受的顶点而不是x本身，并且x的所有竞争对手都偏好于N(x)中的一个顶点而不是它所能接受的任何其他顶点。现在我们可以证明x在所有SMS中都是不可匹配的。为了矛盾起见，假定存在一个SM M，其中x与某个顶点N(x)匹配。注意到v∈N(N(x))-x与N(x)中的一个顶点匹配。如果有些v不匹配，那么由于所述的偏好，以及假设的第二部分N(x)中的所有顶点的deg>1，所说的v将与N(x)中的某个顶点形成阻塞对。然而，这意味着N(N(x))顶点（x的所有竞争对手plusx本身）与N(x)顶点匹配。但是，由于N(N(x))>N(x)，根据鸽子洞原理，这是一个矛盾。因此，x在P下的所有SMs中是不匹配的。注意deg(y)=1的否定是deg(y)>1，因为它在某个顶点的邻域上，所以deg(y)>0。现在是主要结果。定理1。Ev ery SM对于所有偏好情形是x-饱和的当且仅当对于所有x∈x，条件（1）或（2）（或两者）成立。首先是if方向。对于所有x∈x，条件（1）或（2）或bothhold。根据引理1，所需的语句保持不变。其次，唯一的if方向。根据引理2.2.1的等价陈述，与之相对应的条件是：对于arket设计者来说，如果所有的SMs都饱和，则不一定重要，但如果至少有一个SMs存在，则不一定重要。此外，在使用Gale-Shapley算法的现实匹配市场中，会产生一个非常特殊的SM,它是x-最优的还是Y-最优的（取决于算法的性能），因此设计者可能特别关心输出的SM是否饱和。有趣的是，由于下面的定理，这些实际上都是同一个问题（McVitie and Wilson[1970])。“在一个n个男人和k个女人的婚姻问题中，如果有人在一个稳定的婚姻解中未婚，那么她在所有的稳定解中都是未婚的。”所以，如果一个sin gle SM是x-饱和的（没有人是“未婚的”），那么任何其他SM也是x-饱和的（包括x-最优的，和x-悲观的），实际上是所有的。引理3。对于给定的偏好实例P,任意SM是X饱和的当且仅当所有SM都是X饱和的。证明。摘自麦克维蒂和威尔逊[1970]。推论1。对于给定的偏好实例P，设所有SMs边界元集。然后，对于所有的偏好情形，任意的M∈M是x饱和的当且仅当对于所有的x∈x，条件（1）和（2）中至少有一个是成立的。由定理1和引理3得出，x-最优SM是这样的，即X∈X比其它SM更喜欢它。x-posimalsm是这样的，即：与它相比，X∈X更喜欢每隔一个SM。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

大多数88

2022-4-20 21:32:12

图1：二分图sxxyyXY(a)xxyyyXY(b)xxxyyyyxyxy(c)的例子因此，定理1中的双条件对于存在一个x-饱和匹配，x-最优SM是x-饱和的，或者对于市场设计者感兴趣的任意SM是相同的。这个等价性对于本文的后续结果也是一样的，根据引理3.3应用3.1示范例子看图1a，条件（1）和（2）对于x是违反的，因为(N(x))=2>N(x)=1，所以对于所有的偏好实例都不存在x饱和的SMs。在图1b中，它只是把一个顶点放在1a上，这两个条件对于x都不成立。最后，在图1c中，条件（1）对于x和x都成立。当xviolatescondition(1))时，它确实满足(2)，deg(y)=1和y∈N(x)。3.2完美匹配Gale和Shapley[1962]认为x=y=N和每个x∈x对y∈y是可接受的（反之亦然）（即偏好是完全的）。在图论中，这是一个完全的二部图。Gale和Shapley[1962]说，在执行他们的算法之后，没有一个顶点是不匹配的。在图论条件下，对于所有的偏好情况，他们算法给出的SM是完美的，这意味着每个顶点都是匹配的。这实际上是定理1所暗示的，如插X∈X和插Y∈Y满足条件(1):πX∈X,N(X)=N和N(N(X))=N（由于是一个偶数二分图），所以条件（1）是有的，类似地，插Y∈图2:A连通和一个不连通的匹配市场xxxxyyyyxy（A）连通dxxxxyyyyxy（b）断开连通的匹配市场xxxxyyyyxy（b）断开的匹配市场xxxxyyyyxy（A）。因此，根据定理1，f或所有偏好实例，每个SM都是xsatating和y-satur的，因此是完美的。事实上，如果我们的匹配市场是一个“块”，那么如果X=Y=n，那么获得完美匹配的唯一方法是如果偏好是完全的。在图2b中，我们可以直观地看到有两个独立的块--在图论中称为组件。即使p个引用是不完整的（例如，xdos not foungnd yacception)，显然完美的SM总是存在的。我考虑只有一个compon的图，如图2a。只有一个分量的图称为连通图，它由存在于任意两个顶点之间的路径所修饰[West,1996]。定理2。给出一个连通二部图G=(X+Y,E）,其中X=Y=n,所有SMs对于所有偏好实例都是完美的当且仅当G是完全二部图。首先是方向。如果G是一个完全二部图，那么，λx∈X，λY∈Y满足条件(1)，如前所述，因此，由定理1，所有偏好情况下的Allsm都是x饱和和Y饱和的，意义完全。另一个方面，通过对n的归纳法进行。对于基casen=1，e在X和Y中各为一个ver tex，当G是连通的时，它们有一条边。显然，这是一个完全二部图。其次，假设对于某些n=k，如果所有的SMs对于所有的Preference ceinstances都是完美的，那么GK+1是一个完全二部图。我们希望证明对于n=k+1,GK+1也是一个完全二部图。GK+1是在每个X和Y上加一个顶点形成的，分别称为X andy。因为GK+1是连通的，所以x或y中至少有一个必须分别连接到y或x以外的顶点。在不丧失一般性的情况下，假设它是x，它连接到某个非Y顶点v∈Y，观察N(v)=k+1，因此N(N(x))=k+1。x必须在所有公关实例中的所有短信中bemathed。通过对位定理2,x必须满足k+1≥N(x)≥N(N(x))=k+1,而soN(x)=k+1,这意味着x连接到Y中的每个顶点。通过类似的r easoning,Y也连接到x中的每个顶点，因此我们有一个完全的二分图。因此，通过归纳法，“仅当”陈述成立。我现在将定理2推广到所有图的情况，而不仅仅是连通图的情况。看图2B，这两个组件ind分别在同一组件中的顶点上显示完整的偏好。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

kedemingshi

2022-4-20 21:32:18

这类组件有一个特殊的名称：称为biclique s[West,1996]。在abiclique中，每一个顶点都连接到另一个集合中的每一个顶点（团到二分图的推广）。一个完全二部图是它自己的双列图。推论2。给出具有X=Y的二部图G=(X+Y,E）,当且仅当G i的每个成分都是一个二部图。3.3与相容约束的匹配问题通过研究加拿大医学r esidency匹配，提出了与相容约束的匹配问题，并指出指定的位置要么是f或英语使用者，要么是orFr和ench使用者；一些会双语的学生可以申请任何一个。THeorem 1使我们可以很容易地将th eir模型推广到n个相容类，将顶点集X划分为n个可能重叠集X=AüAüA.⑵安。对于所有i,j∈[1,n],集合ai-üj6=iaj必须是非空的，即th在每个类中必须至少有一个顶点不是其他类的顶点。将集合Y划分为n个不相交的su B集Y=BüB。②BN。参见图3的示意图。如果一个顶点与另一个顶点不属于同一类，则该顶点不能被接受；否则他们可能会，但不一定。在Maaz和Pap在astasiou[2020]研究的相容性完全（或CW-完全）偏好的特殊情况下，每个顶点都可以接受同一类中的每个顶点。定理3。对于n个相容类，在CW完全偏好的所有实例中，每个SM是X饱和的当且仅当Bi≥Ai，且所有1≤i≤n。证明。首先是if d irection。取任意x∈x，它属于一个或多个兼容性类；让这个类列表存储在VectorQ中。则N(x)=pi∈Qbi。此外，注意到N（N(x))是x中也属于相同兼容性类的所有顶点的集合，包括Xithns。因此，N(N(x))=pi∈Qai。因为Bi≥Ai对于所有1≤i≤n，所以条件（1）对于这个x成立，实际上对于所有x成立。根据引理1，结果如下。接下来是“仅当”方向。出于矛盾的原因，存在一个兼容性类i是Bi<ai。至少存在一个Evertex x∈x，它在第ith相容类中，而不在任何其他类中。那么，N(x)=Bi<Ai=N(N(x))，所以它不符合fulferll条件(1)，而且，它也不符合fulferll条件(2)，因为它不能连接到度数为1的顶点y，因为y会违反CW-complete偏好，除非x是唯一的顶点，但违反了Bi<Ai，否则它不能连接到度为1的顶点y。通过引理2，存在一个偏好实例，其SM是n ot x饱和的，这是一个contradiction。这是Maaz和Papanastasiou[2020]限制的推广，即只有一个非零数量的学生只说英语，只有一个非零数量的学生只说法语。图3：匹配2和3个类别的兼容性约束。线表示线的端点接触的两个子集中的每个顶点之间的兼容性；在CW-complete preferences下，行也指示可接受性。aabbx Y(a)2 c Ompatiability Classesaabba(b)3兼容性ClassesReferencesd。盖尔和L.S.沙普利。大学入学与婚姻稳定。《美国数学月刊》，1962年，69(1):9-15.页。大厅。关于子集的代表。J.伦敦数学。Soc,10（1）：26-30,193 5.M.Maaz和A.Papanastasiou。与兼容性约束的匹配：加拿大医学住院医师匹配的C ase。《汉学与制度设计学报》，2020年4:99-117D.G.麦克维蒂和L.B.威尔逊。不等集的稳定婚姻分配。位数字数学，1970年10:295-308.罗斯和索托马约尔。双面匹配。博弈理论与经济应用手册，1992:485-541.B.西部。图论导论，第2卷。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

nandehutu2022

2022-4-20 21:32:18

1996年，新泽西州UpperSaddle River。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

分享

扫码加好友，拉您进群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群