结合基于结果和基于偏好的匹配：一种受限的

也就是说，除了可能在一组代理认为最差的位置之间存在联系外，每个代理对其他位置都有严格的偏好。正式地，对于所有代理人i，如果l~对于某些l6=l，没有这样的l伊利诺伊州。这仍然允许代理在所有位置上都是独立的。这一假设的动机是我们对难民分配的申请：难民家庭通常没有关于所有可能地点的完整信息，但他们可能（严格）偏好于有限的一组首选。定义集合Si=L \\{L∈ L：l~il}是所有的位置，除了代理i不同的位置。代理人i在SIA的所有地点都有严格的偏好，如果任何地点被排除在Sithen之外，那么它一定是排名最差的。匹配的u将代理集映射到位置。匹配的u为1。如果满足容量限制，则可行：|u-1（l）|≤ ql，l2。\'g-如果平均结果得分不低于\'g，则可接受：nPigi（u（i））≥ “g.”g-可接受性反映了规划师希望平均结果分数不低于特定阈值的想法。规划师希望确保分配人员具有某种最低水平的预期结果（例如最低预期就业率/GPA或测试分数）。请注意，并非所有的“g”值都能产生可行的匹配。让\'gmaxdenote为可行匹配产生的最高可能平均结果分数：\'gmax：=最大unXigi（u（i）），受|u-1（l）|≤ ql，l（1）可行的“g”-仅存在“g”的可接受匹配≤ (R)gmax。2.2分配程序的值为“g”≤ (R)gmax，该算法从代理1开始，按n个步骤的顺序向下到代理n，然后在第n个步骤或额外的（n+1）个步骤中完成。

在步骤i≤ n、 代理i要么被分配到一个位置，要么被添加到一组临时未分配的代理，这些代理将在步骤n+1同时被分配。在每个步骤i中，让Nidenote保留已放置的代理集j<i。N= 因为在算法开始时，没有代理处于等待状态。我们假设所有代理都喜欢被分配到一个位置，而不是不被分配，因此我们可以从每个代理的可能结果集中省略不分配。我们认为这反映了排名最差地区的真实差异。如果代理事实上对这些位置有严格的偏好，但由于缺乏信息而表现出差异，那么我们的机制就不一定是战略证明。如果代理j<i在步骤i之前被分配了一个位置，那么让αi（j）表示该位置，而（j，αi（j））表示分配，查看αias a函数。请参阅步骤i中已完成的分配。请注意，α=, 因此，步骤1中完成的任务很简单。剩余的赋值βiat步骤i是未赋值代理{i，…，n}的映射∪ Nito位置，使得u（αi，βi）（j）：=αi（j）if j<iβi（j）if j∈ {i，…，n}∪ NI是匹配的。我们将u（αi，βi）称为与完成和剩余赋值对（αi，βi）相关的匹配。该算法将确保这些匹配的存在。在每个步骤i≤ n、 给定αide定义setL'gi（αi）={l∈ L： β为。t、 l=βi（i）和u（αi，βi）是一个可行的“g-可接受匹配”}这是一组未满负荷的位置，有一种方法可以完成分配所有未分配的代理，以创建一个可行的“g-可接受匹配”。设qil为在前一个i中分配了i之前的任何代理（即j<i）后，位置l的剩余容量- 1步骤。

首先，我们将ql=ql用于所有l。还可以方便地确定以下问题：对于所有步骤i=1。。。，n+1，给定一个向量qi：=（qil）l∈五十、 Gi（qi）：=最大βiXj∈{i，…，n}∪Nigj（βi（j））受|β影响-1i（l）|≤ 齐鲁，l（2）{i，…，n}：= 如果i=n+1。在每个步骤i，（2）中的问题会根据步骤i中更新的容量限制，找到最大化总结果分数的剩余任务。每个步骤中该问题的解决方案确定相关匹配是否为“g-可接受”。事实上，为了验证位置l是否属于l’gi（αi），我们必须首先检查剩余分配下可实现的平均结果得分的最高可能值是否至少为‘g’；i、 e.“gi（l）：=nGi+1（qi+1）+Gi（l）+Xj<i s.t.j/∈Nigj（αi（j））≥ (R)G其中qi+1l=qi对于所有l6=l和qi+1l=qil- 1、如果确实是gi（l）≥ g和qil＞0，则l属于l gi（αi）；否则，它不会。在每个步骤i=1，…，构造L'gi（αi）。。。，因此，n+1需要解决（2）中给出的问题。此外，为了验证“g<”gmaxalso是否需要解决其中一个问题，因为（1）中的问题等于g（q）/n。该算法的步骤如下。步骤0。验证“g”≤ \'gmax，仅当其保持不变时才继续。第一步≤ n、 如果Si∩ L'gi（αi）为空（意味着代理i没有严格指定的位置，我们可以找到生成可行的'g-可接受匹配的剩余分配），然后搁置代理i。在这种情况下，setNi+1=Ni∪ {i} ，αi+1=αi，qi+1l=qil着陆继续执行步骤i+1。否则，如果Si∩ L'gi（αi）是非空的，那么从代理i的角度来看，它包含一个唯一的最佳位置，即一个位置L*我知道我*我ilfor所有l∈ 硅∩ L'gi（αi）。

