本文驳斥了在线预算分配（Online Budgeted Allocation）竞争比为 $1-1/e$ 的长期猜想。作者构造了一类输入实例，并证明对任意随机在线算法，其竞争比上界严格小于 $1-1/e$，即存在一个绝对常数 $\varepsilon>0$ 使得
$$\text{CR} \le 1 - \frac{1}{e} - \varepsilon.$$
在线预算分配模型描述如下：给定一组广告主，每个拥有预算 $B_i$，以及一系列到达的广告请求，每个请求对应一个边 $(i,j)$，权值 $w_{ij}$ 表示将请求 $j$ 分配给广告主 $i$ 所获得的收益。算法必须在请求到达时即时决定是否分配且不能超过预算。竞争比定义为在线算法期望收益与最优离线解收益的比值。
作者首先回顾了经典的 $1-1/e$ 竞争比上界来源于随机化的平衡分配（Balance）算法及其对应的下界构造。随后通过精细的对偶分析，构造了一组“高价值‑低频率”请求，使得任何算法在保持预算约束的同时，都不可避免地放弃部分高价值请求，从而导致收益下降。关键技术包括：
- 对偶变量的动态调整，使得在线决策的潜在损失可以被下界函数捕获；
- 使用概率论中的集中不等式，证明在随机顺序下，算法的期望收益与对偶上界之间存在固定的差距 $\varepsilon$；
- 通过构造特定的分布族，展示该差距不依赖于输入规模，仅取决于常数 $\varepsilon$。
最终，作者给出完整的证明框架，证明了不存在竞争比达到 $1-1/e$ 的随机在线算法，因而原猜想被否定。该结果对在线广告分配、资源调度等领域的理论极限有重要影响。
点评：本文通过严谨的对偶分析和精巧的实例构造，成功突破了长期以来的 $1-1/e$ 上界壁垒，为在线预算分配的竞争比研究打开了新方向。未来工作可探索更紧的上界或在特定限制条件下恢复 $1-1/e$ 的可达性。