双边合同交易网络

因此RS（˙XS˙XB）=˙XS\\A，RB（˙XB˙XS）=˙XB\\A，所以X\\RS（˙XSXB）=˙XB，X\\RB。B.2命题2和命题3的证明首先，我们证明算子Φ（定义如下）的固定点形成一个完整的子格（子格定理B.3），扩展了Fleiner（2003）的定理7.3和7.5。然后我们展示了终端代理的两个晶格性质（终端子晶格理论EMB.4和终端优势引理B.6）。然后我们用这三个结果来证明命题2和命题3。B.2.1固定点的子格属性首先注意，我们已经在引理1的证明中指出了总需求和总供给（LAD/LAS）定律的直接含义。如果表格f的选择函数满足LAD/LAS，对于合同集Y′ Y XBf和Z Z′ XSf（即（Y′，Z′） （Y，Z））然后|CfB（Y′|Z′）|- |CfS（Z′|Y′）|≤ |CfB（Y | Z）|- |CfS（Z | Y）|。对于每个f公司，我们在Xf合同上定义了一个权重函数，即w（x）=1if x∈ XBfand w（x）=-1如果x∈ XSf。所以w（Cf（Y，Z））=|CfB（Y | Z）|-|CfS（Z | Y）|。因此，如果满足LAD/LAS，那么（Y′，Z′） （Y，Z）表示w（Cf（Y′，Z′）≤ w（Cf（Y，Z））。权重函数可以更一般地定义，见Fleiner（2003）。设Y和Y′是XBf的子集，Z和Z′是XSf的子集。我们在XSfwithZ=XSf\\Z中表示Z的互补。定义运算（Y，Z）e\\（Y′，Z′）=（Y\\Y′，Z′）。对于agiven Firm f，我们称之为集合函数R:2Xf→ 2Xfa w-收缩如果为每（Y′，Z′） （Y，Z）对，w（R（Y，Z）e\\R（Y′，Z′）≤ w（（Y，Z）e \\（Y′，Z′）让我们描述一下这个引理B.1的一些性质。对于一个函数f，假设Y和Y′是XBf的子集，Z和Z′是xsfsuch（Y′，Z′）的子集 （Y，Z）。那么下面的陈述是正确的：1。w（（Y，Z）e \\（Y′，Z′）=w（（Y，Z））- w（（Y′，Z′）- |XSf | 2。对于任何（A，B）对，w（（A，B）e \\（Y，Z））≤ w（（A，B）e \\（Y′，Z′））.3。

If（Y，Z） （A，B）那么w（（A，B）e \\（Y，Z））=w（（A，B）e \\（Y′，Z′）等式意味着（Y′，Z′）=（Y，Z）。莱玛的证据。1.让我们分别处理每种说法：1。w（（Y，Z）e \\（Y′，Z′）=|Y\\Y′|- |Z′\\Z|=|Y|- |Y′|- |XSf |+|Z′|- |Z |=w（（Y，Z））-w（（Y′，Z′）- |XSf | 2。自从 Y′，这意味着A\\Y A\\Y′，和类似的Z Z′给了我们Z\\B Z′\\B，soZ\\B Z′\\B，因此w（（A，B）e \\（Y，Z））=|A\\Y|-|Z\\B|≤ |A\\Y′|-|Z′\\B|=w（（A，B）e \\（Y′，Z′）3。如果w（（A，B）e \\（Y，Z））=w（（A，B）e \\（Y′，Z′），那么等式必须在|A\\Y |=|A\\Y′|和|Z\\B |=|Z′\\B |）处成立。自从Y\' Y A和Z′ Z B、 我们得到Y=Y′和Z=Z′。引理B.2。假设f的选择函数∈ F满足完全可替代性和LAD/LAS。然后是拒绝函数Rfis-等渗酮和w收缩。莱玛的证据。2.设Y和Y′是XBfand的子集，Z′是XSf的子集，且设（Y′，Z′） （Y，Z）。我们之前已经看到了RFI-isotone，so Rf（Y′，Z′） Rf（Y，Z）。为了证明它是w收缩，w（Rf（Y，Z）e\\Rf（Y′，Z′）+|XSf|=w（Rf（Y，Z））- w（Rf（Y′，Z′）=w（Y，Z）\\Cf（Y，Z））- w（（Y′，Z′）\\Cf（Y′，Z′）=w（Y，Z）- w（Cf（Y，Z））- w（Y′，Z′）+w（Cf（Y′，Z′）≤w（Y，Z）-w（Y′，Z′）=w（Y，Z）e \\（Y′，Z′）+|XSf |。我们使用了w（Cf（Y′，Z′）≤ w（Cf（Y，Z））。如果我们从两边减去| XSf |，我们得到w（Rf（Y，Z）e\\Rf（Y′，Z′）≤ w（（Y，Z）e \\（Y′，Z′），所以rf实际上是一个w-收缩。我们将研究（2（X，X），e∪ ,E∩ ) 格子木架我们可以把它想象成一个网络，每个合同（两份半合同）实际上包含两份（不相关的）副本，一份给买方，一份给卖方。现在，企业的Cfchoice功能是在不相交的一组合同上定义的，因此 （X，X）我们可以定义C（Y）=Sf∈FCf（Yf）。类似地，R（Y）=Sf∈FRf（Yf）。