这源于我对姐妹元素进行排序的事实。将代理i分配给l*i、 setNi+1=Ni，αi+1=αi∪ {（i，l）*i） }，qi+1l*i=qil*我- 1，且qi+1l=qill 6=l*如果i<n，则转至步骤i+1。如果i=n，则仅当代理被挂起时（即Nn+16=); 否则，停止。步骤n+1。在此阶段，唯一未分配的代理是在Nn+1中保留的代理。在这里，根据完成的作业和能力限制，选择任何剩余的作业，使平均结果得分最大化；也就是说，求解（2）的i=n+1并停止。对于任何满足我们假设的偏好向量%，我们的算法会产生匹配，即u（αs，βs），其中s∈ {n，n+1}是算法停止的步骤。该算法定义了一种机制，给定模型的其他参数，该机制是从偏好向量到可行匹配的映射。我们将该机制称为“g-约束优先权”，因为它是对通常优先权机制的修改（Satterthwaite和Sonnenschein，1981）。在每个步骤i中，该机制的实施涉及迭代求解等式2中的最大化问题，以验证如果代理i按照偏好顺序分配给每个可用位置，则仍然可以满足“g-可接受性”，直到找到这样的位置。这相当于迭代解决一个标准的线性和分配问题，对于这个问题，存在各种多项式时间算法。在最坏的情况下，如果每个代理都在未成功考虑其所有严格分类的位置后被搁置，这将需要解决一个大小相等的最大化问题，即等式2，总共n（| L |）- 2） 《泰晤士报》。在图论中，分配问题被称为最大加权二部匹配。

请参阅补充信息（SI），了解有关分配问题在机制实现中的作用的更多详细信息。请注意，然后需要在步骤n+1中使用所有代理最终解决最大化问题。最坏情况的原因是（| L |）- 2） 术语是当代理对除两个地点以外的所有地点进行严格排名时，因为不可能对除一个地点以外的所有地点进行严格排名，如果对所有地点进行了严格的排名，则不会暂停代理，方程式2中的最大化问题将逐渐变小，并且在每个成功步骤i中解决的成本会降低。2.3 MechanismLet的属性ν（%）表示满足我们假设的任何偏好向量%的“g-约束优先级机制”产生的匹配，和Д（%）（i）代理i在此匹配下的位置分配。通过构造，该机制产生的匹配是可行的且“g-可接受”。此外，该机制满足两个关键特性。它是：1。约束效率，即对于满足您假设的所有偏好向量%，Д（%）不是由另一个可行的“g-可接受匹配u”支配的帕累托。也就是说，并非所有试剂i的u（i）%iИ（%）（i）和u（i）iИ（%）（i）对于某些代理i.2。策略证明，真实报告是诱导偏好报告博弈的主导策略。

也就是说，对于满足我们假设的每个偏好向量%，每个代理i，以及每个备选偏好%i，我可以报告也满足我们假设的，Д（%）（i）%iД（%i，%-i） （一）。该机制的约束效率和策略证明的证明很简单，但为了完整性，我们将其包含在SI中。规范优先级机制的一个重要特性是，该机制表征了全套帕累托有效分配，而不是我们的“g-约束优先级机制”。Abdulkadiroglu和Sonmez（1998）表明，对于任何帕累托有效分配，都存在一个代理排序，在该排序下，实现优先级机制会生成该分配。有鉴于此，人们可能会问，对于每个“g约束的效率分配”，是否存在“g约束的优先级机制”为其生成该分配的代理的排序。这个问题的答案是否定的，如下例所示，两个代理1和2以及三个位置A、B和C。该表给出了每个代理的三个位置的排名，并在括号中给出了每个代理位置对的结果得分gi（l）。第一个选项第二个选项第三个选项1 A（0.1）B（0.5）C（0.9）2 A（0.1）C（0.5）B（0.9）假设每个位置可容纳1个座位。如果规划师的阈值“g”设置为0.45，并且代理1首先进入，则他将被分配到位置A，代理2将被分配到B。如果代理2首先进入，则她将被分配到A，代理1将被发送到C。

