分配最大化

关于F AM mechan i sms：（i）对于任何问题P和任何稳定匹配Pu*, 对于a F AMmechan i smψ的每个平衡点P′，|ψ（P′）|≥ |u*|.（ii）复存在一个F AM机制ψ，问题P，以及ψ在P上的平衡曲线P′，例如|ψ（P′）|>u**|, 在哪里**是P的任何稳定匹配。有人可能会将本节中的结果解释为，使用EAM和FAM等最大化机制并没有多少好处，因为当代理人对其激励做出反应时，结果与其他非最大化机制产生的结果相似。然而，下面我们展示的是，只要部分学生是真诚的，匹配的基数就会有所改善。提议3。对于任何最大的机制ψ，问题P，以及具有错误偏好的学生，P′都是ψi（P′i，P-i） πψi（P），我们有|ψ（P）|≥ |ψ（P′i，P-i） |。此外，还存在一个问题，即带有错误偏好的学生i和ψi（`Pi，`P-i） ~Piψi（~P）和|ψ（~P）|>ψ（\'Pi，~Pi）|。在一个由最大机制诱导的偏好报告ga me中，唯一活跃的玩家是策略性学生，在这个意义上，其他人总是真诚的，命题3导致以下推论。推论1。在任何一种最大机制下，随着学生数量的增加，在任何问题中，均衡匹配的学生数量要么保持不变，要么增加。作业最大化6参考Abdulkadiroglu、Atila和Tayfun S–onmez，“学校选择：一种机制设计方法”，《美国经济评论》，2003年，93（3），729–747。3法坎，M.O，Z.H。

Aliogullari和Mehmet Barlo，“学校选择中的粘性匹配”，经济理论，2017年，64509–538。Afacan、Mustafa O和Umut M Dur，“经战略验证的规模改进：可能吗？”mimeo，2018年。Andersson、Tommy和J¨orgen Kratz，“血型屏障上的成对肾脏交换”，mimeo，2018年。拉尔斯·埃勒斯，“将难民分配给瑞典的安德洛兹：高效稳定的最大匹配”，即将出版，斯堪的纳维亚经济杂志，2018年。Ashlagi、Itai、Amin Saberi和Ali Shameli，“分配约束下的分配机制”，运营研究，2020年3月，6 8（2），46 7–479。克劳德·伯格，“图论中的两个定理”，《美国国家科学院院刊》，1957年，43（9），842-844。Bogomolnaia，Anna和Herv\'e Moulin，“随机分配问题的新解决方案”，经济理论杂志，2001年，100（2），2 95–328。和Herve Moulin，“二分偏好下的随机匹配”，Economo e trica，2004，72（1），257–279。以及《分配问题中的规模与公平》，《游戏与经济》cBehavior，2015年，90119-127页。Chun，Youngsub，Eun Jeong Heo和Sunghoon Hong，“免疫抑制剂的肾脏交换”，mimeo，2018年。Dur，Umut和Onur Kesten，“顺序与同时分配系统和两种应用”，经济理论，2019年，68（2），251–283。，Arda Gitmez和¨Ozgur Yilmaz，“部分公平的学校选择”，Forthcoming，《理论经济学》，2018年。Ergin、Haluk I、Tayfun Sonmez和M Utku–Unver，“双供体器官交换”，计量经济学，2017年，851645–1671年。，以及“高效且激励相容的肝脏交换”，m imeo，2018年。Gale，David and Lloyd S Shapley，“大学入学和婚姻的稳定性”，美国数学月刊，1962年，69（1），9-15.1，2里文，罗伯特·W.和大卫·F·曼洛夫，“寻找大型稳定匹配”，ACM J。

