O&SCM运营与供应链管理知识库

LATEST RESEARCH FRONTIERS / 最新研究前沿

平台设计 · 双边匹配 · 次模优化

有限的推荐名额,
如何促成更多匹配?

约会启发式算法:一种针对在线约会平台的可证明强效匹配算法

243 个原生公式 · 3 张表

FULL PAPER SUMMARY / 完整论文总结

约会启发式算法:一种针对在线约会平台的可证明强效匹配算法

《约会启发式算法:一种针对在线约会平台的可证明强效匹配算法》全文总结

The Dating Heuristic: A Provably Strong Matching Algorithm for Dating Platforms

文献信息项 具体内容
作者(原文名) Ignacio Rios (School of Management, University of Texas at Dallas,通讯作者);Alfredo Torrico (Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California)
发表期刊 Manufacturing & Service Operations Management (M&SOM),2026 年,第 28 卷第 6 期,第 1837–1855 页
发表时间与 DOI 2024 年 6 月投稿,2026 年 2 月录用,2026 年 3 月在线发表;DOI: https://doi.org/10.1287/msom.2024.1053
关键词 约会平台 (dating)、平台设计 (platform design)、匹配市场 (matching markets)、次模优化 (submodular optimization)

一、全文概要与研究背景

本文由 Ignacio Rios 与 Alfredo Torrico 合作撰写,发表于运营管理顶级期刊 Manufacturing & Service Operations Management(2026 年第 28 卷第 6 期)。研究聚焦于“精选式(curated)”在线约会平台(如 Bumble、Hinge、Coffee Meets Bagel 和 The League 等)的核心运营决策:平台在有限的 𝑇\mathit{T} 个时期内,每期应向每位用户展示哪一个有限规模的候选资料子集,以最大化整个时间范围内双方相互“喜欢”而达成的期望总匹配数。

这一动态品类优化问题面临三重核心挑战:第一,双边交互性,匹配仅在两位用户彼此看到并相互喜欢时成立,且可能跨期(顺序匹配)或同期(非顺序匹配)发生;第二,状态空间爆炸,问题本身是 NP-hard 的,平台需动态追踪海量用户的待处理喜欢列表(backlog)与过往评价记录;第三,历史依赖的行为动态,用户的过往经历(如近期匹配数、使用时长或知晓对方已喜欢自己)会显著改变其后续的喜欢概率。为此,作者构建了通用的动态双边匹配理论模型,提出了基于前瞻一步策略的整数约会启发式算法(Integral Dating Heuristic,简称 DH-int)及其多期半自适应变体 DHT,首次为该类问题建立了统一的 1 − 1𝑒\text{1 − }\frac{\text{1}}{\mathit{e}} 理论近似性能保证,并依托美国某大型在线约会平台的真实专有数据验证了算法在不同平台设计与多种历史效应下的卓越表现。

二、文章的核心贡献

相较于既有双边品类优化(如 Ashlagi et al. 2022;Aouad and Saban 2022)、约会平台实践研究(Rios et al. 2023)以及随机探测匹配文献,本文在理论建模、算法构造、性能保证与实证机制四个层面做出了突破性贡献:

  • 通用的动态双边与历史依赖理论模型:既有双边品类优化文献多局限于单向发起、顺序匹配且每位用户仅能达成单一匹配的简化设定;本文允许用户在多期内喜欢多个对象并形成多重匹配,同时兼容双向/单向发起、顺序/非顺序匹配等多种平台架构,并将一般化的用户历史向量 𝜎ℓ𝑡\mathit{\sigma}_{\mathit{\ell}}^{\mathit{t}} 引入喜欢概率函数,能够灵活刻画匹配饱和、使用倦怠、信号激励等多元行为模式。

  • 提出无须舍入的 DH-int 算法与免重复求解的 DHT 算法:原始约会启发式算法(DH,Rios et al. 2023)求解连续松弛线性规划后再进行启发式舍入,既引入效率损失又阻碍理论分析。本文提出的 DH-int 对当期决策强制取二元整数变量,对下期决策保留连续期望形式,直接产出可执行方案且未增加额外计算负担;针对长周期高算力开销场景,进一步提出半自适应算法 DHT,仅需期初求解一次多期整数规划即可预分配发起展示列表,并动态清理待处理喜欢列表。

  • 首次建立统一的 1 − 1𝑒\text{1 − }\frac{\text{1}}{\mathit{e}} 理论近似保证及创新证明框架:本文证明了贪心算法(Greedy)与完美匹配算法(Perfect Matching,PM)在最坏情形下的近似比会随市场规模扩大趋近于 0,而多项式时间次模算法仅能给出较弱且依赖平台设计的常数因子保证(定理 2)。相比之下,DH-int 在两期模型中对所有平台设计均达到统一的 1 − 1𝑒\text{1 − }\frac{\text{1}}{\mathit{e}}(约 63.2%)近似保证(定理 1);在多期模型中,DHT 相对最优半自适应策略同样达到 1 − 1𝑒\text{1 − }\frac{\text{1}}{\mathit{e}} 保证(定理 3),且在单向顺序设定下相对任意全自适应策略亦成立(定理 4)。文章创新性地将混合整数松弛与“待处理列表分布问题(distribution problem)”线性规划相连,结合强对偶性与相关间隙(correlation gap)得出上述结论。

  • 大规模真实数据实证与内在作用机制揭示:利用美国休斯敦地区真实约会面板数据,在双向与单向(男发起/女发起)平台及五种历史效应(无历史、线性衰减、阈值截断、参与倦怠、信号激励)下开展大规模仿真。结果显示 DH-int 稳健优于所有基准且极度逼近理论上限,DHT 亦展现出极具竞争力的性价比。文章进一步揭示了其胜出的核心机制:算法并非盲目追逐最高初次喜欢概率,而是通过精准平衡“初始触达的喜欢概率”与“后续对方回赞的转化概率”,最大化双边成对效率。

算法名称 原文伪代码 策略类型 前瞻周期 首期决策变量 后续期决策变量
DH(原始) Algorithm A.1 自适应 2 期(前瞻一步) 连续变量(需舍入) 连续变量
DH-int(核心) Algorithm 1 / 2 自适应 2 期(前瞻一步) 二元整数变量(直接执行) 连续变量
DHT(多期变体) Algorithm 3 半自适应 𝑇\mathit{T} 期(全周期) 二元整数变量 二元整数变量

三、理论模型与核心函数详解

考虑一个在离散时间 [𝑇] = {1, …, 𝑇}\left\lbrack \mathit{T} \right\rbrack\text{ = }\left\{ \text{1, …, }\mathit{T} \right\} 内运营的异性恋双边约会平台,两侧固定用户集合分别为 𝐼\mathit{I} 和 𝐽\mathit{J}。每位用户 ℓ ∈ 𝐼 ∪ 𝐽\mathit{\ell}\text{ ∈ }\mathit{I}\text{ ∪ }\mathit{J} 每期最多浏览 𝐾ℓ\mathit{K}_{\mathit{\ell}} 份候选资料(容量约束 |𝑆ℓ𝑡| ≤ 𝐾ℓ\left| \mathit{S}_{\mathit{\ell}}^{\mathit{t}} \right|\text{ ≤ }\mathit{K}_{\mathit{\ell}})。下文逐一解析模型中的所有核心函数与动态映射关系。

3.1 系统状态动态演化函数与历史向量