在整个网络上，我们称之为集合函数R:2（X，X）→ 2（X，X）w-收缩，如果对应的RFF是w-收缩。让我们用XSF=Sf表示起始半份合同（卖方方）的集合∈FXSf，以及XBF=Sf的终止一半合同（买方方）∈FXBf。现在| XSF |=|XBF |=|X |。让我来 XBFand Z XSF。（Y，Z）的对偶就是我们通过切换这两个部分得到的。我们用（Y，Z）表示它*= （Z，Y）。在这个模型中，让XSF中的所有合约都具有权重w=-XBF中的所有合同的重量w=1。引理B.3。如果F:2（X，X）→ 2（X，X）是-等收缩和w收缩形成（2（X，X），e）的非空子晶格∪,E∩).莱玛的证据。3.根据定理B.1，固定点集是非空的。现在让我们（X，X）和V （X，X）。假设F（U）=U和F（V）=V。通过单调性∩ V=F（U）e∩ F（V） F（Ue）∩ V）和∪ V=F（U）e∪ F（V） F（Ue）∩ V）。从W收缩性质和LemmaB。1.我们有∩ V)≥ F（e）U\\w∩ V)≥ w（Ue\\（Ue）∩ V），w（（Ue）∪ V）e\\U）≥ w（F（Ue）∪ V）e\\F（U））≥ w（（Ue）∪ V）e\\U），因此必须始终保持平等。使用LemmaB的第三部分。1.我们可以看到（Ue）∩ V）=F（Ue∩ V）和（Ue）∪ V）=F（Ue∪ V）因此它们也是F的固定点。观察B.2。考虑两组契约（Y，Z）和（Y′，Z′），其中Y，Y′ XBFand Z，Z′ XSFand（X，X）\\（Y，Z）=（X\\Y，X\\Z）。If（Y′，Z′） （Y，Z），然后（（X\\Y，X\\Z）*e \\（X\\Y′，X\\Z′）*) = （（X\\Z）\\（X\\Z′，（X\\Y′）\\（X\\Y））=（（Z′\\Z），（Y\\Y′）=（（X，X）\\（（Y，Z）e\\（Y′，Z′）*.定理B.3（子格定理）。假设选择函数满足完全可替换性和LAD/LAS。然后Φ（Y，Z）=（X\\RS（Z | Y），X\\RB（Y | Z））的固定点形成（2X×2X，e）的非空完整子格∪,E∩).理论证明。3.Φ（Y，Z）=（X\\RS（Z | Y），X\\RB（Y | Z））函数也可以写成Φ（Y）=（（X，X）\\R（Y，Z））*.