实验算法，2010年1月14日。Korte，Bernhard和Jens Vygen，算法与组合学2011。2Krysta，Piotr，David Manlove，Baharak Rastegari和Jinshan Zhang，“房屋分配问题中的规模与真实性”，第五届ACM经济与计算会议论文集——EC\'14，2014年。哈罗德·W·库恩，“分配问题的匈牙利方法”，《海军研究后勤季刊》，1955年，第2期（1-2），第83-97页。Morrill，Thayer和Lars Ehlers，“（Il）学校选择中的法律作业”，mi meo，2018年。2Nicol\'o，A ntonio和Carmelo Rodriguez Alvarez，“配对肾脏交换中基于年龄的参考”，游戏与经济行为，2017102508–524。野田俊彦，“供应灵活的大型市场中的大型匹配”，mimeo，2018年。阿尔文·E·罗思，“医学实习生和住院医师劳动力市场的演变：博弈论中的案例研究”，《政治经济学杂志》，1984年，92（6），991-1016。Roth、Alvin E、Tayfun S¨onmez和M Utku¨Unver，“肾脏交换”，经济学季刊，20041119105-129。2分配最大化7和《成对肾脏交换》，经济理论杂志，2005125（2），151–188。S¨onmez，Tayfun，M Utku¨Unver和¨Ozgur Yilmaz，“如何（不）将血液亚型技术整合到肾脏交换中，”经济理论杂志，2018年，176193–231。Troyan、Peter、David Delacr’etaz和Andrew Kloosterman，《基本稳定的配对》，mimeo，2018年。分配最大化8附录证明。定理1。我们将使用以下引理：引理。最大匹配u是有效的，当且仅当它不允许改进链或循环。当然。“只要”部分。设u为有效匹配。如果它允许一个改进链{i，..in，c，..cn+1}，那么我们可以通过将每个代理分配给ck+1，同时保持其他代理的分配不变，来定义一个新的匹配。

通过改进链定义，新匹配主导着u，这与我们最初认为u有效的假设相矛盾。同样的论点也适用于改进周期的情况。“如果”部分。设u为不允许改进链或循环的最大匹配。假设存在一个矛盾，即存在一个支配u的匹配u′。设W={i∈ I:u′iPiuI}。根据假设，w6=. 请注意，对于任何具有ui6的学生i=,我们有u′i6=. 这以及u的最大值意味着|u′|=|u|。因此，对于任何具有ui=, u′i=.用W={i，…，in}列举学生，并为任何k=1，…，写出u′ik=ck。。，n、 如果|uck |<qckforsome k，那么对{ik，ck}构成一个改进链，一个矛盾。假设|uck |=qckf对于任何k=1。。，由于CID没有在Ca和S\' i= C上有多余的CAPA城市，所以我们有另一个学生在W，比如I，C，然后考虑学生I，并且因为没有超额容量，在I和C＝C，我们有另一个学生在W，我说，所以I = C。如果我们继续与我们的W W的其他学生相同的参数，我们将得到一个改进的循环，矛盾。现在让ψ成为EAM机制，u和u′分别是其第一阶段和最终结果。由于在ψ的第1步中，学生没有被分配到他们不可接受的学校，u是个人的。假设u不是最大值，并且存在u′\'6=u，使得|u′\'|>u|。设{i，…，in}为ψ下使用的代理枚举。作为|u′′|>u|，存在一些代理ik∈ I使得u′ik6= 和uik=. 根据上述列举，将ik′作为起始点，使得u′ik′6= 和uik′=. 这意味着对于eachk<k′，μik6= 或μik= 和u′ik=. 设B（u，k′）=i∈ N：uik6= 对于任何k<k′}。

也就是说，这是一组在上述枚举中位于代理ik′之前的代理，它们被分配到匹配不足的u。现在考虑代理IK’。通过定义ψ，uik′= 因为在将B（u，k′）中的所有代理分配给其中一个可接受对象的同时，不可能将agentik′与他的一些可接受对象匹配。这意味着，为了让代理ik′接收其可接受的对象之一，必须取消从B（u，k′）分配的u下的一个代理的分配。这一论点适用于根据u′’分配但不根据u分配的每个其他代理。这意味着u是最大的。在ψ的第2步中，通过实施改进链和循环（如果有）来获得新的匹配。根据他们的定义，没有哪个学生的学校比他的作业更差。这一点，加上u的个体合理性，意味着tu′是最大的。u′的效率直接来自上述困境。命题2。设ψb为EAM机制。EAM第0步中的第一个学生通过将其报告为唯一可接受的选择，获得了自己的首选。根据同样的理由，第二名学生可以在考虑学生的作业后，在剩余的有座位的学校中，通过报告该学校是他唯一可接受的选择，获得他的首选。一旦我们对其他学生重复相同的论点，我们不仅找到ψ的n平衡，而且还得出结论，分配最大化9这是唯一的平衡结果，它与连续独裁的结果一致，顺序与ψ的步骤0相同。设φ为fam机制。设u为P处的稳定匹配。考虑偏好SubasePoP，对于任何学生I，唯一可接受的学校是：I。任何未分配的学生在P’s报告没有学校可接受。很容易验证φ（P′）=u。其次，我们认为P′是φ下的平衡提交。

