双边匹配市场中的社会融合

一个匹配方案σ：（MS）∪ WS）×2S7→ （毫秒∪ WS）是为每个P指定匹配σ（·，P）的函数∈ 2S，即σ（·，P）：（MP∪WP）7→ （MP∪WP）。匹配机制Γ是一个函数7.→ Γ()从所有偏好文件集到所有匹配方案集。要给出一个扩展MP和匹配方案的示例，请考虑一个有两个社区a和B的社区，每个社区有一男一女。代理人的偏好是，A社区的男性（mA）比B社区的女性（wB）更喜欢A社区的女性（wA）。其余代理的首选项总结如下amAwBmB瓦马瓦mBwBmBwBmAA可能的匹配方案σ为σ（mA，A）=wA，σ（mB，B）=wB，σ（mA，S）=wB，σ（mB，S）=wA。我们将在命题1.3.1中返回此示例。效率匹配模式我考虑两个众所周知的效率属性。首先是稳定性。除了其直观的吸引力外，稳定性的概念也是一些现实生活中匹配机制成功与否的良好预测因素（Roth和Sotomayor，1992）。定义1（稳定性）。A匹配u：（WP）∪ MP）7→ （WP∪ MP）如果没有人m，则不稳定∈ M无女性w∈ wP彼此未结婚（u（m）6=w），因此wmu（m）和mwu（w）。任何这样的对（m，w）都称为阻塞对。帕累托最优是一个较弱的效率特性。这可以说是经济学中最基本的效率考虑。它只要求在不伤害任何其他代理人的情况下，不可能让一个代理人变得更好。为了简单起见，我假设每个男人（代表女人）都喜欢与任何女人（代表男人）匹配，而不是独自一人。定义2（帕累托最优）。A匹配u：（WP）∪MP）7→ （WP∪如果没有其他匹配u，使得每个试剂x的u（x）<xu（x），则MP）是帕累托最优的∈ （WP∪ MP）和u（y）yu（y）对于某些试剂y∈（WP∪ MP）。匹配的性质很容易扩展到匹配方案和机制。

如果匹配σ（·，P）在每个总体P中是稳定的（帕累托最优），则匹配方案σ是稳定的（帕累托最优的） S、 如果匹配模式Γ() 相对于优先文件而言是稳定的（帕累托最优）.3.2。Pro Integration匹配模式我引入了两个Pro Integration属性。第一种是弱积分单调性（WIM）。它要求在所有社区整合时，不伤害任何代理。定义3（弱积分单调性）。一个匹配方案σisWIM-ifC∈ S和x个∈ （MC∪ WC），σ（x，S）<xσ（x，Cx）。WIM匹配方案确保在社区合并后，每个代理的效果都会弱一些，因此它鼓励不相交社区的完全集成。一个更强的概念是积分单调性（IM）。它要求在任何两个不相交的群体融合的时候，都不要伤害任何一个人。定义4（积分单调性）。匹配方案σ为IM ifP、 P∈ 2S使P∩ P= 和x个∈ （MP∪ WP），σ（x，P∪ P） <xσ（x，P）。如果匹配方案Γ() 是否与优惠文件相关的IM（分别为WIM）.IM匹配方案保证了两个重要属性。首先，完全的社会融合将独立于我们合并社区的顺序而发生（该顺序可能会影响谁与谁结婚，但融合总是使代理人在仅匹配方面发挥更好的作用。相比Ashlagi andRoth（2014）中的个人理性财产，IM的要求更高，这就要求在所有社区整合后，每个社区匹配的代理数量会略微增加。如果所有代理人在融合发生后都与最差的伴侣结婚，那么个人理性是令人满意的。

