Ehsani、Hajiaghayi、Kesselheim 与 Singla（SODA 2018）给出了矩阵先知‑秘书问题以及带 XOS 估值函数的先知‑秘书问题的 $(1-1/e)$ 竞争比。本文证明这两个比率的极限不同。我们为任意矩阵构造了一个随机 $(1-1/e+\varepsilon_0)$ 竞争算法，其中 $\varepsilon_0=10^{-6}$，该保证适用于独立的非负值且期望最优解有限。若给定的是有限分布且取值与概率为有理数，算法在矩阵独立性 oracle 模型下的最坏情况运行时间为多项式。算法期望调用 $O(N^4)$ 次独立性查询，最坏情况下 $O(N^4\log(N+2))$ 次，$N$ 为元素数量。进一步地，在 i.i.d. 版本中，我们提供了 $0.6767$ 的竞争比，对所有矩阵均成立，前提是权重来自已知分布的非负 i.i.d. 随机变量。该保证甚至在固定到达顺序（即 i.i.d. 矩阵先知不等式）下仍有效，算法仅在元素到达时学习顺序。相反，对于具有 XOS 估值的组合拍卖，$1-1/e$ 是最优竞争比。我们给出一族显式的有限实例，证明即使买家估值 i.i.d.、每个加法子句系数仅为 $0$ 或 $1$，且计算资源无限制，任何在线算法也无法超过 $1-1/e$。因此，矩阵上的改进利用了 XOS 估值一般分配中不存在的结构。
点评