但将1发送给B和2发送给C的可能性也符合规划师的约束，并且不受规划师可接受的任何其他任务的帕累托支配。3应用为了说明该机制，我们将其应用于模拟数据以及两个使用来自美国的真实数据的经验样本，这些数据涉及移民安置地点的安置和学生到学校的分配。我们的机制要求规划者为“g”选择一个值，而这个选择意味着在基于结果和基于偏好的匹配之间存在一种差异。从规划师的角度来看，最好实现“g”的最大可能值，以确保试剂的结果得到优化。然而，设置更高的“g”值是以将代理分配到预期偏好排名较低的地点为代价的。也就是说，虽然该机制同时考虑结果和偏好，但两者之间存在权衡，权衡的平衡会随着“G”的增加而变化。交易效果的大小还取决于代理人偏好排名及其结果得分的联合分布。特别是，有两个衡量标准发挥着重要作用：结果分数与代理人偏好排名之间的相关性（即代理人的首选位置与代理人将实现其最佳结果的位置一致的程度）以及代理人之间偏好排名之间的相关性（即代理人具有类似偏好排名的程度）。我们将在下面对此进行演示。3.1模拟数据我们将该机制应用于模拟数据，以显示这些特性。为了简单起见，我们的模拟包括将100名代理分配到100个位置，每个位置有一个座位。

对于每个阶段，我们随机生成一个偏好等级向量（1表示最期望的位置，100表示最差的位置）和一个结果得分向量（值在[0，1]）。模拟改变了偏好向量和结果向量之间的相关性(-0.5、0和0.5）以及跨代理的偏好向量之间的相关性（0、0.5和0.8）。这产生了九种不同的场景，在每种场景中，我们应用我们的机制来分配不同的“g”值。有关详细信息，请参阅补充信息（SI）。3.2难民数据作为该机制如何在真实场景中发挥作用的模拟说明，我们将其应用于来自美国难民的数据，其中难民家庭是代理人，移民安置城市是地点。早期就业是美国移民安置计划的核心目标，该计划致力于将难民快速过渡到本研究的复制材料中，可在Acharya等人（2020a，b）中找到。偏好和结果向量之间的相关性将更高的偏好（即接近1）视为更正值，因此偏好和结果之间的正相关性表明，更高的偏好位置也会导致更高的结果分数。到达后的自我支持。该应用程序说明了我们的机制如何假设在美国使用，以实现预期的早期就业水平，同时根据难民的位置偏好在地理上分配难民。我们的真实难民数据包括2011-2016年期间由美国最大的难民安置机构之一重新安置到美国的工作年龄难民（18至64岁；N=33782）的未识别信息。在此期间，各机构的安置办公室将难民集中分配到工程处网络中约40个安置地点之一。

这些数据包含难民特征的详细信息，如年龄、性别、出身和教育。它还包括指定的安置地点、难民是否在抵达后90天内就业，以及难民是否在90天内从最初的地点移民。我们将我们的机制应用于2016年第三季度（Q3）抵达的难民家庭的数据，特别关注可以自由分配到不同安置地点（561个家庭）的难民，而不是根据现有家庭或其他关系预定到特定地点的难民。为了在每个地点生成每个家庭的结果得分向量，我们采用了Bansak等人（2018）的相同方法，利用2011年至2016年第三季度（但不包括）的难民数据，生成模型，预测家庭在任何地点的预期就业成功率（即家庭工作年龄成员的平均就业概率），作为其背景特征的函数。然后将这些模型应用于2016年第三季度抵达的家庭，以生成他们在每个地点的就业成功预测，这包括他们的结果得分向量。详见SI和Bansak等人（2018）。我们的机制还需要关于难民位置偏好的数据。据我们所知，美国目前不存在此类数据，因为那里的难民被安置机构分配到不同的地点。因此，我们从二次迁移行为推断出所揭示的位置偏好。具体而言，我们使用与结果得分估计中使用的建模程序相同的建模程序，只是将外迁替代就业作为响应变量。

这使我们能够预测2016年第3季度抵达的每个refugeefamily在每个位置的外迁概率，作为其背景特征的函数。然后，我们对每个家庭的位置进行排名，以确保外迁概率最低（最高）的位置排在第一（最后）。SI中提供了有关数据和样本的详细信息。我们承认，从二次移民行为推断出的位置偏好不一定与难民在申请表中表示的位置偏好相同，如果东道国政府有机会这样做。也就是说，有理由相信推断的位置偏好提供了一个有用的代理。外迁是一个代价高昂的信号，表明难民宁愿搬家，也不愿留在原来指定的地点。Mossad等人（2020年）对美国难民的二次移民模式进行了全面分析，并发现二次移民主要是由寻求就业机会和共同种族社区的难民迁移驱动的。这些影响发挥作用的主要渠道之一是难民的国籍，这也是我们用来推断二次移民所揭示的区位偏好的模型中的一个重要预测因素。3.3教育数据作为该机制在现实世界场景中如何运行的第二个模拟示例，我们将其应用于来自美国的教育数据，其中代理是个别学生，地点是学校。特别是，我们考虑了田纳西州教育部开展的田纳西州师生成就率（STAR）项目的数据（详情见Achilles et al.（2008））。