整合后的婚姻数量（微弱）较高，但（某些）代理人显然是不称职的。在社会的一个子群体中）。第二，在所有社区的融合发生之后，没有一个社区的子集希望与社会的其他部分分离，从而与其自身相匹配。这两个需求证明了IM的定义是正确的。在介绍我的结果之前，我讨论了效率与pro积分属性之间的关系。可以推测，积分单调性与帕累托最优相结合意味着稳定性。鉴于文献中已有的类似结果，这一猜想是自然的。然而，这个猜测是错误的。考虑一个有两个社区的社会。一个有一个漂亮的男人和一个丑陋的女人，而另一个有一个丑陋的男人和一个邋遢的女人。总是将人与自己社区中的人结合在一起的匹配方案是积分单调和帕累托最优的（如果丑人喜欢漂亮的人而不是丑人）。然而，这种匹配方案并不稳定：与配偶相比，漂亮的男人和女人更喜欢对方。4、结果构建稳定的IM匹配机制是理想的。不幸的是，我们甚至缺乏一个稳定的WIM匹配机制。提案1。对于每个至少有两个社区的社会，没有一种稳定匹配机制是弱整合单调的。证据让A和B成为两个社区，每个社区有一个男人和一个女人。考虑以下偏好文件华盛顿州mAwBmB瓦马瓦mBwBmB所有的女人都喜欢mba，所有的男人都喜欢wA。匹配模式的稳定性要求σ（wA，a）=mA，σ（wB，B）=mB，和σ（wA，a∪ B） =mB。然而，当社区a和B合并时，男人和女人都会得到一个更糟糕的伴侣。

因此，对于优惠文件, 任何稳定的匹配机制Γ都会生成匹配方案Γ() 那不是维姆。命题1是一个预期结果，因为众所周知的结果表明，增加一个男人会使每个女人的效果都弱得更差，在具有可转移效用的合作博弈中，人口单调性和效率意味着核心属性（Sprumont，1990）。在交换经济中，整合单调性和效率意味着核心属性（Chambers和Hayashi，2017）。在引言中。然而，命题2表明，尽管稳定匹配机制不能保证所有主体在融合发生后都有微弱的改善，但它们不会伤害社会中超过一半的主体。提案2。在任何稳定匹配方案中σ*,{x∈ （毫秒∪ WS）：σ*（x，Cx）xσ*（x，S）}≤MS公司∪ WS系列界限很紧。证据让我们把S分成三个集合S，S+和S-, 定义的asS：={x∈ （毫秒∪ WS）：σ*（x，S）=σ*（x，Cx）}S+：={x∈ （毫秒∪ WS）：σ*（x，S）xσ*（x，Cx）}S-:= {x∈ （毫秒∪ WS）：σ*（x，Cx）xσ*（x，S）}因此，Sis是在整合后保持同一伙伴的人的集合，S+是那些喜欢他们的“整合”伙伴的人，S-是那些喜欢“隔离”伴侣的人。考虑任意一对（x，σ*（x，Cx））。如果x∈ S-, σ*（x，Cx）∈ S+因为其他（x，σ*（x，Cx））构成匹配σ的块对*（·，S），与σ*是一个稳定的匹配方案。由此得出| S+|≥ |S-|, 因此| S |+| S+|≥ |S-|. 因此{x∈ （毫秒∪ WS）：σ*（x，S）<xσ*（x，Cx）}≥MS公司∪ WS系列/2，完成预防。命题1证明中使用的例子表明，一个半界是紧的。命题1表明，稳定性不能与pro integrationcriteria相结合。

然而，命题3表明，即使帕累托最优的效率特性相当弱，也与IM不兼容。提案3。对于每个至少有三个社区的社会，没有一个Paretooptimal匹配机制是整合单调的。证据让A、B和D成为三个社区，每个社区有一男一女。考虑以下偏好文件wB公司mAwD公司马瓦姆wAmD公司wAmAwD公司mBwA公司mBwBmDwBmAwBmBwA公司mDwB公司mDwDmAwDmBwDmDAgents的偏好是，社区A的代理更喜欢来自B的代理，B的代理更喜欢来自D的代理，D的代理更喜欢来自A的代理。所有帕累托最优匹配方案都需要σ（wA，A∪ B） =mB，σ（wB，B∪ D） =mD和σ（wD，D∪ A） =毫安。请注意，在任何Paretooptimal匹配方案中，每当我们只合并两个社区时，总会有一个社区获得其FirstChoice。IM要求，当我们聚合所有社区时，所有代理都应该做得至少和只有两个社会合并时一样好，即σ（mA，S）<mAwBσ（wA，S）<wAmBσ（mB，S）<mBwDσ（wB，S）<wBmDσ（mD，S）<mDwAσ（wD，S）<wDmAThis是不可能的，因为某些代理将不再能够获得第一选择。命题1和命题3表明，效率和亲集成属性相互矛盾。他们只能在各自的弱版本中共同满足。很明显，帕累托最优和WIM匹配方案总是存在的。我们可以通过将每个代理与他们自己的社区相结合来获得它们，然后在初始匹配时重复执行帕累托改进。请注意，种群是一组外源给定的群落。我们可以考虑一个更强大的集成单调性概念，每当两个任意的代理集（而不是社区集）合并时，需要弱的改进。这个概念比Iconsider的概念更强大。