因为R是-等通，Φ也是-等渗酮。我们需要证明Φ是一个w收缩。假设（Y′，Z′） （Y，Z）。使用ObservationB。2，w（Φ（Y，Z）e \\Φ（Y′，Z′）=w（（X，X）\\R（Y，Z））*e\\（（X，X）\\R（Y′，Z′）*) = w（（X，X）\\（R（Y，Z）e\\R（Y′，Z′））*) = w（R（Y，Z）e\\R（Y′，Z′）≤ w（（Y，Z）e \\（Y′，Z′）因为在LemmaB中。2我们证明了R是w收缩。既然是-异丙酮和一个w收缩，LemmaB。3给出Φ的固定点形成（2（X，X），e）的子格∪,E∩).B.2.2终端代理的晶格以下路径独立条件由Aizerman和Malishevski（1981）引入。Echenique和Yenmez（2015年）在多对一匹配市场以及Fleiner（2003年）和Chambers和Yenmez（2017年）在多对多匹配市场进行了深入探索。引理B.4。（路径独立性）如果选择函数Cf:2X→ 2x是同一侧可替代且满足IRC，然后是Cf（Y∪ Z） =Cf（Y）∪ Cf（Z））Y，Z的何尔德 X.LemmaB的证明。4.由于Cf是同一侧可替代的，Cf（Y∪ Z） （Y）∪ Cf（Z））。用RC我们得到了Cf（Y）∪ Z） （Y）∪ Cf（Z）） （Y）∪ Z） 意味着Cf（Y∪ Z） =Cf（Y）∪Cf（Z））。引理B.5。假设选择函数满足完全可替换性和IRC。终端优势是终端跟踪稳定结果的偏序。莱玛的证据。5.我们需要证明这一点是反射的、反对称的和传递的。假设A、A′和A′是可接受的结果。As Cf（Af）∪ Af）=Cf（Af）=afholds对于每个代理（因此对于每个终端卖方）f，r她活得很好。如果萨伊当我们有Af=Cf（Af∪ A′f）=A′f适用于任何终端代理f，因此A=A′和Sis反对称。对于及物性，假设萨伊SA′\'。使用这个和LemmaB。4.我们得到任何终端代理f thatCf（Af∪A′f）=Cf（Cf（Af∪A′f）∪A′f）=Cf（Af∪A\'f∪A′f）=Cf（Af∪Cf（A′f）∪A′f））=Cf（Af∪A′f）=Af，因此A“萨”的确成立。

这就完成了证明。定理B.4（终端子格定理）。如果L是（2X×2X，e）的非空完备子格∪,E∩) 然后LT={（YT，ZT）：（Y，Z）∈ 五十} 是（2T×2T，e）的子晶格∪,E∩).理论证明。4.对于给定的（AT，BT），在原始晶格中可以有多个逆像。让（A）*, B*) =eS{（Y，Z）∈ L:（YT，ZT） （英国电信，AT）}。因为L是一个具有格运算的完全格∪ 安第斯山脉∩, 这意味着（A）*, B*) ∈ L和（A）*T、 B*T） =（英国电信，AT）。我们称之为（AT，BT）的标准逆像，因为这是-在allinverse图像中最伟大的。如果（AT，BT）和（CT，DT）∈ 让我们考虑一下（Y，Z）=（A*, B*)E∩ （C）*, D*). 自（Y，Z） （A）*, B*) 这意味着（YT，ZT） （A）*T、 B*T） =（英国电信，AT）。类似地（YT，ZT）（CT，DT）。我们想证明（YT，ZT）是LT中（AT，BT）和（CT，DT）的最大下界*, Z*)  （A）*, B*) 和（Y）*, Z*)  （C）*, D*) 因为*, B*) 定义为更大集合的联合。因此（Y）*, Z*) = （Y，Z）。假设存在一个（ET，FT）∈ 使（ET，FT） （英国电信公司AT）和（英国东部航空公司FT）（CT，DT）但（ET，FT）6 （YT，ZT）。然后在原始晶格中（E*, F*)  （A）*, B*) 和（E）*, F*)  （C）*, D*) 但是（E）*, F*) 6. （Y）*, Z*). 但这是不可能的，因为（Y，Z）=（A*, B*)E∩ （C）*, D*).所以我们找到了（AT，BT）和（CT，DT）的一个唯一的最大公共下界。为了找到（AT，BT）和（CT，DT）的最低共同上界，可以进行类似的论证。设（Y，Z）=（A）*, B*)E∪ （C）*, D*). 自（Y，Z） （A）*, B*) 这意味着（YT，ZT） （A）*T、 B*T） =（英国电信，AT）。类似地（YT，ZT） （CT，DT）。假设存在一个（ET，FT）∈ 使（ET，FT） （英国电信公司AT）和（英国东部航空公司FT）（CT，DT）但是（ET，FT）6 （YT，ZT）。