假设一个矛盾存在一个学生i和P′i，φi（P′i，P′）-i） Piφi（P′）。为了便于编写，设φi（P′i，P′）-i） =砂φi（P′）=s′。由于u是稳定的，|us |=qs。这与P′和φi（P′i，P′）的定义有关-i） =s，意味着存在一个学生j6=i，使得uj=s和φj（P′i，P′）-i） =. 此外，从μ的稳定性来看，我们还有j硅。这些结果与未分配φ的学生的公平性相矛盾，表明P′是φ的平衡。理论3。我们将使用以下方法。引理。设ψ为EAM，φ为个体理性机制。在任何市场（I，S，, q） 问题P，如果|ψ（P′）|<|φ（P′）|其中P′和P′分别是ψ和φ下的平衡，那么存在一个学生i，使得ψi（P′）Piφi（P′）Pi.当然。在一个市场（I，S，, q） 问题P，设|ψ（P′）|<|φ（P′）|其中P′和P′分别在ψ和φ下平衡。这意味着，对于某些学派而言，|ψs（P′）|<|φs（P′）|≤ qs。因此，让我∈ φs（P′）\\ψs（P′）。通过φ和P′在φ下平衡的个体合理性，我们得到了sPi, 式中φi（P′）=s。由于ψ的唯一平衡结果与SD机制（命题5）的（真相）结果一致，我们得到了ψ（P′）=SD（P）。因此，在SD（P）下，学校有n过剩容量。此外，从上面看，ψi（P′）=SDi（P）6=s。因此，由于SD的非浪费性，我必须与严格优于s的school匹配，因此ψi（P′）=SDi（P）Piφi（P′）Pi, 这就完成了证据。现在让我们（我，S，, q） 做一个市场，ψ做一个团队机制。假设存在一个矛盾，即在平衡状态下，一个单独合理的机制φ尺寸方面主导着ψ。这特别说明，对于某些问题P，|ψ（P′）|<|φ（P′）|对于ψ和φ下的每个平衡点P′和P′。在下面的内容中，我们将固定一对这样的P′，P′。

我们分两步来证明这个结果。第一步。通过上面的引理，存在一个学生i，使得ψi（P′）Piφi（P′）Pi. 让“Pibeth偏好关系”保持学校的相对优势与Pi下相同，同时将任何比ψi（P′）更差的学校报告为不可接受。换句话说，“Pitruncates”在ψi（P′）以下。让我们写下\'P=（\'Pi，P-i） 。回想一下，ψ的唯一平衡结果总是与SD机制的真实结果一致（命题5）。更重要的是，通过'P的构造，SD（P）=SD（'P）。这又意味着ψ（P′）=ψ“P”对于ψ在问题P下的每个平衡点P。接下来我们考虑问题P。如果不存在学生j，则ψj“P”\'-Pjφj“P”“-Pj 对于ψ和φ下的一些平衡‘P’和‘P’，我们进入第2步。否则，我们选择这样的学生j。注意，由于“Pistates”的定义，任何低于ψi的结果“P”是不可接受的，因为i和φ分别是有理的，ψj“P”\'-Pjφj“P”“-Pj 不能为j=i保留，因此j 6=i。那么，如上所述，让¨Pjbe表示截断pjblowψj的首选项列表“P”. 让我们写下P=（\'Pi，\'Pj，P-{i，j}）。根据上述相同原因，ψ（P′）=ψ~P′对于问题P中ψ下的任意平衡点P′。接下来我们考虑问题P。如果不存在学生k，则ψk~P′~Pkφk~P′\'~Pk 对于ψ和φ下的一些平衡点P′和P′，我们进入第2步。否则，我们选择这样一个学生k。基于上述相同的原因，学生k与i和j都不同。然后，我们遵循上述相同的论点，获得一个新的偏好公式。在每次迭代中，我们必须考虑不同的学生。但是，由于学生人数众多，这种情况不可能永远持续下去。