因此，当使用积分单调性这一更强大的概念时，命题3中描述的不可能性就存在了。5、稳定匹配机制整合的收益在本节中，我量化了整合发生后发生的福利变化。我通过整合前后代理获得的排名差异来衡量这些变化。由于该分析使用了现有的结果，因此我将假设每个社区都有nmen和n个女性。尽管有限制性，但这一假设允许我将融合的影响与不平衡社会的影响隔离开来。在一个只有两个社区的社会中，IM和帕累托最优是相容的。这是因为，对于这样一个社会，IM和WIM是等价的。Ashlagi等人（2017）详细讨论了他们的性别比例。这一假设意味着所有代理都是在任何稳定匹配中结婚的。我还始终假设，在积分前后发生的匹配是men最优稳定匹配（MOSM）。MOSMis是一种稳定的匹配，在任何其他稳定的匹配中，没有人能找到更好的伴侣，而且它总是存在的。这一假设使我能够比较不同稳定匹配中代理人的福利，Dogan和Yenmez（2017）、Hafalir和Yenmez（2017）以及Ekmekci和Yenmez（2018）也提出了这一假设。这一假设在多个应用中得到了验证。例如，学生的最佳稳定匹配是有吸引力的，并且在学校选择中是一致选择的（Abdulkadiroglu和S¨onmez，2003）。类似地，theresident optimal stable matching也被用于为美国的医院分配医学实习生（Roth和Peranson，1999）。

I用σ表示*themen最优匹配方案，使σ*（·，P）是匹配问题（MP，WP；P） 和σ*（·，C）表示MP的MOSM（MCi，WCi，Ci），Ci公司∈ S、 现在我介绍一些有用的定义。给定一个社会，通过为每个男人和每个女人独立地、均匀地随机绘制一个完整的偏好列表，生成一个扩展的随机MP。Wilson（1972）首次对随机MPs进行了研究，并从那时起进行了广泛研究。rkm（w）定义了女性在男性m（社会中所有潜在配偶）优先顺序中的绝对排名w：={w∈ WS:w<mw}.同样，我使用rkw（m）表示m在优先顺序w中的绝对排名。给定匹配的u，男性妻子的绝对平均排名由km（u）定义：=| MS | Xm∈MSrkm（u（m））相同的符号用于表示女性丈夫的平均排名rkW（u）。在第6节讨论不平衡社区的融合之前，男性从融合中获得的收益反映了男性平均妻子级别之间的差异。形式上，我应该写σ*p因为MOSM取决于偏好文件P、 同样，我应该写在rkm（w，m） 和rkM（u，M） 表示男性对女性的排名和男性对妻子的平均排名，因为两者都取决于优先顺序需求偏好文件M、 然而，我在文献之后简化了符号（Ashlagi et al.，2017，第75页），因为很明显这些对象取决于代理的偏好。在MOSM下进行集成后。形式上，γM：=rkM（σ*（·，C））- rkM（σ*（·，S））相同的符号用于表示女性从融合中获得的收益γW。更高的排名意味着不太理想的人，因此，每当γ和γ分别为正值时，男性和女性都有融合的预期。

