offer 超发问题

Posted on Waline:

现有 \(n\) 个求职者，\(m\) 个公司，每个公司均招聘 \(t\) 人。每个公司可以均匀随机地给任意个求职者发放 offer，每个求职者会在其收到的所有公司的 offer 中均匀随机选择一个加入。设 \(n \geq mt\)。

求每个公司应该发放的 offer 数 \(o_i\)，使得该公司能招聘到的期望人数恰好为 \(t\)。

均匀 HC 下的解答

引理

设随机变量 \(X \sim B(n, p)\)，则

\[ E\left(\frac{1}{X+1} \right) = \frac{1 - (1-p)^{n+1}}{p(n+1)}. \]

设随机变量 \(X \sim \text{Poisson}(\lambda)\)，则

\[ E\left(\frac{1}{X+1} \right) = \frac{1 - \mathrm e^{- \lambda}}{\lambda}. \]

证明 仅以二项分布为例，泊松分布可同理得到。

\(X\) 的概率生成函数为

\[ G_X(t) = E(t^X) = (1 - p + pt)^n, \]

注意到

\[ \frac{1}{X+1} = \int_0^1 t^X \, \mathrm d t, \]

那么

\[ \begin{aligned} E\left(\frac{1}{X+1} \right) &= E\left( \int_0^1 t^X \, \mathrm d t \right) \\ &= \int_0^1 E(t^X) \, \mathrm d t \\ &= \int_0^1 (1 - p + pt)^n \, \mathrm d t \\ &= \frac{1 - (1-p)^{n+1}}{p(n+1)}. \end{aligned} \]

解答

在均匀 HC 假设下，每个公司发放的 offer 数相等为 \(o\)。

对每个求职者，其等概率地收到来自每个公司的 offer，该概率为 \(\frac{o}{n}\)。

对于公司 \(i\) 的一个特定 offer，收到该 offer 的求职者收到其他公司的 offer 数 \(S_i\) 服从二项分布，即 \(S_i \sim B(m - 1, \frac{o}{n})\)。

那么，求职者加入公司 \(i\) 的概率为

\[ E \left(\frac{1}{S_i+1} \right) = \frac{1 - (1 - \frac{o}{n})^m}{m \cdot \frac{o}{n}}. \]

公司 \(i\) 期望招聘到的人数为

\[ o \cdot E \left(\frac{1}{S_i+1} \right) = \frac{n}{m}\left(1 - \left(1 - \frac{o}{n} \right)^m \right). \]

令上式 \(=t\)，解方程得到

\[ o = n \left(1 - \left(1 - \frac{mt}{n} \right)^{1/m} \right). \]

特殊值观察

变化 \(n\)
  • \(n = \sum_{i=1}^m a_i = mt\)

此时有 \(o = n\)，即所有公司向所有求职者发放 offer，此时所有求职者每个均匀随机选择一个公司加入。

  • \(n \to \infty\)

注意到，当 \(x \to \infty\) 时有 \((1+x)^a \sim 1 + ax\)，即 \((1 + x)^a - 1 \sim ax\)，故

\[ \left(1 - \frac{mt}{n} \right)^{1/m} - 1 \sim \frac{1}{m} \left(-\frac{mt}{n} \right) = -\frac{t}{n}. \]

故

\[ 1 - \left(1 - \frac{mt}{n} \right)^{1/m} \sim \frac{t}{n}. \]

于是

\[ \lim_{n \to \infty} o = t. \]

即所有公司只需恰好发放 \(t\) 个 offer，由于求职者人数足够多，几乎不存在获取了多个 offer 的求职者，因此每个公司都能招聘到 \(t\) 个求职者。

对于给定的 \(n \in [\sum_{i=1}^m a_i, +\infty)\)，\(o(n)\) 单调递减。

因此，在岗位供大于求的情况下，报录比越高，每个公司所需发放的 offer 数越少。

变化 \(m\)