然后在原始晶格中（E*, F*)  （A）*, B*) 和（E）*, F*)  （C）*, D*) 因此（E*, F*)  （Y，Z），so（E）*T、 F*T） =（东部，英尺） （YT，ZT），这是一个矛盾。所以我们找到了（AT，BT）和（CT，DT），So（LT，e）的唯一最低共同上界∪,E∩) 它确实是一个格子。现在我们只考虑码头卖方出售的合同。对任何人来说 十、 letYS={X∈ Y | s（x）∈ T}。给定两个轨迹稳定的输出A和A′，让我们表示A与˙XBand˙XS的正则轨迹稳定对（定义见定理1的证明末尾），以及A与˙X′带˙X′S的正则轨迹稳定对。引理B.6（终端优势引理）。给定两个轨迹稳定的输出A和A′，Cf（Af∪ A′f）=当且仅当˙XSS˙X′SSand˙XBS˙X′BSholds。类似的声明适用于终端买家。莱玛的证据。6.如果f是终端卖家，Cf（˙XS）=af和Cf（˙X′S）=a′f。假设˙XSS˙X′SS。由美国空军IRC报道 Af∪ A\'f˙xsf表示Cf（Af∪ A′f）=Af。对于相反方向，取一个合同x∈ 这样x/∈ Cf（A′f）∪ x） 。我们用的是Lemmab。5、A萨伊Sx，因此ASx，所以x/∈ Cf（Af∪ {x} ）。当我们定义A和A′的稳定对时，如果x∈ Cf（A′f）∪ {x} ）然后是x∈˙XB，如果x/∈ Cf（A′f）∪ {x} ）然后∈˙XS。从前面的观察中我们可以看到˙XSS˙X′SSand˙XBS˙X′BS。码头买家的首选是安娜·罗格斯。命题2的证明。在定理1的证明中，我们已经看到，格L上的等通映射Φ的任何固定点（˙XB，˙XS）都决定了跟踪稳定的结果AX。此外，每个稳定结果A至少对应于Φ的一个固定点（˙XB，˙XS）。从理论上来说。1，Φ的固定点形成晶格，因此存在-最小固定点（˙YB，˙YS）a和a-最大值（˙ZB，˙ZS）。我们表明，所有稳定的结果都是卖方最优，而AZis买方最优。所以假设A轴是一个稳定的结果。

