在线约会中的纳什社会福利与效率公平的实现

Online dating applications are more and more ubiquitous and be-coming an integral part of young adults’ everyday lives. Theseapplications 1, such as Coffee Meets Bagel [1], Tantan [2], and Tin-der [3], provide platforms for people to make new friends withvarious purposes including meeting new friends and developingpersonal or romantic relationships. The report in [4] shows thatthe percentage of online dating users in the USA triples (i.e., from5% to 15%) from 2013 to 2016. Tinder consistently ranks as one ofthe top 10 grossing apps in Apple’s online store, with more than50 million active users [5]. It is also reported that Coffee MeetsBagel has created 997 million matches and more than 50, 000 happycouples in long-standing relationships [6]. Tantan claims 60 millionregistered users, of which 6 million are active on a daily basis [7].Behind the great success of the online dating apps is the doubleopt-in design, which provides the users with appealing online dat-ing experiences: For instance, all of the above three apps present4290当在线约会遇上纳什社会福利：实现效率和公平0YongzhengJia清华大学jiayz13@mails.tsinghua.edu.cn0Xue LiuMcGill大学xueliu@cs.mcgill.ca0WeiXu清华大学wei.xu.0@gmail.com0摘要0移动约会应用程序，如Coffee MeetsBagel，Tantan和Tinder，已成为年轻人结识新朋友和发现浪漫关系的重要途径。从系统设计师的角度来看，为了在这些应用程序中实现更好的用户体验，我们应该同时考虑约会市场的效率和公平性，以增加所有用户的整体满意度。为此，我们研究了在线约会市场的边际收益递减性质（即由次模性捕捉），以及市场效率和公平性之间的纳什社会福利的权衡。我们进一步设计了有效的在线算法来改进这些应用程序。我们通过对真实数据进行充分的理论分析和实证研究来验证我们的模型和算法，并展示了我们的算法可以显著改善在线约会应用程序的生态系统。0ACM参考格式：Yongzheng Jia，Xue Liu和WeiXu。2018。当在线约会遇上纳什社会福利：实现效率和公平。在WWW2018：2018年网络会议上，2018年4月23日至27日，法国里昂。ACM，美国纽约，10页。https://doi.org/10.1145/3178876.318610901 引言01由于这些约会应用程序都是基于手机的，我们将在本文的其余部分中使用“应用程序”作为“应用程序”的缩写0本文发表在知识共享署名4.0国际许可证（CC BY4.0）下。作者保留在个人和公司网站上传播作品的权利，并附上适当的归属。WWW2018，2018年4月23日至27日，法国里昂，©2018IW3C2（国际万维网会议委员会），根据知识共享CC BY 4.0许可证发布。ACM ISBN978-1-4503-5639-8/18/04。https://doi.org/10.1145/3178876.31861090潜在匹配与用户可以在应用程序中滑动的个人资料卡片相结合。每个个人资料卡片包括一组照片和一个可选的基于文本的传记。每个用户有两个主要活动：通过（即“向左滑动”）和喜欢（即“向右滑动”）个人资料卡片。这些约会应用程序只在双方互相喜欢（即“匹配”）时通知用户。只有匹配的用户才能开始对话。双向选择的设计将向另一个人介绍自己这个复杂、焦虑且有时尴尬的行为转变为简单而有趣的体验[8]。这种设计激励用户发现更多个人资料并获得更多匹配。为了在这些新兴约会应用程序中实现更好的用户体验，系统设计师应同时考虑约会市场的效率和公平性。效率意味着应用程序应在市场上尽可能多地进行匹配。这类似于最大化社会福利。与此同时，我们还应考虑约会市场的公平性，这在应用程序的设计者中经常被忽视。大多数约会应用程序遵循“免费增值”策略，即基本功能对所有用户免费，而付费用户获得高级服务。高级服务的例子包括TinderBoost，Tinder Plus和Coffee Meets BagelWoo。约会应用程序更倾向于付费用户。然而，这些偏好可能会引入不公平，导致非付费用户更难获得匹配。例如，使用Boost的人将比不使用Boost的人有更多的机会被展示给其他人，从而获得更多的匹配。更“公平”的情况是，应用程序应帮助活跃的付费用户和非付费用户获得一定数量的匹配。对于系统设计师来说，保持非付费用户的一定数量的匹配非常重要，因为这会导致更高的用户留存率：我们根据在线约会应用程序的数据分析了用户的留存率和匹配数量之间的相关性。我们发现，匹配数量较少的用户（通常是“不太有吸引力的用户”）通常感到沮丧，因此他们倾向于变得不活跃，留存率较低（我们在第3.2节中展示了详细的分析）。每个在线约会应用程序都是由许多因素相互作用而形成的复杂生态系统。为了更好地理解上述公平性问题，我们将这些因素分为两类：不可控因素（主要由用户的吸引力决定）和可控因素（由应用程序中使用的策略和算法引起）。对于不可控因素，由于人们的外貌吸引力，存在一种自然和固有的不公平。此外，据报道[9]，无论自己的外貌如何，用户都倾向于追求有吸引力的用户。这种倾向导致一小部分有吸引力的用户比其他人更容易获得匹配。对于可控因素，Tinder和其他一些在线约会应用程序可以通过向另一个用户显示或不显示用户的个人资料卡片来控制每个推荐。此外，约会应用程序0跟踪：社交网络分析和图算法用于Web WWW 2018，2018年4月23日至27日，法国里昂4300也可以控制对付费用户的特权，以在收入和约会市场的公平之间进行权衡。在这项工作中，我们只关注基于经济模型和在线算法设计来改善在线约会生态系统的效率和公平的可控因素的讨论。我们表明我们的算法可以显著提高在线约会市场的效率和公平性，并且在线约会应用程序可以使用它们来缓解不可控因素的影响，以提供更好的用户体验。现有的研究，如[10][11]和[12]观察到Tinder上匹配的不平衡分布，暗示了公平性的重要性。然而，他们没有提出解决这个问题的可行解决方案。设计和实施既高效又公平的在线约会市场是具有挑战性的。要克服这个问题有三个关键挑战。首先，效率和公平的目标通常不一致。在一个系统框架内，很难提出适当的性能度量来权衡这些目标。其次，应用程序部署的算法应该运行足够快，并且能够扩展到庞大的用户活动。例如，Tinder每天处理数十亿个事件，生成的数据量达到了TB级[8]，因此慢算法会严重降低用户的体验。最后但并非最不重要的是，算法应该是在线的，以处理不可预测的用户活动。在线要求很重要，因为很难预测用户何时开始/停止滑动；他们将在多少个个人资料卡上滑动。此外，他们对匹配的偏好也可能随时间变化。据我们所知，这是第一项基于数据驱动研究的广义模型，旨在实现高效和公平的在线约会市场，并旨在设计快速的在线算法：首先，我们为约会市场提出了一个系统化和广义的模型，以权衡效率和公平之间的目标。我们根据在线约会应用程序的数据，通过用户的保留率和匹配数量之间的相关性找到匹配目标，并发现在线约会市场的递减边际回报特性。我们进一步为不同用户群体设定匹配目标，并定义实用函数来衡量约会应用程序中每个用户的满意度。然后，我们提出了最大化市场整体满意度（即福利）的目标函数，该函数表示效率和公平性。其次，通过发现当用户获得越来越多的匹配时递减边际回报，我们将问题减少到在线次模型福利最大化问题。然后，我们提出了一种有效的在线算法来解决这个问题。02-竞争性在线贪心算法来解决问题。我们进一步表明，在理论和实践中，在线贪心算法是有效的。第三，我们将纳什社会福利调整到在线约会市场中，这提供了效率和公平之间的自然平衡。我们进一步将最大化纳什社会福利的问题减少到次模型福利优化的特殊情况，并调整我们的在线算法来解决问题。最后但并非最不重要的是，我们通过使用来自数据的数据驱动的实证研究来评估我们模型的性能。0一个在线约会应用程序。为了实现这个目标，我们定义了广义的性能度量，并讨论了适当的实用函数和参数的选择。更有趣的是，我们在评估纳什社会福利的性能时发现了一个均衡点。这个均衡点表示了一个市场配置，使得非付费用户和付费用户都满意。最后，我们通过与数据集的分布进行比较，评估应用纳什社会福利的改进。结果显示，使用纳什社会福利在效率和公平性方面都有显著改善。本文的其余部分组织如下：首先，在第2节中讨论相关工作，并在第3节中提出问题模型。接下来，我们将问题减少到在线次模型福利最大化问题，并提出一种有效的在线算法来解决它。然后，我们讨论如何将纳什社会福利应用于在线约会市场的背景中。最后，我们根据数据驱动的研究结果，展示了我们方法的有效性。在第7节中，我们总结了本文，并提出了未来工作的开放问题。02 相关工作0在线约会市场吸引了社交网络、通信、经济学甚至心理学、社会学和人类学等广泛的跨学科研究兴趣。0在线约会应用。近年来，学术界和社交媒体上出现了许多关于在线约会应用的研究[6][10]。研究人员研究了用户的动机[13][14]、社会影响[15][16]和在线约会的隐私问题[17]。他们还调查了男性和女性之间的性别差异，包括不同的选择策略[18][12]，以及对话行为[19]。一些研究使用经济模型来分析约会市场上的用户行为，[20]研究了一种经济匹配模型来解释匹配模式并评估匹配的效率。[9]的作者通过数据驱动的研究分析和预测了在线约会中的用户偏好。一些文章展示了在线约会中匹配的不平衡分布，并表明对于一些不太有吸引力的男性来说，很难找到匹配[10][11]。[12]的作者进一步提出了在线约会市场中的“反馈循环”假设：男性被迫在希望找到匹配的情况下变得不太挑剔，而女性则变得更加挑剔，因为她们知道她们喜欢的任何男性都有很高的概率会匹配成功。所有这些发现都表明公平性是在线约会应用中需要考虑的一个关键因素。0双边市场：模型和算法。在线约会市场是典型的双边（匹配）市场[21]。为了更好地理解在线约会市场的模型和挑战，我们将其与其他双边市场进行比较。其中一个是研究充分的在线顺风车市场（如Uber和Lyft）[22][23][24]。在线顺风车市场比在线约会市场简单得多，它基于集中匹配设计，即市场制造者（即平台）决定所有的匹配。然而，在在线约会市场中，平台只通过展示个人资料卡片来推荐潜在的匹配，用户的所有（滑动）活动都无法被平台控制。0主题：社交网络分析和网络图算法 2018年WWW会议，2018年4月23日至27日，法国里昂a(t)m =4310另一个类似的双边市场是在线广告市场，如谷歌的Adwords[25]。[26]的作者总结了在线广告市场的各种模型和基本在线算法。[27]提出了设计在线广告分配算法以实现效率和公平的理论研究。方法学。子模性福利最大化是一种资源分配的框架，其边际效用递减。现有的研究调查了复杂性[28][29]、离线算法[30][31]和在线算法[26][32][33][34]。纳什社会福利是在效率和公平之间权衡的一个合理标准，最早由约翰∙纳什提出[35]。最近，研究人员在[36][37][38]中找出了它的性质。他们还设计了离线算法，在不同的设置中最大化纳什社会福利[39][40][41][42]。我们将在第4和第5节中讨论更多方法的细节。03 市场、观察和模型0在本节中，我们根据我们从数据驱动的研究中得出的结果，介绍在线约会应用中每个用户的效用模型（即满意度程度）。我们首先介绍在线约会市场配置的基础知识。然后，我们使用来自一款热门在线约会应用的数据分析了用户的留存率与匹配数量之间的相关性，并从我们的结果中发现了匹配目标（即在一段时间内预期的匹配数量）。我们进一步通过用户的匹配目标和实际匹配来定义每个用户的效用。最后，我们制定了我们的目标函数，该函数最大化了所有用户的总满意度。03.1 在线约会的市场配置0在线约会市场由两个群体组成，我们称之为男性和女性。两个群体在市场中的行为方式相同。在本文中，我们只考虑两个群体之间发生的匹配。我们考虑一个拥有 M 个男性和 F个女性用户的约会市场。我们采用约定 [ X ] = { 1 , 2 , ... , X }来表示本文中的 X 个元素的集合，例如 [ M ] = { 1 , 2 , ∙ ∙ ∙ , M }是所有男性的集合，[ F ] = { 1 , 2 , ∙ ∙ ∙ , F }是所有女性的集合。为了简化讨论，我们将时间分为固定长度的时间段，称为“轮次”。如果用户在第 t轮至少滑动一次，则认为用户在第 t轮处于“活跃”状态。请注意，在我们的大部分讨论中，由于两个群体在大多数情况下是对称的，没有损失一般性，我们将重点放在为女性推荐男性的算法上，而另一边的情况相同。我们还将第 t轮中滑动次数（或查看的个人资料数）定义为用户的（滑动）容量。我们分别将男性 m 或女性 f 在第 t 轮的容量表示为 c ( t ) m 和 ¯ c (t ) f。0估计实现的匹配。为了估计每个用户实现的匹配数量，我们仔细研究了双向选择模型下的匹配过程。该应用程序有一个机制来估计女性 f在第 t 轮上是否会向男性 m右滑（即喜欢）的概率。我们将这个估计表示为 ¯ p ( t ) f , m（反过来也是 p ( t ) m , f ），对于任意 m ∈ [ M ] 和任意 f ∈ [ F]。在实践中，协同过滤是一种预测概率的好算法。预测算法的细节超出了本文的范围。0图1：（归一化的）留存率与匹配数0本文的范围是我们只将预测的概率作为输入。我们进一步定义第 t轮的匹配得分为两个方向上预测（喜欢）概率的乘积，即 w ( t ) m ,f =0p ( t ) m , f ∙ ¯ p ( t ) f ,m。直观地说，匹配得分捕捉了一对用户之间相互喜欢的程度。当我们在第 t 轮向女性 f 推荐男性 m 时，m 和 f 之间实现匹配的概率是w ( t ) m , f。决策变量是在线约会应用程序是否应该在第 t 轮向 f推荐 m，表示为二进制变量 x ( t ) m , f ∈ { 0 , 1 }，对于任意 m ∈ [M ]，任意 f ∈ [ F ]。总之，我们估计男性 m 在第 t轮实现匹配的期望如下：0f ∈ [ F ] w ( t ) m , f ∙ x ( t ) m , f � m ∈ [ M]。 (1)03.2 寻找匹配目标0留存率与匹配数。为了发现在线约会市场的洞察力，并探索匹配数如何影响用户对在线约会的满意度。我们分析了留存率与每周匹配数之间的相关性。在实践中，留存率是一个可靠且广泛使用的指标，为我们提供了用户满意度的定量测量，因为如果用户满意，他往往会继续使用该应用程序。我们收集了一个热门在线约会应用的用户两周的活动数据。对于每个用户，我们统计了他在第一周的匹配数，并将他的留存情况表示为一个二进制变量，即他在第二周是否打开应用程序，其中 1 表示“是”，0表示“否”。那么问题是：在第一周内获得一定数量的匹配的情况下，用户在第二周使用该应用程序的概率是多少（即留存率）？图1显示了男性和女性用户的（归一化的）留存率与（归一化的）匹配数之间的相关性。横轴是用户在第一周内收到的（归一化的）匹配数，纵轴是（归一化的）平均留存率3（即他们在第二周是否打开应用程序的概率）。02在本文中，一些观察是基于在线约会应用的数据。然而，为了不透露任何与业务相关的细节，所有呈现的数据都经过了归一化处理。3在本文的剩余部分，我们将使用“匹配”作为“（归一化的）匹配”的缩写，将“留存率”作为“（归一化的）留存率”的缩写。0Track：社交网络分析和网络图算法WWW 2018，2018年4月23日至27日，法国里昂4320用户与相应匹配数的平均留存率（例如，第一周和第二周）之间的关系。由于数据的机密性，我们通过将每个平均留存率除以没有匹配的男性的平均留存率来对留存率进行归一化。图1中的两条实线曲线说明了留存率与匹配数之间的相关性。我们将x轴（即匹配数）的范围限制在{0，1，2，...，20}，因为当每周匹配数超过20时，男性和女性的曲线保持平坦。此外，两条垂直虚线显示了男性和女性的每周匹配数的中位数。根据数据，我们根据男性和女性的留存率与每周匹配数之间的关系得出以下关键观察：0•当男性用户在一周内获得少于7次匹配时，他的留存率迅速增加。当男性用户获得超过7次匹配时，留存率保持稳定。•男性用户的平均匹配次数约为5次，中位数为1次（即一半的男性在第一周内获得的匹配次数少于1次）。如果我们将男性的匹配次数从0提高到7，留存率将增加两倍。如果我们将其从1提高到7，留存率也会提高65%，这表明帮助每个男性用户每天获得一次匹配，将使一半的男性的留存率增加65%。同时，将男性的匹配次数从中位数水平提高到平均水平，也将使他的留存率增加49%。•然而，提高女性的匹配次数的效果并不显著。女性用户的平均匹配次数约为15次，中位数为7次。中位数（即7次）之后，女性曲线的斜率要温和得多。此外，即使我们将女性的匹配次数从7提高到20，留存率也只会增加27%。0根据上述观察，我们得出以下结论：1）对于男性和女性来说，匹配越多，留存率越高。2）我们发现，男性的留存率在匹配数量方面比女性更敏感，因为女性的匹配数量更乐观。3）将每个男性的每周匹配数提高到约7次（即我们称之为男性匹配的“魔法数字”）将显著提高男性的留存率。同时，如果男性获得的匹配数超过了魔法数字，那么他的留存率的提高就相对较小。4）男性和女性的留存曲线都是凹的，表明当用户逐渐获得更多匹配时，边际回报递减，我们将在第4节中讨论细节。5）我们的观察还说明了为什么我们更关注男性的匹配数量，即使我们从当前水平大幅提高女性的匹配数量，留存率的提高也是适度的。为了给观察到的魔法数字在后续的理论研究中提供正式定义，我们引入了男性匹配目标的概念如下：0对于每一轮，一天为一个周期，或者如果我们考虑用户获取匹配的季节性因素，可以将每一轮的长度设定为一周。这是因为在线约会应用的匹配分布在一周的不同天数上有所变化，周末男性和女性用户在线上的时间比工作日更多。对于一个普通的非付费用户，系统可以将他的匹配目标设定为每天一次匹配（或每周7到8次匹配），也就是说，非付费用户每天获得一次匹配就会感到满意。对于付费用户（例如TinderBoost用户）或新用户，系统可以为他设定更高的匹配目标（例如每天2到4次匹配），因为付费用户应该获得更多的匹配，而新用户在开始使用应用时获得更多匹配会更有动力。实际上，我们还可以根据不同地区动态调整匹配目标，因为市场配置可能会有所不同。用户的匹配目标是系统设定的他对匹配的期望的估计。为了捕捉（男性）用户m的匹配目标与实际匹配之间的差异，我们还定义了实际匹配数a(t)m，表示m在第t轮期间的实际匹配数。我们进一步定义了（匹配）达成率r(t)m，表示实际匹配数（即a(t)m）与匹配目标之间的比率。0（即д（t）m）对于每个男性m，使得r（t）m = a（t）m0д（t）m，�m∈ [M]。03.3 问题建模0满意度和效用函数。我们用效用函数u（t）m乘以权重因子α（t）m来定义每个用户的满意度（即s（t）m）（2），其中效用函数在[0，+∞)上定义，输入为r（t）m。权重因子α（t）m用于区分不同用户的优先级。0s（t）m = α（t）m∙u（t）m（r（t）m）= α（t）m∙u（t）m� � f∈ [F] w（t）m，fx（t）m，f0д（t0�。（2）0系统中的值是固定的，因此s（t）m仅由决策变量x（t）m，f确定。为了简化模型，我们还可以进一步假设效用函数在所有回合中对不同男性是对称的，即u（t）m（∙）�u（∙），�m ∈ [M]，t ∈ N+。目标。我们的目标函数是最大化男性的加权满意度（即（3）），受到每个女性的（滑动）容量约束（即（4a））和每个男性的（滑动）容量约束（即（4b））的限制：0max：0m ∈ [M] s（t）m（3）0s.t.，�0m ∈ [M] x（t）m，f ≤ ¯c（t）f，�f ∈ [F]；（4a）0f ∈ [F] x（t）m，f ≤ c（t）m，�m ∈ [M]；（4b）0x（t）m，f∈{0，1}，�m ∈ [M]，�f ∈ [F]。（4c）0在实践中，当我们设计推荐男性给女性的算法时，我们可以忽略每个男性容量的约束（即（4b））。这是因为在在线环境中，仅通过观察女性的滑动活动很难估计每个男性的容量c（t）m，并且如果男性没有获得足够的匹配，他倾向于自发增加他的（滑动）容量。然而，即使我们添加了约束（4b），我们在第4节中的在线算法仍然可以通过应用[32]中的方法来工作。正如我们之前讨论的，我们想提到，本文中的镜像模型和推荐女性给男性的算法在理论上是正确的，尽管在实际中对保留的影响较小。在下一节中，为了简洁和实用的考虑，我们只讨论男性向女性的推荐算法。0研讨会：社交网络分析和Web上的图算法WWW 2018年4月23日至27日，法国里昂male’s capacityc(t)m by only looking at the females’ swiping activitiesin an online setting, and a male tends to spontaneously increase his(swiping) capacity if he has not get enough matches. However, eventhough we add constraint (4b), our online algorithm in Section 4still works by applying the methodologies in [32].As we discussed before, we want to mention that the mirroringmodel and algorithm of recommending females to males throughoutthis paper is theoretically correct, though practically it impactsthe retention much less significantly. In the following section, forconcise and practical considerations, we only discuss the algorithmsfor the recommendations from males to females.43304 在线子模性福利最大化0在前一节中，我们定义了问题模型，以最大化市场的整体满意度（即福利）。根据第3.2节的结果，每个用户的边际回报（即满意度）在他在某一回合逐渐获得更多匹配时逐渐减少。此外，当他的匹配数达到阈值时（例如，他几乎无法跟上与所有匹配的对话），他的效用停止增加。04.1 定义子模性0我们发现在线约会市场具有递减边际回报的特性，为了捕捉这一特性，我们在本节中引入了子模性。我们首先为每个m ∈[M]定义印象集I（t）m，表示应用程序向m推荐的女性集合：0我（t）m = {f | x（t）m，f = 1}，�m ∈ [M]。（5）0很容易发现，�I（t）m，I（t）m � [F]且I（t）m ∈ 2[F]。此外，我们在印象集上呈现了每个用户的加权效用函数（即等同于（2）），它是在2 [F]上定义的函数：0s(t)m = µ(t)m(I(t)m) = α ∙u(t)m � �0f ∈ I(t)mw(t)m,f0д(t)0对于每个m ∈[M]。（6）0然后我们给出µm的子模块性和单调性属性如下：0定义1.（单调子模块化）如果对于每个男性m ∈[M]，具有任何印象集˜I(t)m � I(t)m和一个女性f / ∈I(t)m，满足以下条件：0µm(I(t)m∪{f})−µm(I(t)m) ≤µm(˜I(t)m∪{f})−µm(˜I(t)m)。（7）0此外，我们说µ是单调子模块化的，如果另外有µm(I(t)m) ≥µm(˜I(t)m)。0回顾一下，µm(I(t)m∪{f})−µm(I(t)m)是当应用程序向m推荐一个以上的女性f后，m的边际效用，而（7）表示m的边际收益递减。此外，当m的印象集增长时，m的效用是非递减的，因此µm是单调子模块化的。由于我们的效用函数是单调子模块化的，我们的目标函数（3）的最大化问题变成了子模块化福利最大化问题。我们总结了离线和在线设置中的现有研究。我们进一步提出了算法1。0算法1：在线子模块化福利最大化的贪心算法 - GA01 初始化：对于每个m ∈ [M]，设置I(t)m = �。02 当女性f ∈[F]在第t轮登录应用程序时，当f继续滑动时，执行以下操作：03（a）选择男性m* ∈ [M]，使得0m* = arдmax m ∈ [M] �04（b）向f推荐男性m*，I(t)m* = I(t)m* ∪ {f}05 结束0并且我们证明了它在我们的应用程序中是有效和实用的，特别是在在线设置中。04.2 解决方案：离线和在线0我们首先描述在线约会应用程序的离线和在线设置，当我们向女性推荐男性时。在离线设置中，我们提前知道所有输入值，如w(t)m,f,¯c(t)f和µ。而在在线设置中，当女性f到达并带有一部分输入值时，应用程序会实时向每个女性f提供推荐。一些值（例如¯c(t)f,w(t)m,f）直到女性f登录应用程序并开始滑动时才会被揭示，而不知道女性何时变得活跃/非活跃，或者她随时间的偏好。为了解决子模块化福利最大化问题，有一种直观但高效的贪心算法，每次我们推荐一个男性m给f，使得边际收益最大，然后更新他的印象集。该算法可以解决离线和在线两种情况。我们在算法1中介绍了在线贪心算法。通过将其与离线和在线设置的现有结果进行比较，我们证明了算法1在理论和实践中都是有希望的。0离线设置。在离线设置中，子模块化福利最大化问题在不能更好地近似于1 - 1 e[28]的情况下是NP难的，而[30]在值预言模型中提供了一个算法来达到这个界限。[29]证明了超过1 - 1的界限是不可能的。0该界限需要指数级的通信。[31]提出了一种随机局部搜索算法，比[30]更简单，也能达到该界限。然而，这些算法的复杂性很高，因此在现实生活中不实用。0在线设置。在在线设置中，[32]表明算法1可以达到1的界限。0对于在线子模块化福利最大化问题，即使在对手输入顺序下，也没有（随机）算法能够达到优于1的竞争比。此外，在[33]中，作者证明了没有（随机）算法能够达到优于1的竞争比。0对于在线子模福利最大化问题，除非NP=RP，否则算法1是一个坚实的在线算法，理论上保证了紧密的1-2竞争性界限。0对于任何子模函数µm，具有2竞争性界限。0时间复杂度。然后我们分析算法1的时间复杂度。对于每个女性f的推荐，算法经过M次迭代选择最佳候选者，因此对于女性f的所有推荐，它需要M∙¯c(t)f次迭代。如果我们考虑所有女性f∈[F]，则算法1的总体时间复杂度为O(M¯C(t)F)，其中¯C(t)F是...0Track：社交网络分析和Web上的图算法WWW 2018，2018年4月23日至27日，法国里昂Track: Social Network Analysis and Graph Algorithms for the WebWWW 2018, April 23-27, 2018, Lyon, France4340考虑到所有女性f∈[F]，则算法1的总体时间复杂度为O(M¯C(t)F)，其中¯C(t)F是...0对于[F]中所有女性的总容量，使得¯C(t)F=�f∈[F]¯c(t)f。因此，在应用算法1时，速度足够快且实用。05 纳什社会福利0为了进一步权衡效率和公平性，我们将纳什社会福利应用于在线约会市场，这在效率和公平性之间提供了一种自然的平衡。05.1 定义和性质0公式（8）给出了在线约会市场纳什社会福利的制定：将推荐分配给最大化用户效用的几何平均值（即s(t)m）。0NSW([M])=�Πm∈[M]s(t)m�10M.（8）0这个想法可以追溯到约翰∙纳什在[35]中对于协商问题的著名解决方案。最近，纳什社会福利被广义（幂）均值函数[38]的一个家族捕捉，其中指数τ：0Aτ([M])=�1M∙�0m∈[M](s(t)m)τ�10τ.（9）0特别地，NSW([M])对应于A0([M])，当τ趋近于零时，它是Aτ([M])的极限。为了研究纳什社会福利在效率和公平性之间的权衡，我们扩展了其性质的处理。Aτ([M])还包括另外两个经过深入研究的函数：（i）当τ→−∞时，对应于平等主义（即最大最小）目标；（ii）当τ=1时，对应于功利主义（即平均）目标。它们分别代表了极端公平性和极端效率。然而，τ→−∞可能导致较大的低效性，使得约会市场的总匹配可能很差。而τ=1则忽视了一些男性可能感到不满意，导致他们很难找到匹配。纳什社会福利处于两个极端之间，实现了自然的平衡。这是因为最大化几何平均值会导致更加平衡的推荐（即公平性），同时也考虑了效率。此外，[36]提出了纳什社会福利的博弈论性质，并证明了具有最大纳什社会福利的每个分配都是帕累托最优（表示效率）和EF1（即Envy-Freeness up to OneGood，表示公平性）。05.2 最大化纳什社会福利0将最大化NSW([M])简化为(3)。重新审视(2)中s(t)m的定义，为了简化，我们首先为所有用户设置统一的权重参数，使得α(t)m=1和s(t)m=u(t)m(r(t)m)=r(t)m，�m∈[M]。然后引入对数效用函数˜s(t)m=˜u(t)m=loд(r(t)m)。因此，最大化纳什社会福利（即(Πm∈[M]s(t)m)1M）0通过使用˜s(t)m（即最大化�m∈[M]˜s(t)m）等价于目标函数（3）。由于˜s(t)m=loд(s(t)m)，r(t)m≥0且M是常数，所以这个简化是成立的。0为了考虑不同的权重参数，我们设置 s ( t ) m =  u ( t ) m ( r ( t ) m ) =0( r ( t ) m ) α  ( t ) m  ，并引入  ˜ s ( t ) m =  α ( t ) m ∙  loд ( r ( t )m ) 和  ˜ u ( t ) m ( r ( t ) m ) =  loд ( r ( t ) m)。然后，我们还可以使用  ˜ s ( t ) m (即  � m ∈ [ M ] ˜ s ( t ) m )0每个  ˜ s ( t ) m 都是一个单调子模性效用函数，如果我们设置 s ( t )m =0( r ( t ) m ) α  ( t ) m  在 (8)中为每个用户。注意，这个设置对于现实生活中的约会应用是合理的。例如，我们设置 α ( t ) m >  1 为付费用户，α ( t ) m = 1为非付费用户，表示应用对于每个付费用户具有更高的优先级。因此，当我们在 (8)中最大化纳什社会福利时，我们倾向于首先尽可能地使 r ( t ) m对于付费用户尽可能大，因为当 α ( t ) m >  1 时，s ( t ) m的值增长更快。我们可以进一步调整 α ( t ) m来为付费用户设置不同的优先级。0效用上限。然而，如果存在一个男性 m ，使得 r ( t ) m >  1 且 α ( t) m >  1，进一步增加 r ( t ) m来最大化纳什社会福利将降低市场的公平性。为了解决这个问题并进一步提高公平性，引入效用上限是实际可行的。0通过设置 r ( t ) m = 1 当 a ( t ) m0д ( t ) m >  1，使得 s ( t ) m = ( r ( t ) m0因此，对于达到匹配目标的男性来说，为他做更多的匹配不会再改善纳什社会福利。0离线解决方案。近年来，设计近似算法来最大化纳什社会福利引起了很多研究兴趣。[ 37 ]表明，对于具有可加性效用的不可分割物品，最大化纳什社会福利是NP难和APX难的。[ 39 ]提出了离线近似算法来最大化具有可加性效用的纳什社会福利，[ 40]进一步处理了具有效用上限的情况。然而，需要注意的是，这些算法应用了Eisenberg-Gale程序 [ 44 ]来实现一个分数最优解，然后再进行精心设计的舍入算法。因此，它们都需要提前知道所有输入值（例如 w ( t ) m , f ,  ¯ c ( t ) f）并且不能直接应用于约会应用的在线环境中。0关于在线解决方案的讨论。值得注意的是，现有的研究主要研究离线解决方案，以最大化纳什社会福利，但这对于约会市场来说是不适用的，正如我们在第1节中讨论的在线算法的要求。在这项工作中，我们的贡献是基于上述的简化将纳什社会福利最大化减少到(3)，并使用算法1得到在线解决方案。在实践中，我们设置 ˜ u ( t ) m ( r ( t ) m) = loд ( ϵ  +  r ( t ) m )，其中 ϵ  = 10 − 4或其他小的值。这是因为 loд (0) =  −∞ ，如果存在一个男性 m，使得 a ( t ) m = 0，输出总是  −∞，因此算法1在初始步骤中没有改进。添加一个小的 ϵ将解决这个困境，让算法1在每次迭代中进行改进。06 数据驱动的实证研究0在本节中，我们基于上述的综合模型和技术进行评估。,F,partition the male users in [M] into two user groups, with [Mnpu]denoting the Mnpu non-paying users, and [Mpay] denoting the Mpaypaying users. We define the paying rate γ = MpayM , and we calculateγ ≈ 0.26 based on the dataset we use. We setup uniform match goalfor the male users in each group, using дpay to denote the matchgoal for each paying user all the time (i.e., д(t)m = дpay,∀m ∈ [Mpay])and дfor the match goal of each non-paying user. We set д= 7,J (t)[M] =m∈[M] amM ·� �m∈[M](a(t)m )2�(11)˜J (t)[M] =� �m∈[M] |I (t)m |�2M ·m∈[