\(m\) 的范围需要保证 \(n \geq \sum_{i=1}^m a_i = mt\)，即 \(m \in [1, \frac{n}{t}]\)，否则无意义。

  • \(m=1\)

此时 \(o = t\)，即不存在竞争。

  • \(m=2\)

此时

\[ o = n \left(1 - \sqrt{1 - \frac{2t}{n}} \right). \]

  • 当 \(m = n/t\) 时，\(o = n\)，此时竞争最激烈，每个公司都需要向所有求职者发放 offer。

对于给定的 \(m \in [1, \frac{n}{t}]\)，\(o(m)\) 单调递增。

因此，在岗位供大于求的情况下，同梯队公司越多，每个公司所需发放的 offer 数越多。

变化 \(t\)

\(t\) 的取值范围为 \([1, \frac{n}{m}]\)。显然有 \(o(0) = 0, o(\frac{n}{m}) = n\)。

对于给定的 \(t \in [1, \frac{n}{m}]\)，\(o(t)\) 单调递增。

因此，在岗位供大于求的情况下，HC 越多，每个公司所需发放的 offer 数越多。

变化市场整体报录比

市场整体报录比为 \(u = \frac{n}{mt}\)，此时

\[ o = mtu \left(1 - \left(1 - \frac{1}{u} \right)^{1/m} \right). \]

  • \(u=1\)，则 \(o = n = mt\)，所有公司向所有求职者发放 offer。
  • \(u \to \infty\)，则 \(o \to t\)。

对给定的报录比，若所有公司统一发放 \(k\) 倍 HC 的 offer，即 \(o = kt\)，那么有

\[ k = mu \left(1 - \left(1 - \frac{1}{u} \right)^{1/m} \right) \]

这就是在给定 \(m\) 和报录比 \(u\) 下，offer 发放的最优倍率。当 \(m\) 增大时，\(k\) 单调递增；\(u\) 增大时，\(k\) 单调递减。特别地，当 \(m \to \infty\) 时，上式有极限

\[ \lim_{m \to \infty} k = u \ln \left( \frac{u}{u-1} \right) \]

即，报录比越大，公司超发 offer 的比例越小；同梯队公司越多，公司超发 offer 的比例越大。

可以据此估计 \(m \to \infty\) 时公司超发 offer 的最优倍率。例如，当报录比 \(u = 1.25\) 时，offer 发放的最优倍率为 \(k \approx 2.0\)。

其他推广

推广：

  • 非均匀 HC：第 \(i\) 个公司的招聘人数为 \(a_i\)。
  • 加权选择公司：每个求职者会根据其收到的所有公司的 offer，加权随机选择一个加入。例如，若公司 \(i\) 的权重为 \(w_i\)，则其加入公司 \(i\) 的概率为 \(\frac{w_i}{\sum_{j \in r} w_j}\)，其中 \(r\) 为该求职者收到的公司的 offer 集合。该权重可能因求职者而异。
  • 有限投递：每个求职者仅投递若干家公司，因此只可能收到这些公司的 offer。
  • 加权发放 offer：每个求职者具有权重 \(w_i\)，每个公司对其发放 offer 的概率为 \(\frac{w_i}{\sum_{j \in r} w_j}\)，其中 \(r\) 为投递该公司的求职者集合。该权重可能因公司而异。
  • 完全信息博弈：对每个求职者，其每投递一个公司都将支付 \(c_1\) 的代价，且最终获得的 offer 数 \(l\) 将为其获取 \(f(l)\) 的收益；对每个公司，在其招聘人数的基础上每超出一个人入职都将支付 \(c_2\) 的代价，而每缺少一个人入职都将支付 \(c_3\) 的代价。为每个求职者和每个公司制定投递和 offer 发放的策略，使得收益最大化。
  • 不完全信息博弈：在以上完全信息博弈的基础上，对每个求职者，求职者的总数、其他求职者投递的公司、其他求职者的权重、公司的招聘人数不完全可见；对每个公司，求职者的总数、其他公司的招聘人数不完全可见。

非均匀 HC：\(m=2\) 的例子

