分布式就业市场中的序列匹配对策的子对策完美均衡

ACM Transactions on Economics and Computation，卷。号74、第二十一条。出版日期：2020年1月序列匹配对策的子对策完美均衡Yasushi Kawase，东京工业大学和RIKEN AIP中心，日本Yutaro Yamaguchi，大坂大学和RIKEN AIP中心，日本YU YOKOI，日本国立信息学研究所我们研究了一个分散的匹配市场中，公司顺序提供给潜在的工人。对于每个提议，工人可以选择“接受”或“拒绝”，但决定是不可撤销的。接受一份工作保证了她在公司的工作，但这也可能使她失去将来从其他公司获得更好工作的机会。我们将这个市场描述为工人们的完全信息扩展型博弈。这个博弈的每个实例都有一个唯一的子博弈完美均衡（SPE），它不一定导致稳定的匹配，并具有一些令人困惑的性质。我们展示了一个二分法的结果，其特点是计算SPE的复杂性。如果每个公司向最多两个工人提供报价，或者每个工人从最多两个公司获得报价，则计算是容易的。相反，即使公司和工人都与最多三个报价有关，它也是PSPACE困难的。我们还研究这个匹配市场的工程方面。结果表明，对于任何偏好配置文件，我们可以设计一个公司的报价时间表，使工人最优的稳定匹配实现在SPE。CCS概念：·计算理论→平衡的精确和近似计算;算法-博弈论;博弈论中的解决方案概念;市场均衡;21附加关键词和短语：稳定匹配，子博弈完美均衡，PSPACE完备性ACM参考格式：Yasushi Kawase，Yutaro Yamaguchi，and Yu Yokoi.2020年。序贯匹配对策的子对策完美均衡 ACMTrans. 经济Comput. 7，4，第21条（2020年1月），30页。https://doi.org/10.1145/33737171介绍想象一个由公司和工人组成的分散的就业市场。每家公司都有一个职位需要填补，并且对潜在的工人有优先顺序。此外，每个工人都有自己的职位。为了填补一个职位，每个公司首先向它最喜欢的工人发出一个报价，如果报价被拒绝，那么下一个报价将被提供给第二个最好的工人，依此类推。也就是说，企业的行为就好像他们模拟了面向企业的延迟接受算法的一个非同步版本[23，24]，该算法已知会发现一个初步的版本[17]出现在EC这项工作得到了JSPS KAKENHI Grants No.JP16H06931，编号JP16K16005和No.JP18K18004、JST ACT-I Grant No.JPMJPR17U7和JST CREST Grant No.JPMJCR14D2.作者地址：Y。Kawase，东京工业大学和RIKEN AIP中心，2-12-1 Ookayama，Meguro-ku，Tokyo，152-8552，Japan;电子邮件：kawase.y. m.titech.ac.jp; Y.山口，大坂大学和RIKEN AIP中心，1-5 Yamadaoka，Suita，大坂，565-0871 ， 日 本 ; 电 子 邮 件 ： yutaro_yamaguchi@ist.osakau.ac.jp; Y 。 Yokoi ， 国 立 信 息 学 研 究 所 ， 2-1-2Hitotsubashi，Chiyoda-ku，Tokyo，101-8430，Japan;电子邮件：yokoi@nii.ac.jp。允许免费制作本作品的全部或部分的数字或硬拷贝，以供个人或课堂使用，前提是制作或分发副本的目的不是为了盈利或商业利益，并且副本的第一页上有本声明和完整的引用。本作品的版权归ACM以外的其他人所有，必须予以尊重。允许使用学分进行摘要。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定许可和/或付费。从permissions@acm.org请求权限。© 2020计算机协会。2167-8375/2020/01-ART21 $15.00https://doi.org/10.1145/3373717ACM Transactions on Economics and Computation，卷。号74、第二十一条。出版日期：2020年1月第二十一Y. Kawase等人位置最优稳定匹配就像原始同步版本[11]。在这些算法中，每个工人都可以保留一份临时合同，并在得到更好的报价时拒绝它，与此相反，当前的市场不允许临时合同。一旦工人收到某个公司的录用通知，她必须立即决定是否接受，以后不能改变决定。因此，接受一份工作保证了她在那个职位上的工作，但也可能消除了将来从其他公司获得更好工作的机会。假设要约是根据规定的时间表作出的，即，在所有可能的报价的集合上存在线性顺序。所有的工人都知道这个顺序，但是一个工人是否会得到每个公司的预定报价取决于其他工人的行动。因此，这个市场具有战略工作者所遇到的决策问题的序列结构。我们的模型处理与每个公司的偏好一致的任何报价顺序。特别是，如果同一公司的所有报价都相继放入订单中，即，在公司集合上存在线性顺序，每个公司根据该线性顺序做出其所有报价。例如，这个案例代表了一个学术就业市场，在这个市场中，不同的职位有不同的招聘季节。求职者知道这些季节，他们可以猜测每个职位一旦研究人员接受了一份工作，她就不能拒绝，因为单方面解除合同会损害她的声誉，并对她未来的职业生涯产生不利影响。基于职位的案例也可以被解释为一个就业市场，在这个市场中，研究机构在不同的季节都有公开的邀请，研究人员战略性地决定是否申请每一个邀请。我们将这个市场表述为工人之间的完全信息扩展形式博弈，我们称之为序贯匹配博弈（正式定义将在2.1节给出）。游戏的每一轮都对应于一家公司的报价报价是按照一定的顺序进行的在每一轮中，收到offer的工人是采取行动的玩家，可能的行动是接受和拒绝。如果工人选择接受，那么公司和工人就匹配并离开市场，我们进入一个子博弈，在这个子博弈中，他们被移除。如果工人选择居留，那么他们就留在市场上，我们进入一个子博弈，在这个子博弈中，工人从公司的偏好列表中被淘汰。如果没有非空列表的公司，游戏结束。每个策略配置文件唯一地定义了一个匹配，或在游戏结束时获得的分配。每个工人本文研究了这种序贯匹配博弈的子博弈完美均衡，即，- 动作简档，其表示在所有其他工作者将在未来采取其最佳动作的假设下的所有回合中的工作者的最佳动作对于每一份工作，不同的行动会给工人带来不同的结果：拒绝一份工作，她以后就不可能得到同样的工作。因此，最佳行动在每一轮由逆向归纳唯一定义。因此，序列匹配博弈的任何实例都有唯一的SPE。为了澄清设置，我们在这里提供一个小例子。实施例1.1. 有三个研究所，P1，P2和P3，每个研究所都有一个职位需要填补。三个求职的研究员，q1，q2和q3，正在等待录用。研究所对可接受的候选人有优先权，研究人员对可能的研究所有优先权，如下所示：p1：q1q1：p2×q1p1p2：q2×p2q1×p2q3q2：p3×q2p2p3：q3×p3q2q3：p2×q3p3。每个研究人员都喜欢被匹配（与一个可接受的研究所），而不是不匹配。研究所p1首先开始侦察，然后p2和p3依次跟进因此，以下顺序是序列匹配对策的子对策完美均衡第二十一ACM Transactions on Economics and Computation，卷。号74、第二十一条。出版日期：2020年1月----图1.一、游戏的树表示红色粗边表示SPE。定义在报价上。发售顺序：（p1，q1），（p2，q2），（p2，q1），（p2，q3），（p3，q3），（p3，q2），其中跳过与先前匹配的机构或研究人员相关的报价当第一个出价（p1，q1）被提出时，q1有两个可能的动作。如果她选择了ACCEPT，那么她在结果匹配中被分配到p1如果她选择RESTATE，那么她必须预测拒绝后会发生什么（见图1）。在q1然后，p2向q2发出要约，q2可以选择接受或拒绝.假设所有工人都通过预测其他工人的未来行动来采取最佳行动，可以得出结论，如果她拒绝（p1，q1），q1将在结果中是不匹配的因此，接受是她在第一轮中最好的动作通过这种方式，我们可以为每一轮定义最佳操作图1显示了所有可能的回合，红色边缘表示最佳动作。然后，这个实例的SPE产生匹配对（p1，q1），（p2，q3），（p3，q2）的赋值。注意，这与在该偏好简档下的唯一稳定匹配（p1，q1）、（p2，q2）、（p3，q3）不一致最近，在各种设置下积极研究了匹配实例上的序列博弈[3在许多这些设置中，已经表明SPE导致稳定的匹配。然而，SPE的这种特征在我们的环境中并不成立实际上，上述示例的结果匹配是不稳定的。此外，我们将在2.3节中看到，我们设置中的结果匹配不仅可能违反标准稳定性，而且可能违反较弱的稳定性，如vNM稳定性[10]和本质稳定性[19]。此外，与许多其他模型不同，SPE的结果匹配根据我们模型中的报价顺序而发生巨大变化。我们在2.3节中还看到，不仅匹配本身，而且匹配的企业和工人的集合也可能发生变化，即，不存在这些独特的功能表明在我们的模型中捕获SPE的困难本文从公平计算和间接市场调节两个不同的角度研究了序贯匹配博弈的SPE在第一部分（第3节和第4节）中，我们揭示了计算给定偏好配置文件和给定发行顺序的SPE结果匹配的复杂性。也就是说，我们分析了假设所有工人都遵循他们的最佳策略，预测市场结果有多难。在第二部分（第5和第6节），我们看到我们的第二十一Y. Kawase等人ACM Transactions on Economics and Computation，卷。号74、第二十一条。出版日期：2020年1月∞∞∞∞≤≤∞∞∞∞∞∞从工程角度看。对于给定的偏好配置文件，我们考虑设计一个提供顺序，以便SPE的结果匹配允许某种社会期望的属性，例如，稳定在这里，我们描述每个部分的细节。1.1平衡计算在第一部分中，我们考虑在我们的模型中计算SPE的复杂性请注意，表示SPE本身显然需要指数级时间，因为树表示具有指数级大小。因此，考虑以下决策问题更合理：给定一个实例和一个历史（一个可能的动作序列），决定下一个参与者是否在SPE中选择ACCEPT请注意，给定实例的每个子博弈也是序列匹配博弈的实例那么，我们更愿意考虑下面的等价问题。程序1.2（SPEM）。 给定一个顺序匹配博弈的实例，决定第一个被提供的worker是否在SPE中选择ACCEPT。我们把这个决策问题称为SPEM。请注意，SPE的结果匹配，我们称之为SPE匹配，可以通过重复求解SPEM来获得。相反，如果我们可以计算SPE匹配，则SPEM被解决。我们分类子类的SPEM的公司和工人的偏好列表对于正整数s和t，问题（s，t）-SPEM是SPEM的限制，其中每个公司的偏好列表和每个工人的偏好列表最多分别有s和t个条目此外，（s，t）-SPEM和（s，t）-SPEM表示只有一侧对列表长度有限制的限制我们提供了以下二分法定理，它完全描述了所有s和t的（s，t）-SPEM的计算复杂性。1.3. 如果s 2或t2，则（s，t）-SPEM问题可以在多项式时间内求解.否则，它是PSPACE完备的。对于上述定理，我们在第三节中证明了（2，）-SPEM和（，2）-SPEM的易处理性，在第四节中证明了（3，3）-SPEM的PSPACE-完全性。我们将首先通过提供一个计算SPE匹配的有效算法来证明（2，）-SPEM和（，2）-SPEM都在复杂性类P中。正如我们在上面的例子中所观察到的，（，2）-SPEM实例的SPE匹配不一定是稳定的。然而，不幸的是，当然，我们可以通过基于延迟接受算法的算法来计算它，我们称之为顺序固定延迟接受算法（SFDA）。该算法反复计算工作者最优稳定匹配，并确定在提供顺序中首先出现的匹配对。SFDA的正确性意味着，当一个工人收到某个公司的报价时，当且仅当她被分配到“当前”子博弈的工人最优稳定匹配中的公司时，她的最佳行动是接受，SFDA还为（2，）-SPEM工作，即，它输出SPE匹配。此外，我们可以证明，对于（2，）-SPEM，SFDA的输出符合工人最佳的稳定匹配独立的提供订单。因此，对于（2，）-SPEM，SPE匹配恰好是工作者最优的稳定匹配。与上述易于处理的情况相反，问题（3，3）-SPEM远不容易处理。事实上，我们证明了它是PSPACE困难的，这意味着除非P= PSPACE，否则不存在多项式时间算法来求解它。我们的证明是基于减少量化3SAT，这是一个PSPACE完全的问题。即使每个偏好列表的长度最多为3，顺序匹配游戏也有一个混乱的结构，这使我们能够构建模拟逻辑门（如NOT，OR和AND）的小工具。序列匹配对策的子对策完美均衡第二十一ACM Transactions on Economics and Computation，卷。号74、第二十一条。出版日期：2020年1月1.2社会合意匹配的序设计如上所述，一般来说，我们模型中的SPE匹配可能远非稳定。此外，SPE匹配没有达到社会福利的其他标准，如帕累托效率和第一选择最大化。然而，正如我们将在例2.5（第2.1节）中展示的那样，SPE匹配可能会根据报价订单而有所不同。这些事实引起了以下问题。“我们能否通过设计一个适当的发行时间表，将市场引导到社会理想的状态？”这是第二部分所探讨的问题。让我们把自己放在一个中央权威的位置上，通过规范公司的发行时间表来部分控制市场。假设我们不能规范但我们可以得出他们的真实偏好。我们首先观察企业和工人的偏好，然后设计一个提供时间表，即，发行顺序，应与每家公司市场过程在由观察到的偏好配置文件和设计的发行顺序组成的实例上进行。我们的目的是设计一个发售顺序，以便在SPE中获得理想的匹配，即，我们的目标是建立市场，使工人具体来说，我们将关注以下标准：稳定性，帕累托效率和首选最大化。可以说，稳定性是双边匹配市场中最重要的标准，它代表了对所有企业和工人的一种公平。一个稳定的匹配被称为工人最优（或企业最优），如果它是工人（或企业）最喜欢的所有稳定匹配。工人方面的帕累托效率也是一个很好的讨论标准时，把重点放在工人在一些应用中，工人方的第一选择最大化吸引了大量的兴趣，这个标准要求分配给他们的第一选择的工人数量最大化[8]。对称地定义了厂商的帕累托效率和厂商的第一选择最大化。不幸的是，在第6节中，我们发现这些标准中的大多数在SPE中通常无法实现。对于除工人最优稳定性之外的每一个，我们可以提供一个偏好配置文件，使得没有提供顺序产生满足所需属性的SPE匹配。这些不可能的结果意味着通过间接调节来控制工人的行为是困难的，即，设计公司然而，令人惊讶的是，我们发现，工人的最佳稳定匹配可以实现在SPE的任何偏好配置文件。下面的定理在第5节中给出。1.4. 给定一个偏好配置文件，可以构建一个报价顺序，使得SPE匹配是工人最佳的稳定匹配。我们证明了这个定理，给出了一个有效的算法来构造一个所需的提供订单的声明，这是两个阶段，直观地如下。我们首先让企业提供给所有工人更可取的，他们的合作伙伴在工人最优的稳定匹配。其余的offer是基于职位的，这是根据在面向工作者的延迟接受算法中被匹配的顺序定义的值得注意的是，定理1.4对偏好列表的长度没有任何假设。这个积极的结果在一定程度上弥补了第一部分中强烈的消极结果。虽然SPE匹配很难计算，并具有复杂的属性，一般来说，一个法规的公司的提供时间表可以导致他们是稳定的任何偏好。1.3相关工作在正规形式博弈中寻找纳什均衡的复杂性已经在算法博弈论的背景下得到了很好的研究[25]。然而，很少有工作已经做了一个子博弈完美均衡的扩展形式的游戏。已知计算SPE是PSPACE完备的，第二十一Y. Kawase等人ACM Transactions on Economics and Computation，卷。号74、第二十一条。出版日期：2020年1月×>×∈∈∪∈∈关于我们×∈ ∪ ∈∪在联系我们||} →>∈×∈{||}×→> × ×∈∈联系我们|}{∈|}∈ ∪ ××}{∈|∈}∈∈∈{∈|∈⊆ ×∈不相关机器调度的顺序版本，拥塞博弈[21]和成本分摊博弈[6]。在经济学的背景下，分散匹配市场产生的结果在各种条件下进行了研究[3大多数现有的研究都分析了分散的市场何时会产生稳定的匹配。Haeringer和Wooders [15]考虑了与我们类似的设置：在每个阶段，每个公司向工人提供一个职位，然后每个工人都可以选择是否接受其中一个职位或拒绝所有职位。粗略地说，他们的游戏基于延迟接受算法的同步版本，而我们的游戏基于异步版本。他们声称，当工人在每个阶段顺序决定他们的行动时，每个SPE都会导致工人最优的稳定匹配[15，定理2]，但这一说法在本研究中已被证明不正确（详见备注2.6）。2预赛2.1模型在本节中，我们给出了序列匹配博弈的形式定义。该游戏是由一个连续的过程中的接受/拒绝提供一个匹配的实例，并制定为一个完美的信息扩展形式的游戏。匹配实例是元组I=（P，Q，E，），其中每个分量定义如下。存在有限的一组公司P=p1，.，pn和工作者的有限集合Q=q1，..，qm.每个公司都有一个头寸，我们经常用它的头寸来识别每个公司。可接受对的集合由E P Q表示。对于e=（p，q）E，我们定义<$P（e）：=p和<$Q（e）：=q。对于每个企业p P和每个工人q Q，可接受的合作伙伴集合表示为ΓI（p）：=qJQ（p，qJ）E和byI（q）：=PJP（PJ，q） E，r是pectivel y. 包含pP的可接受对的集合和q Q分别表示为δI（p）：=e E<$P（e）=p和δI（q）：=e E<$Q（e）=q。很好每个r P Q对ΓI（r）有严格的序偏好r，表示（r）rPQ。我们有时写（p，q）p（p，qJ）表示qpqJ对于pP.A映射μ：PQPQ被称为I=（P，Q，E， ）if μ（r）ΓI（r）r和μ（μ（r））=r，对于每个r PQ.公司或工人rP如果μ（r）≠ r，则称Q与μ（r）匹配，如果μ（r）=r，则称Q不匹配。对于每个r P Q和两个匹配μ1和μ2，如果μ1（r）rμ2（r），我们写μ1rμ2，其中我们假设r虚拟地加到偏好r相对于ΓI（r）的底部（即，每个R优选与可接受的伙伴匹配而不是不匹配）。I中的匹配μ通常与相应的可接受对集合相识别{（p，μ（p））|p ∈ P，μ（p）<$p}={（μ（q），q）|q ∈ Q，μ（q）<$q}. 设MI表示所有匹配的集合序贯匹配博弈1由一对匹配实例I=（P，Q，E，）和E上的提供顺序σ定义，它是从1，.，E到E。我们假设σ与（p）pP一致，即，如果σ（i），σ（j） δI（p）和σ（i）pσ（j）则i − − ×\∈−––元素e被添加到集合μ中联系我们并且分别从集合μ中移除。定义2.1（删除）。 设e ∈ E是匹配实例I =（P，Q，E，×）中的可接受对。从I中删除e被定义为I−e：=（P，Q，E−e，×J），其中×rJ是相对于ΓI−e（r）的偏好，对于每个r∈P<$Q，它与×r一致，即，s×rJt当且仅当对每个s，t∈ΓI−e（r）有s×rt。对于E上的一个阶σ，从σ中删除e是E−e上的一个与σ相容的阶σ−e，即，（σ−e）−1（e1）（σ−e）−1（e2）当且仅当对每个e1，e2∈E−e，σ−1（e1）σ−1（e2）。定义2.2（收缩）。 设e =（p，q）E是匹配实例I=（P，Q，E，）中的可接受对。I被e压缩定义为I/e：=（Pp，Qq，E/e，J），其中E/e：=E（δI（p）δI（q）），且rJ是与以下一致的rI/e（r）的概率：r对于每个r（Pp）（Qq）。对于σ在E上的阶，σ被e压缩是σ/e在E/e上的阶，即与σ一致。OB sERVATI on 2.3. 删除和收缩是可交换的。也就是说，对于任何两个不相交的对，e1，e2∈E，有ve（I/e1）−e2=（I−e2）/e1和d（σ/e1）−e2=（σ−e2）/e1.Lete=（p，q）∈E. 对于I/e中的匹配μJ，我们不通过yμJ+e来确定I中的匹配μ，使得μ（p）=q，μ（q）=p，并且对于每个r∈（P-p）<$（Q-q），μ（r）=μJ（r）。相反，对于I中的匹配μ，其中μ（p）=q且μ（q）=p，我们不通过I / e中的匹配μJ使得对于每个r ∈（P-p）<$（Q-jq），μ j（r）= μ（r）。注意，这些可以被视为普通的集合操作：博弈（I，σ）递归定义如下。设σ（1）=e=（p，q）.在第一轮中，p向q出价，q选择接受或拒绝。如果q选择ACCEPT，则p和q被直接匹配，并且当（I/e，σ/e）被规划时（即，例如，对于I / e中的任意项，结果是μJ+e）。如果q选择RESTAL，则p和q不匹配，并且此时（Ie，σe）被播放（即，结果是I e）中的某种匹配正如我们在图1中看到的，过程可以用一个有根树来表示，其中根对应于博弈的第一轮（I，σ），每个节点（除了叶子）对应于一个博弈（I J，σ J），并且有两个子博弈对应于两个子博弈（I J/σJ（1），σ J/σ J（1））和（I Jσ J（1），σ Jσ J（1））。我们称这棵树为博弈（I，σ）的树表示。考虑了序列匹配博弈的子博弈完美均衡。一个策略剖面是一个子博弈完美均衡，如果它是原博弈的每个子博弈的纳什均衡在游戏的每一轮中，接受和拒绝两个动作（p，q）会导致不同的结果匹配，比如μ1和μ2。工人q更喜欢其中一个，因为μ1（q）=p<$μ2（q）。因此，最优策略是唯一的定义在每个子博弈的逆向归纳法，每个游戏承认一个唯一的SPE。根据博弈（I，σ）的SPE进行的结果匹配称为（I，σ）的SPE匹配，记为SPE（I，σ）。下一个属性紧接着上面的定义。我在2.4上写对 任 意 序 列 匹 配 对 策 （ I ， σ ） 中 的e =（p，q）= σ（1），我们有如下性质.(a) 如果SPE（I − e，σ − e）（q）×qp，则SPE（I，σ）= SPE（I − e，σ − e）。(b) 若SP E（I−e，σ−e）（q）<$qp，则SP E（I，σ）=SP E（I/e，σ/e）+（p，q）.实施例2.5. 让我们将例1.1表述为一个序列匹配博弈（I，σ），其中I=（P，Q，E，）。公司集合是P=p1，p2，p3，工人集合是Q=q1，q2，q3.可接受对的集合是E={（p1，q1），（p2，q1），（p2，q2），（p2，q3），（p3，q2），（p3，q3）}，第二十一Y. Kawase等人ACM Transactions on Economics and Computation，卷。号74、第二十一条。出版日期：2020年1月联系我们图二、 （I，σ J）的树表示。红色粗边表示SPE。且偏好（×r）r∈P<$Q为p1：q1q1：p2×q1p1p2：q2×p2q1×p2q3q2：p3×q2p2p3：q3×p3q2q3：p2×q3p3。提供顺序σ∈<$I为（σ（1），σ（2），.，σ（6））=（（p1，q1），（p2，q2），（p2，q1），（p2，q3），（p3，q3），（p3，q2））.我们还可以看到，σ是由位置顺序π：1，2，3P诱导的，使得（π（1），π（2），π（3））=（p1，p2，p3）。如例1.1所示（参见图1中的树表示），SPE匹配是SPE（I，σ）={（p1，q1），（p2，q3），（p3，q2）}.让我们演示一下，即使匹配实例完全相同，不同的报价顺序也可能导致不同的SPE匹配考虑上面的例子I，设σJ∈I为（σJ（1），σJ（2），.，σJ（6））=（（p2，q2），（p2，q1），（p2，q3），（p3，q3），（p3，q2），（p1，q1））.注意，这个σJ也是基于位置的（由位置顺序πJ诱导，其中（πJ（1），πJ（2），πJ（3））=（p2，p3，p1））。（I，σJ）的树表示如图2所示，SPE匹配为SPE（I，σJ）={（p1，q1），（p2，q2），（p3，q3）}.正如定义中所提到的，对于任何顺序匹配博弈，可以通过逆向归纳算法计算唯一的SPE然而，计算时间是输入大小的指数，因为树表示具有指数大小。在这篇文章中，我们考虑了在第一轮中决定是否选择ACCEPT我们把这个问题称为SPEM，如问题1.2中所定义的。SPEM的限制，其中每个公司和每个工人的可接受的合作伙伴的数量分别最多为s和t，表示为（s，t）-SPEM。备注2.6. 在文献[15]中，考虑了类似的序贯匹配对策，并且他们的模型与我们的模型之间存在一些差异。参考文献[15，第4节]研究了最相似的设置，其中唯一的区别是，在所有公序列匹配对策的子对策完美均衡第二十一ACM Transactions on Economics and Computation，卷。号74、第二十一条。出版日期：2020年1月司都提供了报价之后（其中每个公司第二十一Y. Kawase等人ACM Transactions on Economics and Computation，卷。号74、第二十一条。出版日期：2020年1月≥--∈∪≥M| |×∈> ∈M> ×∈∈M∈∈M≥ ≥ <$∈×公司提供给它从未提供给的工人中最喜欢的工人），工人以预先指定的顺序依次选择他们的行动（要么接受一个提议并拒绝其余提议，要么拒绝所有提议）。例如，让我们考虑例2.5中的匹配实例I。在第一阶段，每个公司pi向qi（i=1，2，3）出价。假设第一个决策者是q1。如果q1拒绝p1在这种情况下，q1将是不匹配的（没有其他公司会向q1出价），因此q1应该得出结论接受p1然后，q2和q3可以分别拒绝p2和p3的报价，随后在第二阶段中，它们分别收到来自p3和p2的报价，这两个公司分别是它们的首选公司。因此，这个博弈的SPE产生匹配（p1，q1），（p2，q3），（p3，q2），这与例2.5中的SPE（I，σ）相同。在参考文献[15，定理2]中，声称这样的博弈享有唯一的SPE，并且它导致工人最优稳定匹配（在下一节中正式定义）。然而，这个声明是不正确的，如上面的例子所证明的，其中I中的工作者最优稳定匹配（以及唯一稳定匹配）是{（p1，q1），（p2，q2），（p3，q3）}。2.2稳定性和延迟接受算法在本节中，我们简要概述了稳定性和延迟验收算法（更多详细信息请参见参考文献[14，20，22，29]设I=（P，Q，E，×）为匹配实例。定义2.7（稳定性[11]）。对于匹配μ I，如果q p μ（p）和p q μ（q），则可接受对e=（p，q）E称为阻塞对（或阻塞μ）（其中回想一下，每个r P Q被认为是偏好r的底部）。如果不存在μ的阻塞对，则称匹配μI是稳定的，否则称为不稳定下面的陈述是农村医院定理的一对一设置版本[12，27，28]，这在多对一稳定匹配设置中是众所周知的第2.8节（Inv ARIA nc E o F un MATCHEDA g E n T s [23]）。如果在I中存在一个稳定匹配，在该匹配下r P Q是匹配的（分别是不匹配的），则r在I中的每个稳定匹配下都是匹配的（分别是不匹配的）。对于μ，μJI，如果μ（q）qμJ（q）（q Q），则写μQμJ，如果μ∈μJ，则写μQμJ很容易观察到Q是I上的偏序。服从I的稳定性，关于这个偏序的极大（极小）元是唯一的。定义2.9（最优性[20]（归因于J. H. Conway））。I中所有稳定匹配的集合形成关于偏序Q的分配格。[2]这个分配格中的唯一极大元称为工作最优或Q-最优，记为QOPT（I）。也就是说，对于I中的任何稳定匹配μ和任何工作者q∈Q，QOPT（I）（q）≥qμ（q）。工人最优稳定匹配可以通过众所周知的延迟接受（DA）算法[11]计算，该算法在算法1中描述。通过该算法，关于每对e=（p，q）E的提议及其拒绝分别在第4行和第7行中最多发生一次，并且关于第6行中的p的比较次数等于第7行中被p拒绝的工人的数量。因此，该算法总共需要O（E）时间。我们在这里展示了工人最优稳定匹配的几个性质，这些性质将在第3节和第5节中使用。2对于每两个匹配μ，μJ∈MI，存在μ∈ μJ：= min {ν ∈ MI|ν ≥Qμ且ν ≥QμJ}和μμJ：= max {ν ∈MI|ν·Qμ和ν·QμJ}。此外，对于每三个匹配μ，μJ，μJ∈MI，我们有μ（μJ<$μJJ）=（μμJ）<$（μμJJ）和μ（μJ<$μJJ）=（μμJ）<$（μμJJ）。序列匹配对策的子对策完美均衡第二十一ACM Transactions on Economics and Computation，卷。号74、第二十一条。出版日期：2020年1月×≺≺{∈|}–∈ ∃ ∈← ←− ∈–––−≺·−–算法1：面向Q的DA [ 11 ]输入：匹配实例I=（P，Q，E，）输出：Q-最优稳定匹配QOPT（I）1对每个r∈P<$Q，设I<$I和μ（r）<$r;2当3，对于每个q∈Q，使得μ（q）=q，且ΓI4设μ（q）为ΓI中的最优厂商（q使μ（q）∈P）;5对于每个p P，使得q Q，μ（q）=pdo6设为μ（p）q中最优选的工人Q μ（q）=p（在已向p提出的工人中）;7μ（q）q和II （p，q），使得μ（q）=p，且μ（p）≠q（p可解拒绝q8 returnμ;很好2.10。 对p ∈ P，q ∈ Q，若q在p的列表的顶部，则QOPT（I）（q）≥ qp.PR oF.相反，假设QOPT（I）（q）qp。然后我们有QOPT（I）（p）pq作为QOPT（I）（p）<$q，因此（p，q）是一个阻塞对，与QOPT（I）的稳定性相矛盾。□PR oPERT y 2.11. 对于e =（p，q）∈ E，如果QOPT（I）（q）= p，则QOPT（I）（q）×qQOPT（I-e）（q）。PR oF.假设QOPT（I e）（q）qQOPT（I）（q）=p.由于QOPT（I e）是I e中的稳定匹配，因此任何eJE e都不是阻塞对。然后，QOPT（I e）也是I中的稳定匹配，因为e不能是阻塞对（由于QOPT（I e）（q）qp）。这与QOPT（I）的Q最优性相矛盾。□PRoPERTy2.12. 对e=（p，q）∈E，如果QOP T（I）（q）=p，则theNQOPT（I/e）+（p，q）≥QOP T（I）.PRoF. Letμ：=QOP T（I）−e。 由于QOP T（I）在I中是稳定的，所以没有对EJ=（PJ，QJ）∈E/e使得QJ×PJμ（PJ）和PJ×QJμ（QJ），这意味着μ在I/e中是稳定的. 通过yQ-最优y，我们有QOPT（I/e）≥Q−qμ，因此QOP T（I/e）+（p，q）≥Qμ+（p，q）=QOP T（I）。□2.13. 对于e =（p，q）∈ E，如果QOPT（I）（q）×qp，则QOPT（I）= QOPT（I-e）。PR oF.由于QOPT（I）在I e中是稳定的，我们通过Q-最优性得到QOPT（I）QQOPT（I e）那么，pqQOPT（I）（q）q QOPT（I e）（q），因此e=（p，q）不能是QOPT（I e）的阻塞对。因此，QOPT（I e）在I中也是稳定的，因此QOPT（I）Q QOPT（I e）通过Q-最优性。□2.3SPE匹配的困惑性质在本节中，我们将演示在顺序匹配博弈中捕获SPE匹配有多难。具体来说，我们展示了几个可能无法实现的具体例子的属性这些内容与主要结果没有直接关系，对例1.1有足够了解的读者可以跳过这一节。第一个声称SPE匹配不满足“农村医院定理”的性质（参见。定理2.8）与稳定匹配相反。我在2.14的时候来了。 存在匹配实例，使得在SPE匹配中匹配的公司和工人的集合根据提供顺序而改变。第二十一Y. Kawase等人ACM Transactions on Economics and Computation，卷。号74、第二十一条。出版日期：2020年1月例2.15（命题2.14的证明）。 考虑一个匹配实例I =（P，Q，E，×），其中有四个公司P={p1，p2，p3，p4}和四个工人Q ={q1，q2，q3，q4}。可接受对的集合为E={（p1，q1），（p1，q2），（p1，q4），（p2，q2），（p2，q4），（p3，q1），（p3，q3），（p4，q4）}，偏好是p1：q2×p1q1×p1q4q1：p1×q1p3p2：q4×p2q2q2：p2×q2p1p3：q1×p3q3q3：p3p4：q4q4：p1×q4p4×q4p2。设σ1和σ2分别提供由位置阶π1和π2诱导的阶，使得（π1（1），π1（2），π1（3），π1（4））=（p1，p2，p3，p4）和（π2（1），π2（2），π2（3），π2（4））=（p4，p3，p2，p1）。然后，SPE匹配是SPE（I，σ1）={（p1，q1），（p2，q2），（p3，q3），（p4，q4）}和SPE（I，σ2）={（p1，q4），（p2，q2），（p3，q1）}。因此，匹配的企业和工人的集合（甚至其规模）都发生了变化。例2.16（命题2.14的另一种证明）。 在前面的例子中，较大的匹配是稳定的，但这并不总是正确的。考虑一个匹配实例I=（P，Q，E，×），其中有四个公司P={p1，p2，p3，p4}和四个工人Q={q1，q2，q3，q4}。可接受对的集合为E={（p1，q1），（p1，q2），（p1，q3），（p2，q2），（p2，q4），（p3，q2），（p3，q3），（p4，q1）}，偏好是p1：q2×p1q1×p1q3q1：p1×q1p4p2：q2×p2q4q2：p3×q2p2×q2p1p3：q3×p3q2q3：p1×q3p3p4：q1q4：p2.设σ1和σ2分别提供由位置阶π1和π2诱导的阶，使得（π1（1），π1（2），π1（3），π1（4））=（p1，p2，p3，p4）和（π2（1），π2（2），π2（3），π2（4））=（p2，p4，p1，p3）。然后，SPE匹配是SPE（I，σ1）={（p1，q1），（p2，q2），（p3，q3）}和SPE（I，σ2）={（p1，q3），（p2，q4），（p3，q2），（p4，q1）}。因此，匹配的企业和工人（甚至其规模）的集合发生了变化，在这种情况下，较小的匹配是稳定的。此外，通过将上述实例与例2.15中的实例组合，可以构造匹配实例，使得具有所有报价订单的SPE匹配的集合包括（i）小于其稳定匹配的匹配，（ii）大于它们的匹配，以及(iii)在企业和工人的匹配集合的意义上，这是一种无法与它们相比的匹配序列匹配对策的子对策完美均衡第二十一ACM Transactions on Economics and Computation，卷。号74、第二十一条。出版日期：2020年1月第二个是关于稳定性;我们已经在例1.1中观察到，SPE匹配在标准意义上可能不是稳定的（定义2.7），对于定义2.17和2.19中定义的较弱稳定性也是如此。定义2.17（冯 对于匹配μ，μ J∈ MI，我们说μ优于μJ，如果某对（p，q）∈μblocksμJ，i. 例如， q×pμJ（p）和p×qμJ（q）。一个非空的匹配集VMI称为vNM-稳定集，如果它满足以下两个性质：第二十一Y. Kawase等人ACM Transactions on Economics and Computation，卷。号74、第二十一条。出版日期：2020年1月∈M⎧⎪⎨⎪−−−−⎪−−⎩∈M≥.Σ----∞∞（内部稳定性）任何μ∈V不支配另一个μJ∈V;（外部稳