提案4确立了融合的预期收益对男性和女性都是积极的，并为代理人和社区数量较多的MPs提供了一个近似值。提案4。在一个随机扩展的带有κ的MP社区中，每个社区都有nmen和n个女性，E[γM]~ 日志nκ-1κ（1） E[γW]~ κn日志n-对数κn（2） 证明。我从一些关于标准MPswithκ=1的预备知识开始证明。McVitie和Wilson（1971）算法是延迟接受算法的改进，在延迟接受算法中，每个步骤只有一个人向一个女人求婚。让X表示该算法查找MOSM所需的提案数量。使用息票收集器问题，我们得到（见Motwani和Raghavan，1995；第58页）E[X]=n log n+O（n）~ n log n因为男性首先向他们最喜欢的女性求婚，E（X）/n是预期男性妻子的绝对平均排名，soE[rkM（σ*（·，S））]=logn+O（1）~ log nEach女性期望收到log（n）提案。她接受的是来自她最喜欢的伴侣的。随机变量[rkW（σ*（·，S））- 1] 与参数（n）呈二元分布-函数f（n，κ）和g（n，κ）是渐近等价的f（n，κ）~ g（n，κ）iflimn，κ→∞f（n，κ）g（n，κ）=1。日志n，日志n+1）。因此，E[rkW（σ*（·，S））]=nlog n+1+O（1）~nlog NTHES结果由Wilson（1972）、Knuth（1997）和Pittel（1989）证实，Canny（2001）对此进行了详细解释。他们暗示在一个延伸的MP中，与κ共同体[rkM（σ*（·，S））]~ logκnE[rkW（σ*（·，S））]~κnlogκ女性在男性偏好顺序中的相对排名由brkm（w）确定：=|{w∈ 厘米：w<mw}|。它表明了w女性相对于属于同一社区asm的所有女性的排名。类似地，我表示m在wbybrkw（m）的优先顺序中的相对秩。

给出一个匹配的u，男性妻子的相对平均排名由BRKM（u）：=| MS | Xm确定∈MSbrkm（u（m））相同的符号用于表示女性的相对平均耕地面积。Pittel的结果也暗示了e[brkM（σ*（·，C））]~ 对数nE【brkW（σ*（·，C））]~nlog nSo表示，在融合之前，男性和女性获得的伴侣相对排名~ n和~ 在他们自己的社区中登录n。我们需要确定这些合作伙伴在所有MSandWS中的绝对排名。为了回答这个问题，假设一个代理在其社区中的所有代理中排名为q。在代理1和代理2之间，…，来自另一个社区的随机代理可能比代理1更好。。。，代理之间q- 1和q之间，代理q和q+1之间，依此类推。因此，来自另一个社区的随机代理以1/（n+1）和thushas q/（n+1）的概率处于任何这些差距中，比我们最初的代理（1989）排名更高的概率证明了一个更强的说法，即thatrkM（σ*（·，S））日志np→ 1和RKW（σ*（·，S））无对数np→ 1.相对排名q.有n（κ-1） 来自其他社区的男性。平均而言，qn（κ-1） n+1人的排名将比他高。此外，在他自己的社区里，已经有q人的排名比他好。这意味着他的预期排名是q+qn（κ-1） n+1=q（κn+1）n+1~ qκ。将q分别替换为log（n）和n/log（n），我们得到了整合前妻子和丈夫的预期平均rankof。因此e[γM]=对数（n）κ- 对数（κn）~ 日志nκ-1κE[γW]=nlog（n）κ-κnlog（κn）~ κn日志n-对数κn诚然，我们需要强有力的假设才能得出命题4。我们需要平衡且人口均等的社区，以及独立且均匀分布的偏好。

尽管这些假设在实践中很可能被违反，但命题4揭示了最重要的稳定匹配机制（MOSM）如何促进社会融合，尽管它与WIM不兼容。这种配对机制不仅不会伤害到社会的一半以上（命题2），而且在融合发生后（在上述假设下），它还提高了男性妻子和女性丈夫的预期平均排名。尽管命题4是一个渐进的结果，但图1显示，命题4中描述的大型社会整合的预期收益是很好的近似值，即使对于较小的n和κ值也是如此。请注意，女性从融合中受益更多。这一观察结果背后的直觉是，女性获得的伴侣在融入社会之前的排名相对较低，在MOSM下出现。与完全优先顺序中的绝对排名相比，这种较差的相对排名更为明显。在结束本文之前，我描述了那些因整合而受到伤害的代理的一些特征。这些观察结果来自于附录中详细描述的模拟练习。首先，在MOSM下，因融合而受到伤害的女性人数大于相应的男性人数（女性74%，男性26%，n=500，κ=5）。其次，他们的损失程度非常不同。女性受到严重伤害（平均损失303个排名，n=500，k=5），而男性最多只能承受中等程度的损失（平均损失8个排名）。当女性的偏好与之相关时，她们的损失就会变小。因融合而受到伤害的代理人的损失程度变得很小图1：按性别划分的融合收益。（a） r=2（b）r=5这些线表示渐近表达式1和2。这些点代表10000次模拟的平均收益。