因此，我们最终得到了一个问题，比如^P，其中不存在学生h，使得作业最大化10ψh（^P′）^Phφh^P′\'^Ph f分别为ψ和φ下的一些平衡态^P′和^P′，并移动到步骤2。我们也有ψ（P′）=ψ（P′）f或问题^P中ψ下的任何平衡点^P′。第二步。根据上面的引理，在问题^P中，我们有ψ^P′≥φ^P′\'对于ψ和φ下的任意平衡态^P′和^P′。如果它严格适用于某些平衡，那么我们就达成了一个矛盾。认为ψ（^P′）=φ^P′\'对于任何平衡态^P′和^P′。我们现在宣称，P′是问题P中φ下的平衡。假设不是，让学生k与^P′k有一个可证明的偏差，比如¨Pk。这意味着φk¨Pk，^P′\'-KPkφk^P′\'.但是，通过上面的构造，^Pk保留了Pk下的相对排名。这意味着φk¨Pk，^P′\'-K^Pkφk^P′\', 与^P′问题中φ下的平衡点相矛盾。回想一下ψ（P′）=ψ（^P′）。因此，这个ψ（^P′）=φ^P′\'我们的上述发现意味着在问题P中，|ψ（P′）|=φ^P′\'其中P′和^P′分别是ψ和φ下的平衡。因此，我们为问题P构造了一个平衡对，其中ψ与φ匹配，与我们的假设相矛盾，即这在问题P中不成立。理论4。（i） 。首先，根据乡村医院定理（Roth，1984），任何稳定匹配中的赋值数与DA中的赋值数相同。设ψ为fam机制。假设在ψ下存在一个问题P和一个平衡函数P′，使得|ψ（P′）|<|DA（P）|。为了便于编写，设DA（P）=ua和ψ（P′）=u′。我们现在宣称，对于某些学生i，对于某些学校s，ui=s，而u′i= 而且，更重要的是，|u′s |<qs。为了证明这一说法，让我们定义W={i∈ I:uI=s和u′I=}. 通过我们的假设| DA（P）|>ψ（P′）|，我们有w6=.

假设每个∈ W，其中ui=s，|u′s |=qs。但这意味着|u′|≥ |u|，与我们最初的假设相矛盾，我们最初的假设最终证明了这一论点。让我∈ I使得μI=s，μ′I=, 和|u′s |<qs。现在，考虑下列偏好p’：p’k＝P′kIf k 6=is， 如果k=i首先，观察在P′处存在一个（单独的有理）匹配，分配|u′|+1个学生s（要看到这一点，除了学生i，其他所有人的分配与学生i在u′处的分配相同，学生i在学校s处的分配相同）。因此，由于ψ的极大值，我们有|ψ（P′）|≥ |u′| + 1. 如果学生被分配到位于ψ（P′）t的学校，那么这与P′在ψ下的平衡相矛盾。因此，ψi（P′）=. 但是，根据P′的定义，ψ（P′）在P′处是单独有理的。这与ψ的最大值一起意味着|ψ（P′）|≥ |ψ（P′）|，与我们之前的结论相矛盾，即|ψ（P′）|≥ |ψ（P′）|+1，完成了第一部分的证明。（二）。让我们考虑i＝{i，j，k，h }和s＝{a，b，c}，每个都具有单位容量。优先权和优先权如下所示。Pi:a，b，; Pj:c，a，; Pk:c，a，; 博士：c，.a:k，i，j，h；b:k，h，j，i；c:k，h，i，j。设ψ是一个fam机制，学生顺序为k，j，i，h。机制ψ是这样的，它在P处产生匹配的u，其中ui=b，uj=a，uk=c，uh=. 任何P\'i∈ P与bP′i,设ψ（P′i，P-i） =u′，其中u′i=b，u′j=, u′k=a和u′h=c。此外，对于任何P′i∈ P与P′ib，ψ（P′i，P-i） =u′，其中u′i=, u′j=, u′k=a，a和u′h=c，对于任何P′h∈ P、 设ψ（P）-h、 P′h）=u。请注意，学生j永远不能通过误报而获得ψ下的学校c，因为否则学生H将被取消分配，并且他在学校c有更高的优先级。可以立即看到，在F AM的过程中，通过特定选择可以获得上述匹配。

所有这些都表明，在ψ下，讲真话是P处的平衡，|ψ（P）|=3。另一方面，DAi（P）表示DAi（P）=a，DAk（P）=c，DAh（P）=DAj（P）=. 因此，|ψ（P）|>|DA（P）|，完成了第二部分的证明。命题3。设P′=（P′i，P-i） ，ψ（P）=u，和ψ（P′i，P-i） =u′。假设|u′|>u|。根据我们的假设，u′iPiui。这与Pj=P′jj对于每个j6=i，u′是单独的理性问题P的事实一起。但是，|u′|>|u|与问题P中u最大的事实相矛盾。考虑{i，j}中的一个问题 N、 {a，b} S、 每个都有单位容量。让Pi:a，, Pj:a，,而其他学生（如果是纽约人）发现每所学校都不可接受。在不丧失普遍性的情况下，该问题中ψ的结果，例如u，是这样的，即ui=a，并且每个学生都是未分配的。考虑一个问题，其中p’i：a，b，, 而每个学生的偏好都是一样的。在真实偏好下，ψ产生u′，其中u′i=b，u′j=a，并且每个学生都是未分配的。然而，学生i可以通过提交Piabove来歪曲他的偏好，因为在这个错误的文件下，ψ产生了上面匹配的u。最后，请注意，|u′|>|u|，完成证明。