This paper disproves the long‑standing conjecture that the competitive ratio of Online Budgeted Allocation equals $1-1/e$. The authors construct a family of input instances and show that for any randomized online algorithm the competitive ratio is strictly bounded away from $1-1/e$, i.e., there exists an absolute constant $\varepsilon>0$ such that
$$\text{CR} \le 1 - \frac{1}{e} - \varepsilon.$$
In the online budgeted allocation model, a set of advertisers each has a budget $B_i$, and a sequence of ad requests arrives online. Each request corresponds to an edge $(i,j)$ with weight $w_{ij}$ representing the revenue if request $j$ is assigned to advertiser $i$. The algorithm must decide irrevocably upon arrival while respecting budgets. The competitive ratio is the expected online revenue divided by the optimal offline revenue.
The paper first revisits the classic $1-1/e$ upper bound derived from the randomized Balance algorithm and its matching lower‑bound construction. Then, using a refined primal‑dual analysis, the authors design a set of “high‑value‑low‑frequency” requests that force any algorithm to forfeit a portion of high‑value assignments under budget constraints, causing a loss in total gain. Core technical ingredients include:
- Dynamic adjustment of dual variables to capture potential loss of online decisions;
- Application of concentration inequalities to show a fixed gap $\varepsilon$ between expected online gain and the dual upper bound under random order;
- Construction of a specific distribution family demonstrating that the gap is a constant independent of instance size.
The full proof framework establishes that no randomized online algorithm can achieve a competitive ratio of $1-1/e$, thereby refuting the conjecture. This result has significant implications for the theoretical limits of online ad allocation and related resource‑allocation problems.
Review: By combining rigorous dual analysis with a clever instance construction, the authors break the $1-1/e$ barrier that has stood for years. The work opens new avenues for tightening competitive‑ratio bounds and investigating conditions under which the classic $1-1/e$ ratio might still be attainable.