直播pk算法的思考

直播 pk 推荐问题的工作流

直播 pk 主要分为随机pk和推荐pk，他们的流程分为是：

• 随机pk:
  • 一段时间内，点击了随机pk的主播会被加到候选池，此时要对池子内的主播进行两两匹配，pk开始。
  • 如果其中一方主播不愿意继续打pk，可以退出，重新选择；否则直到一场pk完成（一般为5分钟）。
  • 由于随机pk双方的发起流程都是系统匹配，所以双方是平等的，因此可以建模成一个无向图模型
• 推荐pk:
  • 主播在推荐列表内邀请主播pk；
  • 对面主播接受或拒绝邀请；
  • 开始pk，最终完成pk或中途结束。
  • 推荐pk需要发起方的主播点击邀请按钮，所以发起方和接收方的情况是不同的，因此推荐pk问题可以建模成一个有向图模型

推荐PK最优化建模

推荐pk的问题描述

一共 $n$ 个主播，要为每个主播推荐 $k$ 个其他主播（ $k$ 为推荐列表长度） 为主播 $i$ 推荐主播 $j$ 时的期望收益为 $gain(i,j)=ctr_{ij}\cdot rtr_{ji} \cdot r_{ij}$

• $ctr_{ij}$：为主播 $i$ 推荐主播 $j$ 时，主播 $i$ 的点击率；注意 $ctr_{ij}\neq ctr_{ji}$ ，即点击邀请率左右屏不对称
• \(rtr_{ij}\)：主播 $j$ 接收主播 $i$ 邀请的概率，即接受率；注意 $rtr_{ij}\neq rtr_{ji}$ ，即接收率左右屏不对称

$r_{ij}$ ：主播 $i$ 与主播 $j$ 打一场pk产生的总收益

最大化总体期望收益

\(\begin{align} E(Gain)^*=\max&\sum_{i}^{N}\sum_{j}^{N}{I_{ij}\cdot gain(i,j)} \\ s.t.& \sum_i^N{I_{ij}}=k, \forall j \quad\quad\quad\quad\quad\quad\space(1)\\ &\sum_j^N{I_{ij}\cdot ctr_{ij}\cdot rtr_{ij}}\leq\beta,\forall i\quad(2) \end{align}\)

• 集合 ${I_{ij}}$ 表示问题的解
• 约束（1）：为主播 $j$ 推荐 $k$ 个其他主播
• 约束（2）：对于任意主播 $i$ 而言，其被推荐给其他主播且与其他主播成功开始pk（开始pk后则被资源独占）的期望概率不大于 $\beta$。其中 $\beta$ 一般可以选择大于等于1的数，表示”超卖率”；当 $\beta=1$ 时表示不超卖，适当的增加 $\beta$ 有助于提升稀缺资源（高营收主播）的利用效率。 当仅有约束（1）时，解为贪心策略，给每个主播推荐 $gain(i,j)$ 最大的即可，等价于目前线上的推荐策略；增加约束（2）则同时考虑了稀缺资源的可分配性，即优质的稀缺资源可被重复推荐的次数是有限的，必须合理分配以使得全局最优。

随机PK最优化

随机pk可以直接简化成一般图的最优匹配问题，由于同时发起pk的人数有限（<1000），因此可以应用匈牙利算法在$o(N^3)$的时间内计算出结果。

推荐pk求解

针对推荐pk而言，候选的主播非常多，因此直接使用匈牙利算法求解不现实。工业界针对此类复杂度较高的问题，一般采用启发式算法。例如，可以采用模拟退火算法、遗传算法等求解近似最优解，以满足工业界实时计算的需求。