设 𝑃ℓ𝑡\mathit{P}_{\mathit{\ell}}^{\mathit{t}} 为用户 ℓ\mathit{\ell} 在第 𝑡\mathit{t} 期初的潜在可匹配对象集合(potentials),𝐵ℓ𝑡\mathit{B}_{\mathit{\ell}}^{\mathit{t}} 为其待处理喜欢集合(backlog,即此前已喜欢 ℓ\mathit{\ell} 但尚未展示给 ℓ\mathit{\ell} 的用户)。每期结束后,系统状态按公式(1)更新:

𝑃ℓ𝑡 = 𝑃ℓ𝑡−1 \(𝑆ℓ𝑡−1 ∪ 𝐷ℓ,←𝑡−1) , 𝐵ℓ𝑡 = (𝐵ℓ𝑡−1 ∪ 𝑁ℓ,←𝑡−1) \𝑆ℓ𝑡−1\mathit{P}_{\mathit{\ell}}^{\mathit{t}}\text{ = }\mathit{P}_{\mathit{\ell}}^{\mathit{t - 1}}\text{ \textbackslash }\left( \mathit{S}_{\mathit{\ell}}^{\mathit{t - 1}}\text{ ∪ }\mathit{D}_{\mathit{\ell, \leftarrow}}^{\mathit{t - 1}} \right)\text{ , }\mathit{B}_{\mathit{\ell}}^{\mathit{t}}\text{ = }\left( \mathit{B}_{\mathit{\ell}}^{\mathit{t - 1}}\text{ ∪ }\mathit{N}_{\mathit{\ell, \leftarrow}}^{\mathit{t - 1}} \right)\text{ \textbackslash }\mathit{S}_{\mathit{\ell}}^{\mathit{t - 1}}

其中 𝑁ℓ,←𝑡−1 = 𝑃ℓ𝑡−1 ∩ 𝐿ℓ,←𝑡−1\mathit{N}_{\mathit{\ell, \leftarrow}}^{\mathit{t - 1}}\text{ = }\mathit{P}_{\mathit{\ell}}^{\mathit{t - 1}}\text{ ∩ }\mathit{L}_{\mathit{\ell, \leftarrow}}^{\mathit{t - 1}} 表示在第 𝑡−1\mathit{t - 1} 期新收到且此前未曾展示过的“喜欢”。这一状态转移说明:每位用户的潜在对象集随时间单调缩减(剔除已看过的资料 𝑆ℓ𝑡−1\mathit{S}_{\mathit{\ell}}^{\mathit{t - 1}} 及明确不喜欢自己的人 𝐷ℓ,←𝑡−1\mathit{D}_{\mathit{\ell, \leftarrow}}^{\mathit{t - 1}}),而待处理集合则是上期存量加上本期新收到的喜欢、再减去本期已展示过的资料。用户的历史向量定义为 𝜎ℓ𝑡 = (𝐿ℓ,→<𝑡, 𝐷ℓ,→<𝑡, 𝐵ℓ𝑡, 𝑀ℓ<𝑡)\mathit{\sigma}_{\mathit{\ell}}^{\mathit{t}}\text{ = }\left( \mathit{L}_{\mathit{\ell, \rightarrow}}^{\mathit{< t}}\text{, }\mathit{D}_{\mathit{\ell, \rightarrow}}^{\mathit{< t}}\text{, }\mathit{B}_{\mathit{\ell}}^{\mathit{t}}\text{, }\mathit{M}_{\mathit{\ell}}^{\mathit{< t}} \right),依次涵盖该用户累计给出的喜欢、累计给出的不喜欢、当前待处理喜欢集合以及累计已达成的匹配集合。

3.2 喜欢概率函数、同期匹配概率与历史效应函数

记二元随机变量 𝛷ℓ,ℓ′𝑡\mathit{\Phi}_{\mathit{\ell,\ell\prime}}^{\mathit{t}} 表示用户 ℓ\mathit{\ell} 在第 𝑡\mathit{t} 期是否喜欢资料 ℓ’\mathit{\ell}\text{'}。模型的行为核心是喜欢概率函数与同期非顺序匹配概率函数:

𝜑ℓ,ℓ′𝑡(𝜎ℓ𝑡) = P(𝛷ℓ,ℓ′𝑡 = 1 | 𝜎ℓ𝑡) , 𝛽ℓ,ℓ′𝑡(𝜎ℓ𝑡, 𝜎ℓ′𝑡) = 𝜑ℓ,ℓ′𝑡(𝜎ℓ𝑡) · 𝜑ℓ′,ℓ𝑡(𝜎ℓ′𝑡)\mathit{\varphi}_{\mathit{\ell,\ell\prime}}^{\mathit{t}}\left( \mathit{\sigma}_{\mathit{\ell}}^{\mathit{t}} \right)\text{ = }\text{P}\left( \mathit{\Phi}_{\mathit{\ell,\ell\prime}}^{\mathit{t}}\text{ = 1 | }\mathit{\sigma}_{\mathit{\ell}}^{\mathit{t}} \right)\text{ , }\mathit{\beta}_{\mathit{\ell,\ell\prime}}^{\mathit{t}}\left( \mathit{\sigma}_{\mathit{\ell}}^{\mathit{t}}\text{, }\mathit{\sigma}_{\mathit{\ell\prime}}^{\mathit{t}} \right)\text{ = }\mathit{\varphi}_{\mathit{\ell,\ell\prime}}^{\mathit{t}}\left( \mathit{\sigma}_{\mathit{\ell}}^{\mathit{t}} \right)\text{ · }\mathit{\varphi}_{\mathit{\ell\prime,\ell}}^{\mathit{t}}\left( \mathit{\sigma}_{\mathit{\ell\prime}}^{\mathit{t}} \right)

函数 𝜑ℓ,ℓ′𝑡(𝜎ℓ𝑡)\mathit{\varphi}_{\mathit{\ell,\ell\prime}}^{\mathit{t}}\left( \mathit{\sigma}_{\mathit{\ell}}^{\mathit{t}} \right) 刻画用户 ℓ\mathit{\ell} 在给定自身历史 𝜎ℓ𝑡\mathit{\sigma}_{\mathit{\ell}}^{\mathit{t}} 下喜欢 ℓ’\mathit{\ell}\text{'} 的概率。模型假定各用户的决定相互独立,且 𝜑ℓ,ℓ′𝑡\mathit{\varphi}_{\mathit{\ell,\ell\prime}}^{\mathit{t}} 不受当期同时展示的其他资料影响(无替代效应)。函数 𝛽𝑒𝑡\mathit{\beta}_{\mathit{e}}^{\mathit{t}}(其中 𝑒 = {ℓ, ℓ’}\mathit{e}\text{ = }\left\{ \mathit{\ell}\text{, }\mathit{\ell}\text{'} \right\})则是两人在同一期互看并同时喜欢的联合概率。在实证部分(第 6.3 节),作者采用 Logit 形式将历史映射为间接效用变动:

𝜑ℓ,ℓ′𝑡 = exp(𝑢ℓ,ℓ′ + 𝛾(𝜎ℓ𝑡))1 + exp(𝑢ℓ,ℓ′ + 𝛾(𝜎ℓ𝑡))\mathit{\varphi}_{\mathit{\ell,\ell\prime}}^{\mathit{t}}\text{ = }\frac{\text{exp}\left( \mathit{u}_{\mathit{\ell,\ell\prime}}\text{ + }\mathit{\gamma}\left( \mathit{\sigma}_{\mathit{\ell}}^{\mathit{t}} \right) \right)}{\text{1 + exp}\left( \mathit{u}_{\mathit{\ell,\ell\prime}}\text{ + }\mathit{\gamma}\left( \mathit{\sigma}_{\mathit{\ell}}^{\mathit{t}} \right) \right)}

