Theorem 9, p. 15 — no randomized online algorithm for b-matching has competitive ratio better than 1 − 1/e, uniformly in the budget b

Consider online b-matching: $N$ bidders, each with the same integer budget $B \ge 1$, bidding $0$ or $1$ on each of $NB$ queries that arrive online.

For every $\delta > 0$ there is $N_0$ such that for every $N \ge N_0$, every budget $B \ge 1$ and every randomized online algorithm $A$ for instances with $N$ bidders and $NB$ queries, there exist an instance $I$ and an offline allocation $\tau$ with

Thus no randomized online algorithm achieves a competitive ratio better than $1-1/e$ for b-matching, and this holds for every budget $b$, in particular for large $b$, where the deterministic algorithm BALANCE attains $1-1/e$ in the limit. The case $B=1$ is the online bipartite matching lower bound of Karp, Vazirani and Vazirani.

Formalization Note "Competitive ratio better than $1-1/e$" is negated as: for every $\delta>0$ some instance has expected revenue at most $(1-1/e+\delta)$ times its optimum; the optimum is witnessed by $\tau$ (no allocation can exceed $NB$, since each of the $N$ bidders is capped at $B$). The algorithm $A$ is quantified before the instance. "For large $b$" is rendered by quantifying over every $B\ge1$ with a threshold $N_0$ independent of $B$, which implies the statement for all large $b$. The paper's instance with budget $1$ and bids $\epsilon$ is the same instance scaled by $B=1/\epsilon$.