匹配市场推荐的优化排名

3280优化匹配市场推荐的排名0YiSu康奈尔大学美国纽约州伊萨卡市ys756@cornell.edu0MagdBayoumi康奈尔大学美国纽约州伊萨卡市mb2363@cornell.edu0ThorstenJoachims康奈尔大学美国纽约州伊萨卡市tj@cs.cornell.edu0摘要0基于推荐系统在电子商务和娱乐领域的成功，人们越来越关注它们在求职等匹配市场中的应用。虽然这对于改善市场流动性和公平性具有潜力，但我们在本文中表明，将现有的推荐系统天真地应用于匹配市场是次优的。考虑到候选人先申请，然后由雇主评估的标准流程，我们提出了一个新的推荐框架来模拟这种交互机制，并提出了在这种情况下计算个性化排名的高效算法。我们表明，最佳排名不仅需要考虑候选人和雇主的潜在偏好的差异，还需要考虑容量限制。这使得仅仅根据某些局部分数（例如，单方面或相互关联）进行排名的传统排名系统高度次优，不仅对于个体用户，而且对于社会目标（例如，低失业率）也是如此。为了解决这个缺点，我们提出了第一种方法，用于联合优化市场上所有候选人的排名，以明确最大化社会福利。除了理论推导，我们还在模拟环境和我们在一个大型计算机科学会议上构建和实施的真实网络推荐系统的数据上评估了该方法。0CCS概念0• 信息系统 → 概率检索模型；• 计算方法 → 排名。0关键词0多边市场，排名，社会福利0ACM参考格式：Yi Su，Magd Bayoumi和ThorstenJoachims。2022年。优化匹配市场推荐的排名。在第28届ACMWeb会议2022年（WWW'22）会议论文集，2022年4月25日至29日，虚拟活动，法国里昂。ACM，纽约，美国，11页。https://doi.org/10.1145/3485447.351196101 引言0大多数搜索和推荐系统依赖于排名作为向用户呈现结果的主要方式。通过首先对最有前途的项目进行排名，它们旨在将用户的注意力集中在上面0未经ACM事先明确许可和/或收费，授予所有或部分此作品的数字或硬拷贝以供个人或课堂使用，但不得为牟利或商业优势而制作或分发副本，并且副本必须带有本通知和第一页的完整引用。必须尊重ACM以外的其他组织拥有的此作品组成部分的版权。允许带有信用的摘要。未经事先明确许可和/或收费，复制，重新发布，发布在服务器上或重新分发给列表，需要事先明确的许可和/或费用。请向permissions@acm.org请求权限。WWW'22，2022年4月25日至29日，虚拟活动，法国里昂。©2022年计算机协会。ACM ISBN978-1-4503-9096-5/22/04...$15.00 https://doi.org/10.1145/3485447.35119610在项目数量庞大时，考虑集合的大小是可以被处理的。对于在线零售或媒体流媒体中的排名系统的传统应用，长期以来人们已经理解到，根据物品与用户的相关性（或购买或点击）的概率对物品进行排名在标准假设下提供了最大效用。根据相关性的概率进行排序被称为概率排名原则（PRP）[29]，它意味着任何用户的最佳排名仅取决于他们的偏好。然而，对于越来越多的新型在线平台（如求职、大学录取、约会或社交推荐）来说，PRP不再是最优的[4, 15, 21,38]。匹配市场的以下两个关键特性使得排名问题比传统的双边市场复杂得多。首先，成功的匹配要求匹配的双方对相互的相关性达成一致[14,26]。其次，双方都对他们可以评估的选项数量有限制。在这些条件下，任何一个参与者的最佳排名取决于市场上其他参与者的排名和相关性，这可能使得PRP排名高度次优。为了说明这些依赖关系的来源，考虑一个求职匹配问题，其中许多求职者聚集到一小部分知名度高的雇主身上。受欢迎的雇主将收到许多申请——超过他们可以仔细评估的数量，其中许多申请者没有所需的资格。与此同时，较不知名的雇主可能不会被相关的候选人发现。结果是许多候选人从受欢迎的雇主那里没有得到回音，许多雇主无法填补职位。这不仅对个体雇主和候选人不利，而且对于系统提供的社会福利来说也是一个不良结果（例如，最小化失业和未填补的职位）。为了解决这个问题，求职匹配的推荐系统应该考虑到候选人（例如，西海岸地点，Python）和雇主（例如，5年经验，Python）的偏好和资格，并帮助发现避免拥挤的互利匹配。本文的主要贡献有四个方面：（1）首先，本文是第一个在许多实际应用中使用的应用/接受交互协议下形式化双边匹配市场排名问题的论文。（2）其次，我们提出了第一个能够共同优化所有候选人的个性化排名以最大化双边匹配市场社会福利的推荐系统。（3）第三，我们讨论了在这个框架下排名的额外战略行为（例如采纳和保留）和公平性问题，这为未来的工作开辟了一个重要领域。（4）最后，我们构建了一个实际的网络推荐系统，该系统在一个大型计算机科学会议上进行了实地测试。我们在这个真实数据集上对我们的方法进行了实证验证，并提供该数据集作为未来研究的基准。3290WWW '22，2022年4月25日至29日，虚拟活动，法国里昂，Yi Su，Magd Bayoumi和Thorsten Joachims01.1 结果概述0在进入我们的方法的正式和数学细节之前，我们提供模型和主要结果的概述。使用申请/接受协议对匹配市场进行建模：我们考虑申请/接受交互协议，这是在职位搜索和大学录取等匹配市场中主要使用的协议。为了清晰起见，我们以职位搜索为例，市场一侧的求职者通过向他们感兴趣的雇主发送申请来行动。市场的另一侧的雇主在评估收到的申请后做出回应，积极的回应会导致双方都希望的匹配结果。我们框架的一个关键组成部分是求职者和雇主都有有限的注意力，因此必须在部分信息下行动。特别是，求职者无法评估所有职位发布，因此需要一个个性化的排名，将他们的注意力集中在最有前途的职位发布上。同样，雇主希望对收到的申请进行排名，以便对审核过程进行分流和更好地分配审核资源。这导致了一个双边排名问题，我们对其进行了形式化，并将相互相关的匹配总数确定为社会福利目标（即最小化失业和未填职位）。请注意，与之前的工作[4, 14, 15, 21, 26,38]相比，这个双边排名问题是根本上的新问题。优化注意力和发现：我们的框架的目标与传统经济学中已知偏好下的匹配优化不同。相反，我们支持当选项数量较大时市场两侧的偏好形成。因此，我们的目标是通过将市场两侧的注意力预算集中在最有前途的选项上，最大化社会福利，这类似于传统推荐系统的注意力集中目标。通过这种方式，我们的方法支持每个参与者发现最有前途的选项进行手动评估，优化参与者在常常令人不知所措的选项集中如何分配有限的注意力资源。这使得所有参与者都对自己的决策拥有自主权，这与传统的匹配程序[10,16]不同，传统的匹配程序要求所有参与者服从决定匹配结果的集中匹配程序[31]。捕捉相互相关性和拥挤：在申请/接受协议下，由于雇主的有限注意力预算，求职者的排名变得相互依赖。我们是第一个在求职者和雇主都将推荐作为排名时建模这种依赖关系的人。特别是，候选人向知名雇主的拥挤程度会影响雇主是否会注意到申请者并收到回复，从而影响其他候选人对拥挤雇主的评估优先级。因此，我们对每个候选人在雇主排名中的位置进行建模，这取决于所有其他候选人的申请行为。我们的模型是第一个在拥挤和相互相关性引入的依赖关系下捕捉排名系统社会福利的模型。优化社会福利的排名方法：我们的关键算法贡献是第一个计算在双边匹配市场中优化社会福利的排名方法。这个目标要求我们同时计算所有参与者的排名。0在市场中，候选人的效用也取决于其他人的行为，因此为每个候选人提供效用的算法与传统的排名算法有根本的不同，传统的排名算法中，每个用户的排名是独立优化的。为了得到一个可行的算法，我们采用了三个关键的技术步骤。首先，我们展示了如何将排名的离散和指数级优化问题转化为多项式大小的边际排名分布的随机优化问题。其次，我们推导出社会福利目标的下界，并展示了如何高效地计算和优化这个目标。最后，我们利用Birkhoff-vonNeumann分解从我们在优化过程中使用的紧凑表示中恢复排名。提供了纳入战略行为的潜力：除了开发用于最大化市场整体效用的算法之外，我们还引发了关于匹配市场排名中公平性和战略行为（如用户采用和保留）的讨论。这些问题比传统的排名系统更复杂，因为个体的行为会相互影响。然而，我们基于优化的框架为纳入各种约束条件（如统计平衡和基于功绩的曝光约束）提供了有希望的潜力。所有这些都为未来关于这种新型匹配市场排名系统的工作开辟了重要的领域。01.2 相关工作0随着多边市场平台成为一种流行的商业模式，搜索和推荐系统在调解它们的交互中发挥了关键作用。这些系统需要平衡各方利益，如用户、供应商和平台本身。关于如何指定每个利益相关者的目标[17]、它们之间的相互作用[18,41]以及在多边市场推荐中设计高效的联合优化目标[19, 30, 36,45]的最近工作有很多。重要的目标包括多样性[7, 27]、新颖性[28,39]和公平性[5, 6, 33,44]。大部分工作依赖于多目标优化技术，包括寻找帕累托前沿[23]、使用归约为单一目标的聚合函数[13, 19,45]，或将一些目标作为约束[30, 33,34]。与这些工作大部分不同，我们直接对两边匹配市场的交互过程进行建模，并旨在最大化市场的整体社会福利作为关键目标。我们的问题设置是一种互惠推荐[14,26]，考虑到双方都有偏好的匹配问题，如在线约会[38, 42]、求职[2,20,43]和社交媒体[46]。因此，大多数互惠推荐系统通过一个结合了双方偏好的互惠分数进行排名，如调和平均数[25]、相似性之和[2]、乘积运算符[37]和社区级匹配[3]。在这些工作中，[38]与我们最接近。他们提出了一个用于约会推荐的两边匹配框架，最大化互发消息的总数，同时通过保持接收/发送的预期消息数量有限来避免给每个用户带来过多负担。[38]中的一个关键简化假设是系统为每个用户提供了一个预定数量的推荐，这在实践中通常很难高效地选择，然后所有这些推荐都将被全面评估。3300在匹配市场中优化推荐排名 WWW '22，2022年4月25日至29日，虚拟活动，法国里昂0用户。最近关于匹配问题的组合规划[4]的工作也做出了类似的假设。我们考虑更现实和更一般的情况，即每个用户都显示一个排名，而每个用户在排名中的位置存在不确定性。此外，我们模拟了广泛使用的申请/接受协议，这在现有方法中没有得到支持。我们的工作还建立在经济学和社会科学文献关于匹配市场的基础上。这里，核心问题在于设计匹配程序。特别是，稳定匹配算法[10]将市场两边的排名偏好列表作为输入，并产生稳定的一对一或多对一匹配，而最大权匹配[9]考虑加权偏好图。相比之下，我们的工作帮助用户在一个难以处理的大量可选项集中形成他们的偏好。特别地，我们不强制最终的匹配步骤，而是让所有参与者对他们的行动和最终决策拥有自主权。这使得它与传统的匹配程序有根本的不同。02 匹配市场中排名的框架0我们首先介绍了我们在匹配市场中的新排名框架。为了简单和具体，我们以工作推荐平台作为一个运行示例。然而，该框架是通用的，可以适应其他领域，其中（1）匹配的成功依赖于双方的相关性，（2）双方都有有限的注意力。我们考虑以下的顺序和不对称的交互协议。首先，求职者（主动方）浏览他们排名的工作列表，并申请他们认为相关的工作。之后，雇主（被动方）浏览他们的申请者的排名，并回应他们认为相关的申请者（例如，邀请面试）。我们称之为匹配，排名系统的目标是为每个候选人设计排名，以最大化市场中预期匹配的总数。现在我们对这个交互模型进行形式化，然后在第3节中提出了联合优化所有候选人排名的算法。图1中的玩具示例作为我们在接下来开发的模型的直观指南。我们将市场中的候选人集合表示为C，雇主集合表示为J，其中|C| < ∞且|J| <∞。为了简单起见，我们使用二进制相关性r(c, j)∈{0,1}来表示雇主j与候选人c的相关性（即c想申请j）。类似地，˜r(j,c)∈{0,1}表示候选人c对雇主j的相关性（即j想面试c）。然而，排名系统并不知道确切的相关性，而只能访问相关性概率。0f c(j) := P(r(c, j) = 1) 和 д j(c) := P(˜r(j, c) = 1)。0关于如何估计相关性概率的大量文献已经存在，为了本文的目的，我们假设准确和无偏的估计是存在的。02.1 候选人行动（主动）0与许多现实世界的市场一样，候选人在我们的模型中首先行动。我们的推荐系统以上下文化的方式进行描述。0随机排名策略 π: C →∆Σ|J|，将每个候选人映射到雇主排名的概率分布。所有可能排名的空间由 Σ|J| 表示。对于每个候选人 c，系统根据 π(∙| c)采样一个确定性排名 σ(c)，即 σ(c) � π(∙| c)，并将其呈现给候选人c。每个候选人 c 在接收到雇主排名 σ(c)后，独立地按照排名进行申请，如果雇主相关，则申请。我们使用基于位置的模型（PBM）[12]来模拟这个申请过程。给定排名σ(c)，PBM 将候选人 c 申请职位 j 的概率建模为相关性概率 f c(j)和考试概率 P(e(j) = 1 | σ(c)) 的乘积：0P(c applies to j | σ(c)) = f c(j) ∙ P(e(j) = 1 | σ(c)) (1)0考试概率表示候选人在特定排名中发现一个职位的可能性。在 PBM中，这个考试概率仅取决于排名 σ(c) 下雇主 j 的排名 rank(j |σ(c))。因此，我们可以写成：0P(e(j) = 1 | σ(c)) = v(rank(j | σ(c))), (2)0其中 v 是一个应用程序相关的函数。常见的选择包括 v(x) = 1/x [12] 和 v(x) = 1。0log(1 + x) [11]，或者可以直接估计应用程序相关的 v[1]。结合这一点，候选人 c 在排名策略 π 下申请给雇主 j 的概率 Pπ c, j 可以表示为：0P π c, j := P(c applies to=0σ(c)∈ Σ|J| π(σ(c)| c) f c(j) v rank(j |σ(c)). (3)0这个表达式乍一看可能是棘手的，因为它涉及到指数数量的可能排名的求和。然而，注意到相关性概率 f c(j) 不依赖于排名，而考试概率v rank(j | σ(c))0仅取决于排名，因此可以等价地用雇主 j 在策略 π 下被排在排名 k的边际概率 P(rank(j | σ(c))) = k 来表示 P π c, j。因此，P π c, j可以重写为：0P π c, j = f |J|0k = 1 P(rank(j | σ(c)) = k | π) v(k) = c(j) |J|0k = 1 M π c(j, k)v(k)0M π c 表示候选人 c 的双重随机矩阵，其中 (j, k) 位置等于 P(rank(j| σ(c))) = k | π。这使得我们在表示候选人 c 的排名策略 π(∙| c)时，只需使用 |J|2 个参数，即 M π c，因为具有相同 M π c的所有随机排名策略是等价的。同时，我们使用 M π C表示所有候选人的双重随机矩阵的连接。接下来，这将使我们能够在双重随机矩阵的空间中进行优化，而不是在指数级大小的排名空间中进行优化。一旦找到最优的 M π c，我们使用 Birkhoff-vonNeumann（BvN）分解来高效地找到与 M π c对应的随机排名策略，并在多项式时间内对候选人进行抽样排名[33]。为了进一步简化表示，我们将考试概率 1 写为向量 v ∈R|J|+，其中 v[k] = v(k) 对于 k ∈01 在这里，我们假设用户的考试是同质的。可以很容易地扩展到异质用户的情况。𝑗!0.20.2000.6𝑗"0.20.200.60𝑗#000.80.20𝑗$00.60.200.2𝑗%0.6000.20.2𝑗%𝑗$𝑗#𝑗"𝑗!𝑓&!(𝑗%)!"𝑓&!(𝑗$)!#𝑓&!(𝑗#)!$𝑓&!(𝑗")!%𝑓&!(𝑗!)𝑔'"(⋅)𝑐!✓0.7𝑐"✓0.9𝑐#✗0.8𝑐$✗0.2𝑐%✓0.6𝑐"𝑐!𝑐%𝑔'"(𝑐")!"𝑔'"(𝑐!)!#𝑔'"(𝑐%)𝑀&!(3310WWW ’22，2022年4月25日至29日，虚拟活动，法国里昂，作者：Yi Su，Magd Bayoumi和Thorsten Joachims0位置10位置20位置30位置40位置50给 � !0应聘0概率0候选人 应聘 相关性0雇主 � 的排序0回复0概率0图1：一个双边匹配市场，有 5 个候选人，5 个雇主和考试函数 v ( x )  =  1 / x。黄色表格显示了特定候选人 c 1的交互过程，而绿色表格是特定雇主 j 4 的交互过程（其他候选人和雇主遵循类似的过程）。从左到右，系统首先计算出个性化的随机排序 M πc 1（一个 5 × 5 的矩阵），然后对 c 1 产生一个排序 ( j 5 ,  j 4 ,  j 3 ,  j 2 ,  j 1 )，呈现给 c 1，c 1根据基于位置的模型应聘给雇主。对于雇主方面，过程的一个实例显示了 { c 1 , c 2 , c 5 } 应聘给 j 4。因此，系统按照 д j 4 (∙) 的顺序将排序 ( c2 , c 1 , c 5 ) 呈现给 j 4。最后，j 4 也按照基于位置的模型回复。0{ 1 ,  2 ,  3 ,  ∙ ∙ ∙  ,  |J |} ，我们使用 e j 作为 |J |维向量空间中的标准基向量，第 j 个位置为 1，其他位置为0。现在候选人 c 应聘给雇主 j 的概率可以写成： P π c , j =  f c ( j )e T j M πc  v .02.2 雇主行动（反应性）0收集完所有的应聘后，轮到雇主回复了。具体来说，排名系统会给每个雇主 j 一个按照他们的相关性概率 д j (∙)对应的候选人排序列表，列表中的候选人是应聘给他们的，按照雇主特定的概率排序。我们将应聘给雇主 j 的候选人集合表示为 C π j �C，需要指出的是 C π j 是随机的，随机性来自候选人在政策 π下的应聘结果。然后每个雇主都会回复给应聘者 c ∈ C πj，遵循一个0与我们为候选人介绍的模型类似，雇主也采用了类似的基于位置的模型。特别地，雇主 j 回复候选人c（例如，邀请面试）的概率取决于相关性概率 д j ( c )和考试概率。需要注意的是，任何应聘给 j 的候选人 c的考试概率取决于 C π j 中还有谁，从而导致了一个排名的分布。设rk π j ( c ) 表示候选人 c 在特定的 C π j 中的排名，按照 д j ( c )排序。我们可以将回复的概率写成如下形式：0P π j , c : =  P ( j  回复  c | c  应聘给  j ,  π )  =  д j ( c ) E � v � rk πj ( c ) �� (4)0期望是在Cπj的随机性上，这是由候选人一方的申请过程引起的。02.3效用和社会福利0我们现在制定排名系统的目标，这是基于成功匹配的概念。对于候选人/雇主对（c，j），如果候选人c成功地发现了一个相关的j并因此申请，雇主j也发现了c相关并成功地在申请者中发现了这个候选人，那么这个匹配是成功的。我们使用Yπc,j∈{0,1}来表示匹配是否成功。我们定义排名系统对候选人c提供的效用Uc(π)为c收到的匹配数（例如，面试）的期望。0一般来说，候选人和雇主的检查函数v（∙）可能不同。为了简化表示，我们在这里保持相同。0j∈J P(Yπc,j=1) = �0Uc(π) = 0j∈J P(Yπc,j=1) = �0j∈J Pπc,jPπj,c0= �0j∈J0�fc(j)дj(c)E�v�rkπj(c)���eTjMπcv(5)0重新排列项后，我们可以看到排名策略π对于候选人c的效用类似于传统的排名度量，如DCG[11]。关键区别在于，每个排名项目的效用不仅取决于候选人自身的相关性，还取决于雇主和潜在的所有其他候选人的相关性，因为它们影响该候选人在雇主排名中的位置。我们还可以为每个雇主定义类似的效用Uj(π)。鉴于个体效用的这种相互依赖性以及许多这些匹配市场所扮演的社会角色，我们将社会福利作为排名系统的总体目标。我们选择社会福利SW(π)的最直接定义，即排名策略π在市场上产生的匹配数的期望。注意，这等价于最大化候选人效用的总和，或者等价地最大化雇主效用的总和。SW(π) = �0c∈C Uc(π) = �0j∈J Uj(π) (6)0最大化匹配总数可以说是对社会目标的合理代理（例如，最小化失业），尽管可以进一步细化此目标（例如，个体的递减收益[22]）以实现其他目标。特别是，确保这种排名系统的公平性是一个重要的附加考虑因素，我们将在第4.3节中进一步讨论。总之，我们在本文中考虑的问题是“双边匹配市场中排名的社会福利最大化问题”。0定义1.给定一个具有主动方C和被动方J的双边匹配市场，以及双边相关概率fc（j），дj（c）�c∈C，j∈J，目标是设计一个随机排名策略π，以最大化市场中的匹配数的期望。c1j1j3j2c2j2j1j3c3j1j2j3fc(j)10.90.1j1c1c3c2j2c2c1c3j3c1c2c3дj(c)10.90.13320Optimizing Rankings for Recommendation in Matching Markets WWW ’22, April 25–29, 2022, Virtual Event, Lyon, France0尽管是对现实世界的抽象，我们的模型捕捉到了许多现代双边匹配市场中面临的关键互动和权衡，其中（1）可用选项的数量通常非常大，（2）市场的双方都没有资源来全面评估所有选项，（3）成功的交易取决于双方的相关性匹配。实际上，市场的双方互动可能是一个高度动态的过程。我们认为，通过在市场上可用的任何新信息的基础上重复优化排名，我们的框架可以适应这一点。值得指出的是，我们的排名问题与经济学文献中考虑的稳定匹配问题根本不同[10,16]。首先，我们的排名问题旨在通过聚焦用户的注意力来帮助用户形成对选项的偏好，而不是假设用户可以轻松地陈述他们对匹配过程的偏好。然而，它仍然没有解决稳定匹配程序是否可以用来解决我们的优化问题的问题。为了回答这个问题，考虑以下简化的top-1排名问题，其中所有参与者只检查他们排名的第一个位置（即v（1）=1且v（k）=0对于所有k≥2和双方都成立）。此外，我们假设相关概率fc（j）和дj（c）对于每个候选人和雇主都意味着一个偏好顺序。以下命题澄清了即使在这种简化的情况下，稳定匹配和社会福利最大化也不等价。0命题2.一个稳定的匹配不一定是社会福利最优的前1名排名，而不稳定的前1名排名可能比稳定的匹配具有更好的社会福利。0证明。我们通过考虑上述双边市场来证明该命题。有三个求职者 { c 1, c 2 , c 3 } 和三个雇主 { j 1 ,  j 2 ,  j 3 }。左侧显示了候选人的相关性表，其中每一行是按照候选人一侧的相关概率 f c ( j )排序的雇主的排名列表。类似地，右侧的表是按照雇主一侧的相关概率 д j ( c ) 排序的候选人的排名列表。匹配 {( c 1 ,  j 1 ) ,  ( c 2 ,  j 2) ,  ( c 3 ,  j 3 )} 是稳定的，并且它提供了一个社会福利为 1  +  1  +0 . 1  ×  0 . 1  =  2 . 01。现在考虑确定性排名策略 π ，使得 π (∙| c1 ) 在排名 1 推荐 j 3 ，π (∙| c 2 ) 在排名 1 推荐 j 2 ，π (∙| c 3 )在排名 1 推荐 j 1 。这个排名策略提供了一个社会福利为 1  +  0 . 9+  0 . 9  =  2 . 8，但它不是一个稳定的匹配（c 1 和 j 1更喜欢彼此而不是他们当前的匹配）。□03 在匹配市场中优化排名0我们现在探索计算最大化社会福利的排名策略 π的算法。为了激发对这些新算法的需求，我们首先在理论上量化了传统PRP策略的次优性，这些策略基于单侧相关性进行排名。用 π n表示朴素的基于相关性的策略，使得对于每个候选人 c ，π n (∙| c )按照 f c ( j ) 进行排序，因此推荐0职位 j 在位置 φ c ( j ) 上的概率为1，其中 φ c ( j ) 表示按照 f c ( j )排名时 j 的排名。等效地，考虑使用双随机矩阵 M π n C进行等价表示，我们0与社会福利最优排名 M π  � C 进行比较。0定理3. 存在一个具有检查模型 v (∙) 和相关概率 f c ( j ) 和 д j ( c )的双边匹配市场，使得最优排名 M π  � C 和朴素的单侧相关性排名M π n C 之间的社会福利差距大于 Θ ( n ) 。0证明见附录6.2。关键思想是构造一个实例，其中存在一个受欢迎的雇主 j �，对所有候选人都有很高的相关概率。朴素的基于相关性的排名将会将 j �排在所有候选人的首位，从而造成拥挤，而最优策略也将考虑到可能具有微不足道较小相关概率的不那么拥挤的雇主。03.1 一个可行的优化目标0鉴于朴素排名的次优性，我们现在开发直接优化社会福利的算法。我们首先证明原始目标是难以直接优化的。为了解决这个问题，我们推导出一个下界，并提出了解决它的高效算法。在深入分析之前，我们将介绍本节中将使用的一些符号。类似于 φ c ( j ) ，我们定义 φ j ( c) ∈ { 1 ,  2 ,  3 ,  ∙ ∙ ∙  ,  |C|} 为候选人 c 在雇主 j 的相关概率 д j ( c )的排名。我们任意打破平局。相反地，我们定义 φ − 1 j ( s )  : =  {c ′  ∈ C| φ j ( c ′ )  =  s } 为在按照 д j ( c ) 排名时在 C 中以排名 s列出的候选人。相应地，我们定义雇主 j 关于候选人 c的优先级集合为 A j ( c )  : =  { c ′ ∈ C| φ j ( c ′ )  <  φ j ( c )}，其中包括那些对雇主 j 来说具有比候选人 c更高相关概率的候选人，由 д j ( c ) 衡量。基于此，令 F l ( j , c )，其中 l ≤ | A j ( c )| ，为所有 l 项的子集的集合0可以从Aj(c)中选择的候选人的数量：Fl(j,c):={B�Aj(c)||B|=l}。给定考察函数v(∙)和双边相关概率fc(j)和дj(c)，注意我们的社会福利目标可以写成：0SW(π) = �0c∈C0j∈J Pπc,jPπj,c = 0c∈C0�0j∈J0�f c(j)eTjMπc0� ������������ �0Pπc,j0дj(c)E�v�rkπj(c)��0� ����������������� �� ����������������� �0Pπj,c0候选人c申请雇主j的概率Pπc,j在策略π（或其对应的双重随机矩阵MπC）中是可线性计算的。困难在于分析rkπj(c)这一项，它是一个随机变量，取决于其他候选人c∈C是否申请给雇主j以及它们之间的相关性。下面的引理给出了rkπj(c)的精确分布，其参数取决于排名策略π。0引理4.对于任意固定的j∈J，c∈C，在排名策略π下，候选人c在申请给雇主j的候选人集合中的排名rkπj(c)是一个随机变量，其中rkπj(c)�1+Xπj,c，其中Xπj,c是具有参数�Pπφ−1j(1),j,Pπφ−1j(2),j,∙∙∙,Pπφ−1j(φj(c)−1),j�的泊松二项式随机变量。每个元素对应于SW(π) :=c ∈C j ∈Jfc(j)дj(c)v 1 +c′∈Aj(c)fc′(j)eTj Mπc′v eTj Mπc v(8)SW(π) =c ∈C j ∈Jfc(j)eTj Mπc v дj(c)E v rkπj (c)≥�c ∈C�j ∈J�fc(j)eTj Mπc v�дj(c)v �E�rkπj (c)��=�c�jfc(j)дj(c)v 1 +�c′ Aj cfc′(j)eTj Mπc′v eTj Mπc v(9)maximizeMπC :={M πc }c∈C c ∈C j ∈Jfc(j)дj(c)v 1 +c′∈Aj(c)fc′(j)eTj Mπc′v eTj Mπc vs. t.1T Mπc = 1T , Mπc 1 = 1, ∀c ∈ C(10)CCC1T Sc = 1T ,Sc1 = 1, ∀c ∈ C, SC = {Sc }c ∈C;MπC ← (1 − ηt )MπC + ηtS∗Cend3330WWW '22，2022年4月25日至29日，虚拟活动，法国里昂，Yi Su，Magd Bayoumi和Thorsten Joachims0对于候选人c'∈Aj(c)申请雇主j的概率，我们有：0P(rkπj(c) = k) = �0U∈Fk−1(j,c)0s∈UPπs,j�0r∈Aj(c)\U(1−Pπr,j)(7)0证明.固定任意的随机排名策略π，对于雇主j和候选人c'，我们用Yπc',j表示候选人c'被雇主j录0申请给雇主j，并且很容易看出Yπc',j是一个参数为P(Yπc',j=1)=Pπc',j的伯努利随机变量。此外，候选人c在雇主j的列表中的排名是1+具有更高相关概率的候选人数量（即集合Aj(c)中的候选人数量），并且0应用于雇主j的候选人c，其中rkπj(c)D�1+�φj(c)−1l=1Yπφ−1j(l),j。然后0很容易看出，独立伯努利试验的和（但不一定是相同分布的）遵循具有概率�Pπφ−1j(1),j,Pπφ−1j(2),j,∙∙∙,Pπφ−1j(φj(c)−1),j�的泊松二项式分布，以及0根据公式7，可以很容易地得出PMF。□0根据引理4，很容易看出rkπj(c)的分布的PMF涉及n!/((n−l)!l!)个求和项（其中n=|Aj(c)|，l∈{1,∙∙∙,φj(c)−1}），这带来了大量的计算负担。虽然文献中存在递归公式[32]，但是由于Pπc',j相对于π（或其MπC）的复杂形式，这些概率的处理会带来重大挑战。为了避免这种情况，我们改为优化对原始目标SW(π)的以下下界，它只需要对考察函数进行轻微的条件，并且计算和优化都更加容易。0定理5.如果考察函数v(∙)是凸函数，则下式是随机排名策略π的社会福利目标的下界：0证明。该证明基于v的凸性和泊松二项随机变量期望的简单形式。0不等式来自于凸函数v(∙)的Jensen不等式。最后一个等式基于rk π j (c )的期望。□0值得注意的是，v的凸性并不具限制性，因为大多数常用的考试模型，如v(x)=1/x和v(x)=1/log2(1+x)，都满足这个条件。现在我们准备制定主要的优化问题，该问题在每个候选人的双重随机矩阵集合上优化可行的社会福利感知目标SW(π)。0可以使用多种方法来优化方程(10)。一种选择是投影梯度下降，其中任何正矩阵到双重随机矩阵集合的投影可以通过Sinkhorn-Knopp算法[35,40]计算，该算法已知可以将任何非负矩阵的KL散度最小化为Birkhoff多面体[40]。另一种选择是条件梯度下降。由于双重随机矩阵集合是凸集，我们可以利用任何凸优化求解器高效地找到下降方向。在我们的实验中，我们使用Frank-Wolfe方法（算法1）。对于特定的考试函数，还存在更专门的算法。例如，对于v(x)=1/x，方程(10)中的优化问题变为可以通过迭代的凸凹过程进行优化的分数规划。0算法1：通过Frank-Wolfe进行社会福利优化0结果：双重随机矩阵：M π C输入：相关性f_c(∙)和д_j(∙)，考试函数v(∙)，停止准则ϵ，时间步长T，学习率η_t；初始化M π c=11T/|J|，�c∈C；for t=0,1, ..., T do04 实验0在本节中，我们通过实证评估我们方法的几个关键属性。我们首先在合成数据上进行实验，这样可以使我们能够改变双边市场的属性，以探索该方法的鲁棒性。此外，我们还对真实世界的数据集进行了评估，以验证外部有效性，包括来自约会平台的基准数据集和我们构建的虚拟会议网络推荐系统的新数据集。04.1 合成数据分析0为了检验我们的方法在不同特征的匹配市场上与基准线相比的表现，我们创建了以下合成数据集。我们构建了具有n个雇主和1.5n个求职者的匹配市场，以避免不现实的对称性，其他程度的不对称性也可以在这里使用。在最简单的情况下，我们通过从[0,1]中独立均匀抽取生成相关概率¯f_c(j)和¯д_j(c)。我们将其称为“随机”设置，但也考虑了更多的结构偏好。一种结构是对某些雇主和候选人的拥挤。为了创建一个具有拥挤的环境，我们以任意顺序对雇主和候选人进行排名，并将它们命名为j_1, j_2, ..., j_|J|和c_1, c_2,...,c_|C|。对于候选人方面的相关性，我们在[0,1]中线性插值相关概率，并定义˜f_c(j_i)=1−i−10|J|-1对于所有c都是相同的，以便固定雇主的相关性对所有候选人都是相同的。对于雇主方的相关性，我们同样取˜дj(ci) = 1 -(i-1)/|C|-1对于所有j。为了调整拥挤程度，我们将随机设置和完全拥挤设置的凸组合参数λ：fc(j) := (1 - λ)¯fc(j) + λ˜fc(j)和дc(j) := (1 -λ)¯дc(j) + λ˜дc(j)。如果不6080100120140160180200220126.2143.8159.5167.465.1104.5106.5128.4106.9131.0135.8152.710020030040050060070047.862.784.4106.9131.0135.8152.7639.2669.7637.6673.72020010020030040018.721.120.823.250.761.461.968.9106.9131.0135.8152.7220.1274.3295.4332.600.516080002040608000156.3199.9184.1198.5128.7166.6156.3173.5106.9131.0135.8152.795.0105.0112.3134.292.192.178.1118.23340为匹配市场中的推荐优化排名 WWW '22，2022年4月25日至29日，虚拟活动，法国里昂0类似的反向随机0两侧相关性的非对称水平01/x 1/(ex) 1/(x+1) 1/log(x+1)0考察函数0市场规模0拥挤0预期匹配数量0Naive-Relevance Ranking Reciprocal-Relevance Ranking LP Baseline Ranking Social-Welfare Ranking0图2：合成数据集的结果。参数为(λ = 0.5，随机，v(x) = 1/x，n = 100)，除非另有说明。标准误差在10^-2数量级上，图中不可见。0除非另有说明，我们在实验中使用 λ = 0.5，市场规模为 n =100，考察函数 v(x) = 1/x适用于所有候选人和雇主。我们通过原始社会福利目标 SW(π)来衡量各种排名策略的质量，我们使用10000次蒙特卡洛模拟匹配市场交互过程来估计这一目标，该过程在第2节中描述。我们模拟这个过程10次并报告平均结果。我们将我们的社会福利排名与以下基线进行比较。Naive-Relevance Ranking根据每个候选人 c 的单向相关性fc(j) 对雇主进行排名。Reciprocal-RelevanceRanking根据每个候选人 c 的互相关概率 fc(j)дj(c)对雇主进行排名，表示一种启发式目标，考虑到匹配的互相性，但忽略了候选人之间的依赖关系。文献中最接近的问题设置是在在线约会平台上选择一组用户进行推荐。虽然这种方法只计算集合，但我们使用计算出的用户被包含在推荐集合中的概率将解转换为排名。我们将其称为LP BaselineRanking。这个基线依赖于