现有 \(n\) 个求职者，\(m = 2\) 个公司，分别招聘 \(a_1 = 1, a_2 = 2\) 人。每个公司可以随机地给任意个求职者发放 offer，每个求职者会在其收到的所有公司的 offer 中均匀随机选择一个加入。设 \(n \geq \sum_{i=1}^m a_i\)。

求每个公司应该发放的 offer 数 \(o_i\)，使得该公司期望能招聘到的人数恰好为 \(a_i\)。

解答

对每个求职者，其收到来自第 \(i\) 个公司的 offer 的概率为 \(\frac{o_i}{n}\)。

只考虑收到了第 \(1\) 个公司的 offer 的求职者：

  • 若其总共只收到了第 \(1\) 个公司的 offer，则其加入概率为 \(1\)；
  • 若其总共收到了 2 个公司的 offer，则其加入概率为 \(1/2\)。

故每个收到了第 \(1\) 个公司的 offer 的求职者加入第 \(1\) 个公司的概率为

\[ p_1 = \left(1 - \frac{o_2}{n} \right) \cdot 1 + \frac{o_2}{n} \cdot \frac{1}{2} = 1 - \frac{o_2}{2n}. \]

同理，每个收到了第 \(2\) 个公司的 offer 的求职者加入第 \(2\) 个公司的概率为 \(p_2 = 1 - \frac{o_1}{2n}\)。故 \(\forall i\)，列出方程组

\[ o_i p_i = a_i, \]

排除不合适的解后，得

\[ o_1 = \frac{2n - 1 - \sqrt{4n^2 - 12n + 1}}{2}, \]

\[ o_2 = \frac{2n + 1 - \sqrt{4n^2 - 12n + 1}}{2}. \]

代入特殊值 \(n=3\)，得到 \(o_1 = 2, o_2 = 3\)，符合预期。

对 \(m=2\) 的情况，可推出一般的解析式，且满足 \(o_2 - o_2 = a_1 - a_2\)，这里留作练习。

非均匀 HC：一般情况

对任意 \(m\) 的情况，每个公司招聘 \(a_i\) 人，这是一个难题。

对每个求职者，其收到来自第 \(i\) 个公司的 offer 的概率为 \(\frac{o_i}{n}\)。

对每个收到了第 \(i\) 个公司的 offer 的求职者，考虑他收到的其他公司的 offer 数 \(S_i\)，那么

\[ S_i = \sum_{j \neq i} Y_j, \]

其中 \(Y_j \in \{0, 1\}\) 表示该求职者收到的公司 \(j\) 的 offer 数，服从参数为 \(\frac{o_j}{n}\) 的 0-1 分布，有 \(E(Y_j) = \frac{o_j}{n}\)，故 \(E(S_i) = \frac{1}{n} \sum_{j \neq i} o_j\)。

那么，求职者加入公司 \(i\) 的概率为

\[ p_i = E \left(\frac{1}{S_i+1} \right). \]

由于 \(S_i\) 是 \(m-1\) 个不同参数的 0-1 分布之和，因此上式很难给出解析的结果，是一个积分方程。

若考虑当 \(m\) 很大，\(\frac{o_j}{n}\) 很小时，\(S_i\) 可近似为泊松分布，其 \(\lambda_i = E(S_i) = \frac{1}{n} \sum_{j \neq i} o_j\)，那么

\[ p_i = E \left(\frac{1}{S_i+1} \right) = \frac{1 - \mathrm e^{- \lambda_i}}{\lambda_i}. \]

最后列出方程组

\[ o_i p_i = a_i, \]

求解之即可（这不是一个线性方程组，因此很不好解）。

经过实验，很可能存在多解，但应该不会无解。

可能可以进一步近似

\[ \lambda_i \approx \frac{1}{n} \sum_{j = 1}^m o_j \]

即对所有 \(i\)，\(\lambda_i\) 近似相等。这需要 \(n,m\) 很大，且所有的 \(o_j\) 近似相等的假设。