一句话总结

来自哈佛大学的工作研究具有单位供给卖家和单位需求买家的双边市场中的收益最优匹配问题，并证明即使每个买家在线下最多知道两个卖家，平台的问题仍然是 NP-hard；同时，在买家对所有卖家估值相同且每个买家只有一条线下卖家边的特殊情形下，论文给出了一个多项式时间算法。

核心贡献

• 论文将双边市场中的平台推荐建模为：把线下交易机会表示为二分图中的边，并将推荐交易的收益定义为竞争均衡价格的固定百分比，其中卖家具有单位供给，买家具有单位需求。

• 论文表明，即使每个买家最多只有两条线下卖家边，选择收益最大化的推荐仍然是 NP-hard。

• 论文提供了一个多项式时间算法，可在同质商品情形下最优求解收益最大化匹配问题，该情形中所有买家对卖家的估值相同，且每个买家只有一条线下卖家边。

引言

双边平台面临一个困难的推荐问题，因为选择展示哪些卖家可能改变价格、消费者结果和平台佣金。推荐价格较低的卖家可能帮助买家找到更好的交易，但可能降低平台收益；推荐价格较高的卖家可能提高佣金潜力，但也可能导致交易流失到线下替代选择。关于竞争均衡网络、平台设计和推荐系统的先前工作，尚未完全刻画这样的情形：平台战略性地创建交易边，而市场出清价格在整个市场中相互作用。作者将买家和卖家建模为二分图，让平台为每个买家和卖家至多添加一个新的交易机会，并表明在一般情形下，选择要添加哪些边以最大化收益在计算上是困难的。他们还识别出一个可处理的同质商品设定，并开发出高效算法，从而澄清收益最优匹配问题在何处可解、在何处变得复杂。

方法

作者将市场建模为双边匹配环境。形式上，市场由二分图 $G = (B, S, E)$G=(B,S,E) 表示，其中 $B = \{b_1, \ldots, b_n\}$B={b1​,…,bn​} 是具有单位需求的买家集合，$S = \{s_1, \ldots, s_m\}$S={s1​,…,sm​} 是具有单位供给的卖家集合，$E$E 是可行交易边集合。买家 $b_i$bi​ 只有在 $(b_i, s_j) \in E$(bi​,sj​)∈E 时才能与卖家 $s_j$sj​ 进行交易。每条边携带一个估值权重 $v_{ij}$vij​，表示买家 $b_i$bi​ 对卖家 $s_j$sj​ 商品的价值评估。市场通过竞争均衡出清，这对应于 $G$G 上的一个最大权重匹配，以及支撑该均衡的商品价格 $p_j$pj​。假设卖家在保持均衡的同时提取最大剩余，因此价格定义为

其中 $W(\cdot)$W(⋅) 表示最大权重匹配的总权重。

为刻画平台的作用，市场被分解为一个现存世界图 $G_w = (B, S, E_w)$Gw​=(B,S,Ew​) 和一组平台边 $E_p$Ep​，其中 $E_p \cap E_w = \varnothing$Ep​∩Ew​=∅。世界边表示平台外可获得的交易机会，而平台选择额外的推荐边以实现平台内交易。在完全知晓买家估值和现存世界图的情况下，平台选择 $E_p$Ep​ 以及一个最大权重匹配，以最大化通过平台边售出的商品所产生的总收益。所得收益目标在概念上可写为通过新增平台边匹配的卖家均衡商品价格之和。

分析表明，这一平台干预问题在一般情况下具有计算困难性。即使在高度受限的估值结构下，甚至当部分买家仅有有限的外部选择时，它仍然是 NP-hard。为获得可处理设定，作者研究买家具有同质估值的情形，即对每个卖家 $j$j 均有 $v_{ij} = v_i$vij​=vi​，且每个买家至多有一条现存世界边。在这些假设下，干预结构可以更清晰地刻画。每个卖家定义一个卖家子图，包含该卖家以及通过世界边与它相连的所有买家。在按每个子图内的最高买家价值对这些卖家子图排序后，收益最优的平台边集合将子图连接成连续的环以及至多一条链。这些环的长度至多为三，链连接到一个环上。如下图所示：

该示例展示了同质估值情形下的结构分解。黑色链接表示现存世界机会，粉色链接表示由收益最优策略选中的平台边。在此类市场中，最优结果中的每笔交易都可以仅由平台边支撑，所得的环和链排列刻画了新增推荐如何重塑竞争均衡。

基于这一结构，算法将优化归约为对可能的环锚点进行一系列局部搜索。对于每条长度至多为三的候选连续环，算法固定该环，并将相关卖家子图从考虑中移除。然后，算法通过动态规划计算通过将剩余子图的初始连续段连接成环所能获得的最佳收益。它还计算将剩余子图后缀连接成链所能实现的收益。该固定锚点对应的最佳收益为

其中 $DP[i]$DP[i] 是前 $i$i 个子图基于环的最优收益，$R[i]$R[i] 是后续子图基于链的收益。对所有可能的固定环锚点重复该过程可得到全局最优解，整体算法在受限同质估值设定下运行时间为 $O(n^2)$O(n2)。