其中 𝑢ℓ,ℓ′\mathit{u}_{\mathit{\ell,\ell\prime}} 为无历史效应时的基础匹配效用,而历史效应函数 𝛾(𝜎)\mathit{\gamma}\left( \mathit{\sigma} \right) 共有五种参数化设定:(1)无历史效应 𝛾(𝜎) = 0\mathit{\gamma}\left( \mathit{\sigma} \right)\text{ = 0};(2)线性衰减 𝛾(𝜎) = 𝛾|𝑀|\mathit{\gamma}\left( \mathit{\sigma} \right)\text{ = }\mathit{\gamma}\left| \mathit{M} \right|(𝛾 = −0.170\mathit{\gamma}\text{ = −0.170},匹配越多越挑剔);(3)阈值截断(当 |𝑀| > 𝛾\left| \mathit{M} \right|\text{ > }\mathit{\gamma} 时 𝛾(𝜎) = −∞\mathit{\gamma}\left( \mathit{\sigma} \right)\text{ = −∞},否则为 0,模拟时间精力上限,基准取 𝛾 = 5\mathit{\gamma}\text{ = 5});(4)参与倦怠 𝛾(𝜎) = 𝛾𝑡\mathit{\gamma}\left( \mathit{\sigma} \right)\text{ = }\mathit{\gamma}\mathit{t}(𝛾 = −0.2\mathit{\gamma}\text{ = −0.2},使用时间越长活跃度越低);(5)信号激励 𝛾(𝜎) = −𝛾𝟏{ℓ’ ∈ 𝐵ℓ𝑡}\mathit{\gamma}\left( \mathit{\sigma} \right)\text{ = −}\mathit{\gamma}\mathbf{1}\left\{ \mathit{\ell}\text{'}\text{ ∈ }\mathit{B}_{\mathit{\ell}}^{\mathit{t}} \right\}(𝛾 = −0.2\mathit{\gamma}\text{ = −0.2},告知对方已喜欢自己时提升回赞效用)。

3.3 平台全局目标函数与随机实现分布函数

平台需从容许策略集 𝛱\mathit{\Pi} 中选择动态展示策略 𝜋\mathit{\pi},以最大化全周期期望总匹配数(Problem 1):

max𝜋 ∈ 𝛱E[∑𝑡=1𝑇∑(𝑖,𝑗)∈𝐼×𝐽𝜇𝑖,𝑗𝑡,𝜋]\underset{\mathit{\pi}\text{ ∈ }\mathit{\Pi}}{\text{max}}\text{E}\left\lbrack \sum_{\mathit{t}\text{=1}}^{\mathit{T}}{\sum_{\left( \mathit{i}\text{,}\mathit{j} \right)\text{∈}\mathit{I}\text{×}\mathit{J}}^{}\mathit{\mu}_{\mathit{i,j}}^{\mathit{t,\pi}}} \right\rbrack

其中 𝜇𝑖,𝑗𝑡,𝜋\mathit{\mu}_{\mathit{i,j}}^{\mathit{t,\pi}} 为指示用户 𝑖\mathit{i} 与 𝑗\mathit{j} 是否在第 𝑡\mathit{t} 期达成匹配的随机变量。在固定时期 𝑡\mathit{t},平台决策由二元向量 𝐱𝑡\mathbf{x}^{\mathit{t}}(顺序展示有向弧)与 𝐰𝑡\mathbf{w}^{\mathit{t}}(同期互看无向边)表征,满足互斥约束 𝑥ℓ,ℓ′𝑡 + 𝑥ℓ′,ℓ𝑡 + 𝑤𝑒𝑡 ≤ 1\mathit{x}_{\mathit{\ell,\ell\prime}}^{\mathit{t}}\text{ + }\mathit{x}_{\mathit{\ell\prime,\ell}}^{\mathit{t}}\text{ + }\mathit{w}_{\mathit{e}}^{\mathit{t}}\text{ ≤ 1}。记 𝑅\mathit{R} 为第 𝑡\mathit{t} 期实际展示且获得喜欢的有向弧及同期双向喜欢的无向边集合,则随机实现分布函数为公式(5):

P𝐳𝑡(𝑅 = 𝑅) = ∏𝑎∈𝑅𝑧𝑎𝑡 · ∏𝑎∉𝑅(1 − 𝑧𝑎𝑡)\text{P}_{\mathbf{z}^{\mathit{t}}}\left( \mathit{R}\text{ = }\mathit{R} \right)\text{ = }\prod_{\mathit{a}\text{∈}\mathit{R}}^{}\mathit{z}_{\mathit{a}}^{\mathit{t}}\text{ · }\prod_{\mathit{a}\text{∉}\mathit{R}}^{}\left( \text{1 − }\mathit{z}_{\mathit{a}}^{\mathit{t}} \right)

其中对有向弧 𝑎 = (ℓ, ℓ’)\mathit{a}\text{ = }\left( \mathit{\ell}\text{, }\mathit{\ell}\text{'} \right) 有 𝑧𝑎𝑡 = 𝜑ℓ,ℓ′𝑡 · 𝑥ℓ,ℓ′𝑡\mathit{z}_{\mathit{a}}^{\mathit{t}}\text{ = }\mathit{\varphi}_{\mathit{\ell,\ell\prime}}^{\mathit{t}}\text{ · }\mathit{x}_{\mathit{\ell,\ell\prime}}^{\mathit{t}},对无向边 𝑎 = {ℓ, ℓ’}\mathit{a}\text{ = }\left\{ \mathit{\ell}\text{, }\mathit{\ell}\text{'} \right\} 有 𝑧𝑎𝑡 = 𝛽𝑎𝑡 · 𝑤𝑎𝑡\mathit{z}_{\mathit{a}}^{\mathit{t}}\text{ = }\mathit{\beta}_{\mathit{a}}^{\mathit{t}}\text{ · }\mathit{w}_{\mathit{a}}^{\mathit{t}}。该函数因用户选择独立而呈现乘积伯努利结构,完整刻画了本期决策诱发下期所有可能状态的概率权重。

3.4 前瞻一步值函数、两期简化函数与代理上界函数

在前瞻一步策略(考虑 {𝑡, 𝑡+1}\left\{ \mathit{t}\text{, }\mathit{t}\text{+1} \right\} 两期)中,模型定义了四个逐层递进的核心值函数:

  • 下期条件最优匹配函数 𝑓𝑡+1(𝑅, 𝐱𝑡, 𝐰𝑡)\mathit{f}^{\mathit{t + 1}}\left( \mathit{R}\text{, }\mathbf{x}^{\mathit{t}}\text{, }\mathbf{w}^{\mathit{t}} \right)(公式 7):在已知第 𝑡\mathit{t} 期展示决策 (𝐱𝑡, 𝐰𝑡)\left( \mathbf{x}^{\mathit{t}}\text{, }\mathbf{w}^{\mathit{t}} \right) 和随机喜欢结果 𝑅\mathit{R} 的条件下,仅着眼于第 𝑡+1\mathit{t + 1} 期(忽略更远未来)通过最优选择顺序回赞展示 𝐱𝑡+1\mathbf{x}^{\mathit{t + 1}} 与非顺序展示 𝐰𝑡+1\mathbf{w}^{\mathit{t + 1}} 所能获得的最大期望匹配数。

  • 下期期望最优匹配函数 M𝑡+1(𝐱𝑡, 𝐰𝑡)\text{M}^{\mathit{t + 1}}\left( \mathbf{x}^{\mathit{t}}\text{, }\mathbf{w}^{\mathit{t}} \right)(公式 8):对所有可能实现 𝑅 ⊆ 𝐸→𝑡 ∪ 𝐸𝑡\mathit{R}\text{ ⊆ }{\overrightarrow{\mathit{E}}}^{\mathit{t}}\text{ ∪ }\mathit{E}^{\mathit{t}} 取期望,即 M𝑡+1(𝐱𝑡, 𝐰𝑡) := E𝑅~𝐳𝑡[𝑓𝑡+1(𝑅, 𝐱𝑡, 𝐰𝑡)]\text{M}^{\mathit{t + 1}}\left( \mathbf{x}^{\mathit{t}}\text{, }\mathbf{w}^{\mathit{t}} \right)\text{ := }\text{E}_{\mathit{R}\text{\textasciitilde}\mathbf{z}^{\mathit{t}}}\left\lbrack \mathit{f}^{\mathit{t + 1}}\left( \mathit{R}\text{, }\mathbf{x}^{\mathit{t}}\text{, }\mathbf{w}^{\mathit{t}} \right) \right\rbrack。将其与第 𝑡\mathit{t} 期即期期望匹配数(公式 9)相加,即构成前瞻一步优化问题(Problem 2)。

  • 两期简化条件值函数 𝑓(𝑅)\mathit{f}\left( \mathit{R} \right)(公式 13)与 M2(𝐱1, 𝐰1)\text{M}^{\text{2}}\left( \mathbf{x}^{\text{1}}\text{, }\mathbf{w}^{\text{1}} \right)(公式 14):在 𝑇 = 2\mathit{T}\text{ = 2} 且假定初始待处理集为空、第二期喜欢概率不依赖历史且禁止非顺序匹配时,𝑓(𝑅)\mathit{f}\left( \mathit{R} \right) 简化为在分区拟阵(partition matroid)上最大化线性目标 ∑(ℓ,ℓ’)∈𝐸→1𝜑ℓ,ℓ′2 · 𝑥ℓ,ℓ′2\sum_{\left( \mathit{\ell}\text{,}\mathit{\ell}\text{'} \right)\text{∈}{\overrightarrow{\mathit{E}}}^{\mathit{1}}}^{}{\mathit{\varphi}_{\mathit{\ell,\ell\prime}}^{\text{2}}\text{ · }\mathit{x}_{\mathit{\ell,\ell\prime}}^{\text{2}}},单用户版本记作 𝑓ℓ(𝐵)\mathit{f}_{\mathit{\ell}}\left( \mathit{B} \right),可在多项式时间内求解。

  • 第二阶段连续松弛上界函数 𝐹(𝐱1,★, 𝐰1,★)\mathit{F}\left( \mathbf{x}^{\text{1,★}}\text{, }\mathbf{w}^{\text{1,★}} \right)(公式 17)与分布问题上界函数 𝐺(𝐱1, 𝐰1)\mathit{G}\left( \mathbf{x}^{\text{1}}\text{, }\mathbf{w}^{\text{1}} \right)(公式 18):DH-int(公式 11、16)用不依赖当期实现的代理概率 𝜑̂ℓ,ℓ′𝑡+1{\widehat{\mathit{\varphi}}}_{\mathit{\ell,\ell\prime}}^{\mathit{t + 1}} 替代 𝜑ℓ,ℓ′𝑡+1\mathit{\varphi}_{\mathit{\ell,\ell\prime}}^{\mathit{t + 1}},将非线性期望转化为混合整数规划;𝐹\mathit{F} 表示在给定首期整数解后,按边际期望约束 𝑦ℓ,ℓ′ ≤ 𝜑ℓ′,ℓ1 · 𝑥ℓ′,ℓ1,★\mathit{y}_{\mathit{\ell,\ell\prime}}\text{ ≤ }\mathit{\varphi}_{\mathit{\ell\prime,\ell}}^{\text{1}}\text{ · }\mathit{x}_{\mathit{\ell\prime,\ell}}^{\text{1,★}} 求解第二期期望匹配的上界;𝐺\mathit{G} 则以各用户待处理集合 𝐵\mathit{B} 的任意联合概率分布 𝜆ℓ,𝐵\mathit{\lambda}_{\mathit{\ell,B}} 为决策变量,在满足首期边际喜欢概率一致性的前提下最大化第二期期望匹配,是建立 1 − 1𝑒\text{1 − }\frac{\text{1}}{\mathit{e}} 保证的关键理论桥梁。

函数记号 名称与定位 经济与数学含义
𝜑ℓ,ℓ′𝑡(𝜎ℓ𝑡)\mathit{\varphi}_{\mathit{\ell,\ell\prime}}^{\mathit{t}}\left( \mathit{\sigma}_{\mathit{\ell}}^{\mathit{t}} \right) 喜欢概率函数 给定历史下用户 ℓ\mathit{\ell} 喜欢 ℓ’\mathit{\ell}\text{'} 的条件概率;实证采用 Logit 形式结合 𝛾(𝜎)\mathit{\gamma}\left( \mathit{\sigma} \right)
𝛽𝑒𝑡\mathit{\beta}_{\mathit{e}}^{\mathit{t}} 同期匹配概率 边 𝑒 = {ℓ,ℓ’}\mathit{e}\text{ = }\left\{ \mathit{\ell}\text{,}\mathit{\ell}\text{'} \right\} 在第 𝑡\mathit{t} 期互看并同时喜欢的联合概率 𝜑ℓ,ℓ′𝑡 · 𝜑ℓ′,ℓ𝑡\mathit{\varphi}_{\mathit{\ell,\ell\prime}}^{\mathit{t}}\text{ · }\mathit{\varphi}_{\mathit{\ell\prime,\ell}}^{\mathit{t}}
P𝐳𝑡(𝑅=𝑅)\text{P}_{\mathbf{z}^{\mathit{t}}}\left( \mathit{R}\text{=}\mathit{R} \right) 随机实现分布函数 在决策 (𝐱𝑡,𝐰𝑡)\left( \mathbf{x}^{\mathit{t}}\text{,}\mathbf{w}^{\mathit{t}} \right) 下本期实现喜欢集合恰好为 𝑅\mathit{R} 的乘积概率分布
𝑓𝑡+1(𝑅,𝐱𝑡,𝐰𝑡)\mathit{f}^{\mathit{t + 1}}\left( \mathit{R}\text{,}\mathbf{x}^{\mathit{t}}\text{,}\mathbf{w}^{\mathit{t}} \right) 下期条件最优值 已知本期决策与喜欢实现 𝑅\mathit{R} 后,第 𝑡+1\mathit{t + 1} 期可达到的最大期望匹配数
M𝑡+1(𝐱𝑡,𝐰𝑡)\text{M}^{\mathit{t + 1}}\left( \mathbf{x}^{\mathit{t}}\text{,}\mathbf{w}^{\mathit{t}} \right) 下期期望最优值 对 𝑓𝑡+1\mathit{f}^{\mathit{t + 1}} 关于所有可能实现 𝑅\mathit{R} 取期望,构成前瞻一步问题核心项
𝑓(𝑅)\mathit{f}\left( \mathit{R} \right) 两期简化值函数 𝑇 = 2\mathit{T}\text{ = 2} 且禁止二期非顺序匹配时的分区拟阵最优值,单调且次模
𝐹 , 𝐺\mathit{F}\text{ , }\mathit{G} 松弛与分布上界 𝐹\mathit{F} 为 DH-int 第二期连续松弛上界;𝐺\mathit{G} 为待处理集联合分布规划上界

四、主要命题、引理与定理的举例阐释(不含证明)

下文按照原文结构顺序,对全文所有的正式理论陈述(包括 1 个命题、2 个引理、1 个核心定义及 4 个定理)逐一提炼其核心含义,并通过具体的数值与平台情境例子加以直观阐释(遵循要求,省略全部数学证明过程)。

4.1 命题 1(Proposition 1):一般情形下下期条件值函数非次模

核心含义:在允许下期存在非顺序匹配(或存在复杂历史依赖)的一般情形下,公式(7)定义的下期最优匹配值函数 𝑓𝑡+1(𝑅, 𝐱𝑡, 𝐰𝑡)\mathit{f}^{\mathit{t + 1}}\left( \mathit{R}\text{, }\mathbf{x}^{\mathit{t}}\text{, }\mathbf{w}^{\mathit{t}} \right) 关于本期喜欢实现集合 𝑅\mathit{R} 不满足次模性(即不满足“边际收益递减”规律),因此无法直接套用经典的次模优化理论来推导算法性能保证。

举例说明:设用户 𝑖1\mathit{i}_{\text{1}} 与 𝑗1\mathit{j}_{\text{1}} 每期均只能浏览 1 份资料(𝐾𝑖1 = 𝐾𝑗1 = 1\mathit{K}_{\mathit{i}_{\text{1}}}\text{ = }\mathit{K}_{\mathit{j}_{\text{1}}}\text{ = 1})。在第 𝑡+1\mathit{t + 1} 期,若两人同期互看(非顺序匹配),匹配概率为 𝛽{𝑖1,𝑗1}𝑡+1 = 0.8\mathit{\beta}_{\left\{ \mathit{i}_{\text{1}}\text{,}\mathit{j}_{\text{1}} \right\}}^{\mathit{t + 1}}\text{ = 0.8}。同时,第 𝑡\mathit{t} 期另有用户 𝑗2\mathit{j}_{\text{2}} 浏览了 𝑖1\mathit{i}_{\text{1}}(若喜欢记作事件 𝑎1\mathit{a}_{\text{1}},下期 𝑖1\mathit{i}_{\text{1}} 回赞概率为 0.5\text{0.5}),用户 𝑖2\mathit{i}_{\text{2}} 浏览了 𝑗1\mathit{j}_{\text{1}}(若喜欢记作事件 𝑎2\mathit{a}_{\text{2}},下期 𝑗1\mathit{j}_{\text{1}} 回赞概率也为 0.5\text{0.5})。对比四种实现:

  • 若 𝑅 = ∅\mathit{R}\text{ = ∅}(均未获得喜欢):平台安排 𝑖1\mathit{i}_{\text{1}} 与 𝑗1\mathit{j}_{\text{1}} 同期互看,期望匹配数为 𝑓𝑡+1(∅) = 0.8\mathit{f}^{\mathit{t + 1}}\left( \text{∅} \right)\text{ = 0.8}。

  • 若仅发生 𝑎1\mathit{a}_{\text{1}}(𝑅 = {𝑎1}\mathit{R}\text{ = }\left\{ \mathit{a}_{\text{1}} \right\}):拆散 {𝑖1,𝑗1}\left\{ \mathit{i}_{\text{1}}\text{,}\mathit{j}_{\text{1}} \right\} 仅得 0.5 < 0.8\text{0.5 < 0.8},故平台仍保持同期互看,𝑓𝑡+1({𝑎1}) = 0.8\mathit{f}^{\mathit{t + 1}}\left( \left\{ \mathit{a}_{\text{1}} \right\} \right)\text{ = 0.8}。可见在空集上增加 𝑎1\mathit{a}_{\text{1}} 的边际增益为 0.8 − 0.8 = 0\text{0.8 − 0.8 = 0}。

  • 同理,若仅发生 𝑎2\mathit{a}_{\text{2}},𝑓𝑡+1({𝑎2}) = 0.8\mathit{f}^{\mathit{t + 1}}\left( \left\{ \mathit{a}_{\text{2}} \right\} \right)\text{ = 0.8}。

  • 但若两者同时发生(𝑅 = {𝑎1, 𝑎2}\mathit{R}\text{ = }\left\{ \mathit{a}_{\text{1}}\text{, }\mathit{a}_{\text{2}} \right\}):平台拆散同期互看,让两人各自回应待处理喜欢,总期望匹配数跃升至 0.5 + 0.5 = 1.0 > 0.8\text{0.5 + 0.5 = 1.0 > 0.8}。此时在更大集合 {𝑎2}\left\{ \mathit{a}_{\text{2}} \right\} 上增加 𝑎1\mathit{a}_{\text{1}} 的边际增益为 1.0 − 0.8 = 0.2 > 0\text{1.0 − 0.8 = 0.2 > 0}!边际收益不降反升,产生了互补效应,直接违背次模性。

4.2 引理 1(Lemma 1):两期简化条件值函数的单调性与次模性

核心含义:当时间跨度为两期(𝑇 = 2\mathit{T}\text{ = 2})且满足初始待处理集为空、第二期喜欢概率不依赖历史、且第二期禁止非顺序匹配三项简化假设时,公式(13)定义的第二期最优值函数 𝑓(𝑅)\mathit{f}\left( \mathit{R} \right) 同时具有单调性(待处理喜欢越多,期望匹配不会减少)和次模性(每新增一个待处理喜欢的边际价值递减)。

举例说明:假设用户 𝐴\mathit{A} 在第二期只能浏览 1 份资料(𝐾𝐴 = 1\mathit{K}_{\mathit{A}}\text{ = 1}),且第二期禁止非顺序匹配,只能从待处理喜欢列表中择优展示。三位候选人 𝐵1\mathit{B}_{\text{1}}、𝐵2\mathit{B}_{\text{2}}、𝐵3\mathit{B}_{\text{3}} 被 𝐴\mathit{A} 回赞的概率分别为 0.7\text{0.7}、0.5\text{0.5} 和 0.8\text{0.8}。单调性显而易见:待处理列表从 ∅\text{∅} 增至 {𝐵2}\left\{ \mathit{B}_{\text{2}} \right\} 再增至 {𝐵1, 𝐵2}\left\{ \mathit{B}_{\text{1}}\text{, }\mathit{B}_{\text{2}} \right\},最优匹配值由 0\text{0} 依次增至 0.5\text{0.5} 与 0.7\text{0.7}。就次模性而言,考察新增优质候选人 𝐵3\mathit{B}_{\text{3}}(概率 0.8\text{0.8})的边际贡献:若原有列表较小,为 𝑅1 = {𝐵2}\mathit{R}_{\text{1}}\text{ = }\left\{ \mathit{B}_{\text{2}} \right\},新增 𝐵3\mathit{B}_{\text{3}} 使收益从 0.5\text{0.5} 升至 0.8\text{0.8},边际增量为 0.3\text{0.3};若原有列表较大,为 𝑅2 = {𝐵1, 𝐵2}\mathit{R}_{\text{2}}\text{ = }\left\{ \mathit{B}_{\text{1}}\text{, }\mathit{B}_{\text{2}} \right\},因已有较优备选 𝐵1\mathit{B}_{\text{1}}(0.7\text{0.7}),新增 𝐵3\mathit{B}_{\text{3}} 仅使收益从 0.7\text{0.7} 升至 0.8\text{0.8},边际增量缩减至 0.1 ≤ 0.3\text{0.1 ≤ 0.3},完美体现边际收益递减。

4.3 定理 1(Theorem 1):DH-int 在两期模型中的统一 1−1/e 近似保证

核心含义:在两期问题(Problem 3)中,无论平台采用何种交互设计(单向或双向、允许或禁止首期非顺序匹配),算法 2(两期版 DH-int)所获得的期望匹配数始终不低于理论最优动态规划解(OPT\text{OPT})的 1 − 1𝑒\text{1 − }\frac{\text{1}}{\mathit{e}}(约 63.2%\text{63.2\%}),彻底克服了贪心算法与完美匹配算法在最坏情形下表现崩溃的缺陷。

举例说明:首先从全局底线看,若某两期约会平台在理论上最理想的动态策略预期可撮合 100\text{100} 对匹配,定理 1 保证 DH-int 在任何极端参数配置下至少能达成 63.2\text{63.2} 对匹配(实证中更是接近理论上限)。其次从微观决策逻辑看,设用户 𝐴\mathit{A}(𝐾𝐴 = 1\mathit{K}_{\mathit{A}}\text{ = 1})首期可在 𝐵1\mathit{B}_{\text{1}} 与 𝐵2\mathit{B}_{\text{2}} 中二选一:假设 𝐴\mathit{A} 极易喜欢高人气用户 𝐵1\mathit{B}_{\text{1}}(𝜑𝐴,𝐵11 = 0.9\mathit{\varphi}_{\mathit{A}\text{,}\mathit{B}_{\text{1}}}^{\text{1}}\text{ = 0.9}),但 𝐵1\mathit{B}_{\text{1}} 十分挑剔且回赞概率极低(𝜑𝐵1,𝐴2 = 0.1\mathit{\varphi}_{\mathit{B}_{\text{1}}\text{,}\mathit{A}}^{\text{2}}\text{ = 0.1});而 𝐴\mathit{A} 喜欢 𝐵2\mathit{B}_{\text{2}} 的概率适中(0.5\text{0.5}),但 𝐵2\mathit{B}_{\text{2}} 回赞概率高达 0.9\text{0.9}。仅追逐首期喜欢率的短视做法会推送 𝐵1\mathit{B}_{\text{1}}(两期成对期望仅 0.9 × 0.1 = 0.09\text{0.9 × 0.1 = 0.09});DH-int 则通过约束 𝑥ℓ,ℓ′2 ≤ 𝜑ℓ′,ℓ1 · 𝑥ℓ′,ℓ1\mathit{x}_{\mathit{\ell,\ell\prime}}^{\text{2}}\text{ ≤ }\mathit{\varphi}_{\mathit{\ell\prime,\ell}}^{\text{1}}\text{ · }\mathit{x}_{\mathit{\ell\prime,\ell}}^{\text{1}} 统筹两期概率与对方容量竞争,果断选择推送 𝐵2\mathit{B}_{\text{2}}(期望匹配 0.5 × 0.9 = 0.45\text{0.5 × 0.9 = 0.45}),从而稳固守住 1 − 1𝑒\text{1 − }\frac{\text{1}}{\mathit{e}} 的理论下界。

4.4 定理 2(Theorem 2):多项式时间次模算法的设计依赖常数因子保证

核心含义:由于 DH-int 需求解混合整数规划,在超大规模市场中可能面临扩展性挑战。作为多项式时间替代方案,利用次模优化技术构造的算法 5(详见原文电子附录 EC.3)也能为两期问题提供常数因子近似保证,但该保证值弱于 1 − 1𝑒\text{1 − }\frac{\text{1}}{\mathit{e}},且具体大小取决于平台的两项核心设计:(1)匹配时机(仅允许顺序匹配,还是允许同期非顺序匹配);(2)交互方向(仅单侧可发起,还是双侧皆可发起)。

举例说明:假设一家拥有数百万日活用户的约会平台因算力限制,决定采用多项式时间次模算法替代整数规划。如果该平台采用类似 Coffee Meets Bagel“Ladies Choice”的单向顺序模式(仅男性发起喜欢、女性次日从待处理列表回复),其可行域约束最为规整,次模算法能给出相对较高的常数保证;但如果平台升级为双向且支持同期非顺序匹配模式(类似 Tinder 的“Hot Takes”限时速聊或 Filteroff/The League 的实时视频速配,允许男女双向发起并在同一期即时互选),可行域涉及多重拟阵交集,该多项式时间算法的理论常数因子保证便会随之下降。这凸显了 DH-int 能在各类平台设计下保持统一 1 − 1𝑒\text{1 − }\frac{\text{1}}{\mathit{e}} 保证的独特稳健优势。

4.5 定义 1 与引理 2(Definition 1 & Lemma 2):半自适应策略及多期上界

核心含义:在 𝑇 > 2\mathit{T}\text{ > 2} 的多期模型(假定喜欢概率不随时间变化且末期无非顺序匹配)中,定义 1 区分了两类策略:半自适应策略(semiadaptive)在为发起方安排新交互(包括顺序发起与非顺序互看)时采用非自适应方式(事前排定、不随中途结果调整),但在为回应方从待处理列表中挑选资料时采用自适应方式;全自适应策略(adaptive)则对发起方与回应方均依据历史实时动态调整。引理 2 指出,将逐期容量汇总为全周期总容量 𝐾ℓ · 𝑇\mathit{K}_{\mathit{\ell}}\text{ · }\mathit{T} 的多期混合整数规划(公式 19),其最优值构成所有半自适应策略在 𝑇\mathit{T} 期内期望匹配数的理论上界。

举例说明:考虑一个运营周期为 1 周(𝑇 = 7\mathit{T}\text{ = 7} 天)、每人每天展示 𝐾ℓ = 2\mathit{K}_{\mathit{\ell}}\text{ = 2} 份资料(全周总配额 2 × 7 = 14\text{2 × 7 = 14} 个展示位)的约会平台。在半自适应策略下,平台周一便预先排好每位用户本周要主动“破冰”展示的新对象名单,不再根据周二、周三的点赞结果修改这份破冰名单;但每天一旦有空余展示位,平台会根据截至当天实际收到的待处理喜欢列表,动态挑出回赞概率最高的人展示。公式(19)放宽了每天必须严格不超过 2 个名额的硬约束,只要求全周总展示数不超过 14 个,并用连续概率 𝑦ℓ,ℓ′ ≤ 𝑥ℓ′,ℓ · 𝜑ℓ′,ℓ\mathit{y}_{\mathit{\ell,\ell\prime}}\text{ ≤ }\mathit{x}_{\mathit{\ell\prime,\ell}}\text{ · }\mathit{\varphi}_{\mathit{\ell\prime,\ell}} 衡量回应展示机会。由于任何真实半自适应策略既受每日名额限制又受随机到达限制,若公式(19)算出的最优值为 500\text{500} 对匹配,那么现实中任何半自适应策略在这 7 天内所能实现的期望匹配数绝不可能超过 500\text{500} 对。

4.6 定理 3(Theorem 3):多期算法 DHT 相对半自适应最优解的 1−1/e 保证

核心含义:对于任意周期长度 𝑇\mathit{T} 和任意平台设计,当策略空间限定为半自适应策略时,算法 3(多期版 DH-int,即 DHT)仅需在期初求解一次公式(19),随后按固定优先级执行展示与自适应清存量,即可获得不低于最优半自适应策略 1 − 1𝑒\text{1 − }\frac{\text{1}}{\mathit{e}} 的期望匹配数。

举例说明:沿用上述 7 天(𝑇 = 7\mathit{T}\text{ = 7}、𝐾ℓ = 2\mathit{K}_{\mathit{\ell}}\text{ = 2})平台情境,假设理论上最优的半自适应策略全周可产生 450\text{450} 对匹配。DHT 在周一清晨一次性求解公式(19),得到每位用户本周的发起名单 𝑋ℓ\mathit{X}_{\mathit{\ell}} 和同期互看名单 𝑊ℓ\mathit{W}_{\mathit{\ell}}。此后每天(如周一至周日)无需再重算任何大规模优化模型,只需按三步填充每人当天的 2 个展示位:第一步优先消耗 𝑋ℓ\mathit{X}_{\mathit{\ell}} 中对方回赞概率 𝜑ℓ′,ℓ\mathit{\varphi}_{\mathit{\ell\prime,\ell}} 最高的发起资料;第二步若仍有空位,安排 𝑊ℓ\mathit{W}_{\mathit{\ell}} 中双方均有空位的同期互看对;第三步若还有剩余空位,则自适应地从当日实时待处理喜欢集 𝐵ℓ𝑡\mathit{B}_{\mathit{\ell}}^{\mathit{t}} 中挑选最易回赞的对象。定理 3 保证,这种极其省算力的执行方式全周至少能稳定产出 (1 − 1𝑒) × 450 ≈ 284.5\left( \text{1 − }\frac{\text{1}}{\mathit{e}} \right)\text{ × 450 ≈ 284.5} 对匹配。

4.7 定理 4(Theorem 4):单向顺序平台下相对全自适应策略的 1−1/e 保证

核心含义:在单向交互(仅一侧可发起)且仅允许顺序匹配的平台设计下,即使允许基准策略采用任意强大的全自适应策略(每期根据全部最新反馈动态重算发起与回应方案),仍存在一个半自适应策略(通过求解公式 19 的线性松弛并结合 Gandhi et al. 2006 的相关随机舍入法输入算法 3),其期望匹配数至少达到最优全自适应策略的 1 − 1𝑒\text{1 − }\frac{\text{1}}{\mathit{e}}。

举例说明:考虑类似 Coffee Meets Bagel“Ladies Choice”的 7 天运营平台:仅男性用户可以主动浏览潜在女性并点赞(单向发起),女性用户则仅浏览此前已喜欢自己的男性资料(顺序匹配)。假设平台拥有无限算力,部署了一个“全自适应”理想系统——每天晚上根据白天所有男女用户的点赞与拒绝记录,重新为第二天每一位男性量身定制推荐名单,全周最高可达成 400\text{400} 对匹配。定理 4 表明,平台其实不必每天耗费巨额算力为男性侧动态重算:只需在周一求解一次线性松弛规划,利用相关随机舍入预先敲定每位男性全周要浏览的女性名单,同时保留女性侧每天根据实时待处理列表择优展示的自适应机制,这套轻量级的半自适应方案在全周至少能够达成 (1 − 1𝑒) × 400 ≈ 252.8\left( \text{1 − }\frac{\text{1}}{\mathit{e}} \right)\text{ × 400 ≈ 252.8} 对匹配,以极低的计算复杂度逼近全自适应极限。

五、实证评估与核心机制发现

作者基于行业合作方(美国某大型在线约会平台)提供的 2020 年 2 月 14 日至 8 月 14 日休斯敦地区异性恋用户完整面板数据,在 1 周时间跨度(𝑇 = 7\mathit{T}\text{ = 7}、每日展示 𝐾ℓ = 3\mathit{K}_{\mathit{\ell}}\text{ = 3} 份资料)下开展了每组 100 次的蒙特卡洛仿真,将 DH-int、DH 与 DHT 同 贪心算法(Greedy)、完美匹配(PM)、合作平台现行算法(Partner) 以及理论上限(UB)进行了全面对比,主要实证结论如下:

  • 全场景稳健领跑并逼近理论上限:无论在无历史效应、线性衰减、阈值截断、参与倦怠还是信号激励下,DH 系列算法均显著优于 Greedy、PM 和 Partner,且表现极度贴近理论上限。其中 DH-int 一致略优于原始 DH,证实取消分数解舍入步骤确实消除了运营损耗;DHT 在完全免去逐期重优化的情况下,表现仍与 DH/DH-int 高度接近。

  • 历史效应越强,DH-int 相对优势越大:在线性历史效应灵敏度测试中,当历史效应强度乘数 𝜓\mathit{\psi} 从 0\text{0}(无历史效应)增大至 5.0\text{5.0}(强挑剔效应)时,虽然各算法总匹配数均随喜欢率下降而走低,但 DH-int 相对基准的优势却从约 20%\text{20\%} 扩大至约 25%\text{25\%}。此外,DH-int 在阈值截断等突变型行为下与理论上限的差距极小,仅在持续性的参与倦怠(Disengagement)情形下差距相对较大。

  • 核心机制在于平衡“初始喜欢率”与“存量回赞率”:分性别剖析各期喜欢率发现,DH 系列算法在前六期的初始交互喜欢率反而显著低于 Greedy 等基准(仅在末期拉高以争取非顺序匹配),但其在待处理存量交互中的回赞率却持续显著高于所有基准且保持平稳。这说明算法并非盲目推送最受欢迎的“明星资料”去刷初始点赞,而是精准挑选“双方互有好感、后续更易获回赞”的资料组合。

  • 单向交互的匹配产出极度接近双向交互,且女性发起略优:由于现实中绝大多数匹配以顺序方式达成,当用户存在一定待处理存量或周期足够长时,单向模式(一方专职破冰扩容、另一方专职清理存量)产生的总匹配数与双向模式极为接近,双向交互带来的边际增量十分有限;同时,由女性发起交互时的总匹配数普遍高于男性发起(在 DHT、Greedy 和 Partner 下增幅尤为明显)。

六、经济与管理启示

本文的理论证明与实证发现不仅为在线约会平台的算法迭代与产品设计提供了直接指南,也为更广泛的动态双边撮合市场带来了深刻的经济与管理启示:

  • 启示一:双边匹配优化必须摒弃“单边贪心思维”,着眼跨期双向转化平衡。在双边精选市场中,单纯追求当期点击率或单侧点赞率(如 Greedy 算法)极易将大量曝光集中于少数高人气用户,导致头部用户待处理队列严重拥堵、回赞率低下,进而引发系统性匹配枯竭。平台算法应当将“发起方的初始喜欢概率”与“回应方的后续回赞概率及展示位容量”联合优化,通过适度牺牲部分单向高赞曝光来换取更高的双向闭环转化率,从根源上缓解人气偏差(popularity bias)与拥堵外部性。

  • 启示二:算法工程化应兼顾“消除舍入损耗”与“算力—自适应性权衡”。DH-int 表明,在滚动前瞻框架中对当期执行变量直接施加整数约束,既能规避连续解舍入带来的隐性效率损失,又不会显著拖累求解速度,是追求极致匹配率平台的优选方案。而对于用户规模庞大、实时计算成本高昂的平台,DHT 提供了极具实用价值的“半自适应”折中路径:将重度计算前置为低频批处理(预先规划冷启动破冰队列),仅在清理存量反馈时保持轻量化实时响应,即可在大幅节约服务器资源的同时保住绝大部分匹配收益。

  • 启示三:精选式单向交互机制可有效简化市场摩擦,且需顺应双边选择不对称性。实证表明,在存在存量积累与多期交互的环境中,允许双侧同时发起交互的边际增益非常有限。平台完全可以通过“单向引导”(例如由选择更审慎、通常更稀缺的一侧——如约会市场中的女性——率先发起,或分角色错峰交互)来降低用户决策负担、抑制无效盲赞并提升匹配质量,同时在理论上确保轻量级半自适应算法也能逼近全自适应最优边界。

  • 启示四:将用户行为动态与产品功能设计融入算法闭环,重点防范使用倦怠。用户并非静态偏好机器,其决策受近期匹配饱和度、使用疲劳度及付费提示信号的显著驱动。一方面,付费“谁喜欢了我”等信号功能可有效抬升存量回赞概率,平台应将此类信号溢价纳入算法权重以放大商业化与匹配率的双赢效应;另一方面,鉴于 DH-int 在持续性“参与倦怠(Disengagement)”场景下与理论上限的差距相对扩大,平台在运营中需通过节奏控制、限量精选与激励机制延缓用户随时间流失的活跃度,而非仅仅依赖后期算法补救。

  • 启示五:核心框架可广泛迁移至自由职业、网约车与共享住宿等动态双边平台。本文提炼的“有限曝光配额、跨期双向确认、存量动态管理与历史依赖偏好”结构具有高度普适性。在自由职业雇佣平台(如 Upwork)、在线招聘、短租住宿(如 Airbnb 房东—房客双向确认)以及共享出行平台中,供给方与需求方同样面临筛选疲劳、申请积压与相互确认延迟。借鉴 DH-int 与 DHT 的前瞻排序与存量协调思想,有助于各类双边市场在有限注意力约束下显著提升整体成交率与生态留存。

七、参考文献

本文核心文献:Rios I, Torrico A (2026) The Dating Heuristic: A Provably Strong Matching Algorithm for Dating Platforms. Manufacturing & Service Operations Management 28(6):1837–1855. https://doi.org/10.1287/msom.2024.1053

原文所附参考文献(按原文首字母顺序):

[1] Adamczyk M (2011) Improved analysis of the greedy algorithm for stochastic matching. Inform. Processing Lett. 111(15):731–737.

[2] Agrawal S, Ding Y, Saberi A, Ye Y (2010) Correlation robust stochastic optimization. Proc. Twenty-First Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1087–1096.

[3] Aouad A, Saban D (2022) Online assortment optimization for two-sided matching platforms. Management Sci. 69(4):2069–2087.

[4] Arnosti N, Shi P (2020) Design of lotteries and wait-lists for affordable housing allocation. Management Sci. 66(6):2291–2307.

[5] Ashlagi I, Krishnaswamy A, Makhijani R, Saban D, Shiragur K (2022) Technical note—Assortment planning for two-sided sequential matching markets. Oper. Res. 70(5):2784–2803.

[6] Bansal N, Gupta A, Li J, Mestre J, Nagarajan V, Rudra A (2012) When LP is the cure for your matching woes: Improved bounds for stochastic matchings. Algorithmica 63:733–762.

[7] Besbes O, Castro F, Lobel I (2021) Surge pricing and its spatial supply response. Management Sci. 67(3):1350–1367.

[8] Besbes O, Fonseca Y, Lobel I, Zheng F (2023) Signaling competition in two-sided markets. Proc. 24th ACM Conf. Econom. Computation (ACM, New York), 293.

[9] Celdir ME, Cho SH, Hwang EH (2024) Popularity bias in online dating platforms: Theory and empirical evidence. Manufacturing Service Oper. Management 26(2):537–553.

[10] Chen N, Nasiry J (2020) Does loss aversion preclude price variation? Manufacturing Service Oper. Management 22(2):383–395.

[11] Chen N, Immorlica N, Karlin AR, Mahdian M, Rudra A (2009) Approximating matches made in heaven. Automata, Languages and Programming (Springer, Berlin, Heidelberg), 266–278.

[12] Cui T, Hamilton M (2024) Pricing strategies for online dating platforms. Preprint, submitted March 24, http://dx.doi.org/10.2139/ssrn.4032735.

[13] Gamlath B, Kale S, Svensson O (2019) Beating greedy for stochastic bipartite matching. Proc. Thirtieth Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 2841–2854.

[14] Gandhi R, Khuller S, Parthasarathy S, Srinivasan A (2006) Dependent rounding and its applications to approximation algorithms. J. ACM 53(3):324–360.

[15] Guo MA, Jiang H, Shen ZJM (2025) Multiproduct dynamic pricing with reference effects under logit demand. Manufacturing Service Oper. Management 27(5):1645–1663.

[16] Halaburda H, Piskorski MJ, Yıldırım P (2018) Competing by restricting choice: The case of search platforms. Management Sci. 64(8):3574–3594.

[17] He T, Zhang Y, Zheng H (2024) Assortment optimization under history-dependent effects. Preprint, submitted August 20, https://arxiv.org/abs/2408.10967.

[18] Hu Z, Nasiry J (2018) Are markets with loss-averse consumers more sensitive to losses? Management Sci. 64(3):1384–1395.

[19] Immorlica N, Lucier B, Manshadi V, Wei A (2022) Designing approximately optimal search on matching platforms. Management Sci. 69(8):4609–4626.

[20] Jeloudar M, Lo I, Pollner T, Saberi A (2021) Decentralized matching in a probabilistic environment. Proc. 22nd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 635–653.

[21] Kagan E, Leider S, Sahin O (2025) Sequential decision making: From decision elicitation to strategy identification. Management Sci., ePub ahead of print September 22, https://doi.org/10.1287/mnsc.2023.02381.

[22] Kanoria Y, Saban D (2021) Facilitating the search for partners on matching platforms. Management Sci. 67(10):5990–6029.

[23] Kök AG, Fisher ML, Vaidyanathan R (2015) Assortment planning: Review of literature and industry practice. Agrawal N, Smith S, eds. Retail Supply Chain Management, International Series in Operations Research & Management Science, vol. 223 (Springer, Berlin), 175–236.

[24] Lee S, Niederle M (2015) Propose with a rose? Signaling in internet dating markets. Experiment. Econom. 18(4):731–755.

[25] Long X, Nasiry J, Wu Y (2020) A behavioral study on abandonment decisions in multistage projects. Management Sci. 66(5):1999–2016.

[26] Manshadi V, Rodilitz S (2022) Online policies for efficient volunteer crowdsourcing. Management Sci. 68(9):6572–6590.

[27] Manshadi V, Rodilitz S, Saban D, Suresh A (2024) Online algorithms for matching platforms with multi-channel traffic. Management Sci. 71(9):7674–7691.

[28] Özer O, Zheng Y (2016) Markdown or everyday low price? The role of behavioral motives. Management Sci. 62(2):326–346.

[29] Rios I, Ghosh P (2024) Competition in optimal stopping: Behavioral insights. Manufacturing Service Oper. Management 26(6):2256–2273.

[30] Rios I, Saban D, Zheng F (2023) Improving match rates in dating markets through assortment optimization. Manufacturing Service Oper. Management 25(4):1304–1323.

[31] Rochet JC, Tirole J (2003) Platform competition in two-sided markets. J. Eur. Econom. Assoc. 1(4):990–1029.

[32] Torrico A, Carvalho M, Lodi A (2020) Multi-agent assortment optimization in sequential matching markets. Preprint, submitted June 8, https://doi.org/10.48550/arXiv.2006.04313.

[33] Wang R (2018) When prospect theory meets consumer choice models: Assortment and pricing management with reference prices. Manufacturing Service Oper. Management 20(3):583–600.