As（˙YB，˙YS） （˙XB，˙XS） （˙ZB，˙ZS），我们有˙YB˙XB˙ZBand˙YS˙XS˙ZS。莱玛。6表示Cf（Af∪ AYf）=AYfand Cf（Af∪ AZf）=对于任何终端卖方f和CG（Ag∪ AYg）=Agand Cg（Ag∪ AZg）=AZg对于任何终端买方，g.因此，定义为优于AYA的卖方和优于A.主张3的卖方。在定理1的证明中，我们已经看到A是踪迹稳定的当且仅当存在正则踪迹稳定对（˙XB，˙XS），使得（˙XB，˙XS）是Sotone映射Φ和A=˙XB的固定点∩˙XS。此外，如果选择函数满足LAD/LAS，则Φ的固定点形成（2X×2X，e）的子格L∪,E∩) 根据EMB。3.从教统局。4.上述点阵到终端的投影，也是 来自莱玛。6.这种偏序与因此，小径稳定的结果在终端优势下形成了一个格子。B.3命题4和命题4的证明。逐字逐句地遵循Hat Field和Kominers（2012）中定理8的证明，仅将“稳定”替换为“轨迹稳定”。命题5的证明。遵循Hat Field和Kojima（2009）中定理1的证明（Hat Field和Kominers（2012）指出了供应链中的稳定结果）。B.4命题6和命题7的证明我们的证明遵循Ostrovsky（2008）。首先，我们调查A的重新稳定结果，我们在命题6和命题7的证明中都扮演了角色。假设A是原始网络中的任意跟踪稳定结果，具有相应的正则跟踪稳定对（˙XB，˙XS）。在新的终端卖方f′到达后，让X成为新网络中所有合同的集合，让我们定义（X）*B、 X*S） =（˙XB，˙XS）∪ Xf′）。

在下文中，我们将根据新网络上的选择函数使用Φ，因此（˙XB，˙XS）不再需要是Φ的固定点。自Xf′以来∩十、*B=, 对于每一个f 6=f′，RfS（X*S | X*B） =RfS（˙XSXB）和RfB（X）*B | X*S） =RfB（˙XBXS）。例如，如果f有一个带有f′的contracts，那么x=f′f不适用于x中的f*Bso它不会被弹出。对于f′，Rf′S（X*S | X*B） =Xf′\\Cf′S（Xf′）和Rf′B（X*B | X*S） =.因此Φ（X）*B、 X*S） =（˙XB）∪ Cf′（Xf′），˙XS∪ Xf′）。所以（X）*B、 X*（S） Φ（X）*B、 X*S） ，Φ是-isotone，soΦ（X）*B、 X*（S） Φ（Φ（X）*B、 X*S） ）等等。所有可能的子集对的晶格都是有限的，因此存在一个k，使得Φk（X*B、 X*S） =（^XB，^XS）是一个固定点。所以（X）*B、 X*（S） Φ（X）*B、 X*（S） Φk（X）*B、 X*S） =（^XB，^XS）。结果^A=^XB∩^XSis trail stable，这就是我们从A.命题证明中所说的稳定。如果f′是终端卖家，我们从结果Amax和最大对（˙ZB，˙ZS）。使用前面的方法，结果^A=^ZB∩^zs是来自A的restabilizedoutcome。在新网络中存在-Φ的最大固定点，即（Z′B，Z′S），因此（˙ZB，˙ZS∪ Xf′）=（Z*B、 Z*（S） （^ZB，^ZS） （Z′B，Z′S）。对应于最大固定点的轨迹稳定结果为A′max=Z′B∩ Z’S.我们必须证明，与最初的Amax相比，A’Maxs对终端买家更好，对终端卖家更糟。如果f是终端买家，因为（Z′B，Z′S）是Φ的固定点，并且（˙ZB，˙ZS）在新代理到达之前是固定的，所以Cf（Z′B）=a′f，max和Cf（Z*B） =Af，maxandz*B Z′Bso fromCf（Z′B） （Af，max）∪ A\'f，max） Z′bb通过IRC我们得到Cf（Af，max）∪ A′f，max）=A′f，maxsoA′f，maxis是终端买家的首选。类似地，如果f是f′之外的终端卖方，Cf（Z′S）=a′f，max和Cf（Z*S） =Af，max和Z\'S Z*来自Cf（Z）的Sso*（S） （Af，max）∪ A\'f，max） Z*通过IRC，我们获得Cf（Af，max∪A′f，max）=Af，maxso Af，maxis是终端买家的首选。

如果f’是终端买家，那么我们可以使用相同的证据来颠倒买家和卖家的角色。命题7的证明。如果f′是终端卖方，a是原始网络中的任意跟踪稳定结果，具有正则跟踪稳定对（˙XB，˙XS），那么（X*B、 X*S） =（˙XB，˙XS）∪Xf′） （^XB，^XS）。重新稳定的结果是^A=^XB∩^XS，类似于建议的证明，我们可以证明，初始生产者对A的偏好较弱，而所有终端消费者（f′除外）对A的偏好都较弱。如果f′是终端买家，偏好就是建议。B.5命题1、9、10和11的证明下面的引理表明，如果一个局部阻塞路径多次与一个代理相交，但他不想选择局部阻塞路径中的每个契约，那么代理仍然会选择他的任何上游（下游）契约，以及他在局部阻塞路径中的另一个下游（上游）契约。引理B.7。假设选择函数满足完全可替换性和IRC。此外，考虑一组契约 以及代理f.1的一组合同{X，X，…，xk，z，z，…，zk}。假设Y是可接受的，x，x，xk∈ XBfand z，z，zk∈ xsf证明{xi，zi}是任何1的（Y，f）-必要对≤ 我≤ k、 但是{x，x，…，xk，z，z，…，zk}是不可接受的。那么{xi，zj}是某些i6=j.2的（Y，f）-必要对。现在让我们移动合同x。假设Y是可接受的，x，xk∈ XBfandz，z，zk∈ xsf证明zis（Y，f）－可接受，{xi，zi}是任何2的（Y，f）－必要对≤ 我≤ k、 但是{x，…，xk，z，z，…，zk}是不可接受的。那么{xi，zj}对于某些i6=j.3是（Y，f）-必要对。现在让我们删除合同X和zk。假设Y是可接受的，x，xk∈ XBfand z，z。

，zk-1.∈ xsf说明zand xkare（Y，f）-可接受，{xi，zi}是任何2个元素的（Y，f）本质对≤ 我≤ K- 但是{x，…，xk，z，z，…，zk-1} 是不可接受的。那么{xi，zj}6={xk，z}是某些i6=j的（Y，f）-必要对。LemmaB的证明。7.我们依次证明每个陈述。1.假设，例如，zj/∈ Cf（Y）∪ {x，x，…，xk，z，z，…，zk}）对于一些j.然后来自CSC，zj/∈ Cf（Y）∪ {xj，z，z，…，zk}）。但是xj∈ Cf（Y）∪ {xj，zj}）因为{xj，zj}根据假设是（Y，f）-必要的，所以从CSC我们必须有那个xj∈ Cf（Y）∪{xj，z，z，…，zk}）。因为{xj}不是（Y，f）-可接受的，所以必须有一个zl∈ Cf（Y）∪{xj，z，z，…，zk}），所以{xj，zl}对于某些l6=j.2是（Y，f）-可接受的。如果已经删除了xhas，那么假设z/∈ Cf（Y）∪{x，…，xk，z，z，…，zk}）。然后，通过CSC，我们必须拥有z/∈ Cf（Y）∪ {z，z，…，zk}）但如果{z}是（Y，f）-可接受的，但其他{zj}合同中没有一个是IRC和SSS可接受的，这就不能成立。因此，必须是xjor zj（对于2≤ J≤ k） 不是由Cf（Y）选择的吗∪ {x，…，xk，z，z，…，zk}）。按照上面第1部分的论证，必须有（Y，f）-基本对{xi，zj}.3。重复第二部分的论点。在证明命题1之前，我们先介绍一个有用的概念。定义B.1。一个非空的契约集Q是一个回路，如果它的元素s可以按某种顺序（x，…，xM）排列，使得b（xM）=s（xM+1）HOLDS代表所有m∈ {1，…，M- 1} andb（xM）=s（x），其中M=|Q |。命题的证明1。为了证明每一个稳定的结果都是跟踪稳定的，我们考虑一个不跟踪稳定的稳定结果a。选择一条本地阻塞的小路。如果Tf*Cf（A）为每一家参与T的公司∪ Tf），然后使用LemmaB。7.有尾流下游合同对xj∈ T和zl∈ 使得j6=l和{xj，zl}是（A，f）-可接受的。