The Power of Flexible Budgets in Adwords

1. Introduction

• Budget flexibility addresses the mismatch between rigid daily limits and uneven traffic, while platforms must still respect a longer-horizon spending cap.The paper cites Google Ads’ allowance of up to twice the nominal daily budget on a day, capped at 30.4 times that budget monthly.Source: §1 · p. 2

1.1. Our Setting: D-day Adwords with δ-flexibility

• The model gives the online algorithm a δB_i daily limit and a DB_i horizon cap, while the offline benchmark retains a B_i daily limit and the same horizon cap.Arrivals are adversarial and queries arrive online.Source: §1.1 · p. 3

1.2. Main Results

• Direct exponential-penalty generalizations of Balance do not beat 1−1/e for any D or δ, because early aggressive spending can exhaust horizon budgets.A more conservative penalty on earlier days is needed.Source: §1.2 · p. 4
• For every D and δ, Algorithm 1 is optimal when the offline optimum exhausts each advertiser’s daily budget; its penalties depend on remaining horizon budget and days.This perfect-utilization setting models high traffic sufficient to use all daily budgets, but it does not always capture the general finite-horizon worst case.Source: §1.2 · pp. 4–5
• For each fixed δ ≥ 1, as D → ∞, Algorithm 1’s competitive ratio for the D-day Adwords problem with δ-flexibility converges to 1 − exp(−δ), matching the optimal guarantee without a horizon spending limit.Source: §1.2 · p. 5
• At D = δ = 2, the general setting’s optimal competitive ratio is strictly below the perfect-utilization ratio, which Theorem 1 gives as approximately 0.729.Extending the exact characterization beyond D = 2 requires identifying and balancing a growing family of candidate penalties that does not readily yield to analysis.Source: §1.2 · p. 6

1.3. Related Work

• The paper studies flexibility from a worst-case perspective and confines its results to the small-bid regime.Understanding flexibility beyond that regime is left for future work.Source: §1.3 · pp. 8, 10

• Ignoring flexibility and running classical Balance independently each day gives a (1−1/e)-competitive baseline for any D.The paper says this guarantee is optimal when flexibility is ignored.Source: §2 · p. 10
• Without a horizon spending limit, applying the exponential penalty fδ(x)=exp(x −δ) each day achieves the optimal ratio 1−exp(−δ).This thought experiment also identifies the optimal penalty on the last day of the main setting.Source: §2 · pp. 10–11
• For every D≥2 and δ∈[1,D], a direct generalization of Balance cannot guarantee a competitive ratio above 1−1/e.The paper also notes that applying the exponential penalty on every day can be too aggressive and perform strictly worse than the baseline.Source: §2 · pp. 11–12
• Algorithm 1 makes each reduced-bid penalty depend on both the advertiser’s remaining horizon budget and the number of remaining days.It assigns a query to an advertiser with the largest positive reduced bid, discarding it if none is positive.Source: §2 · p. 12
• Valid penalties are non-decreasing, equal 1 at the effective daily spending limit, and are C-Lipschitz.These conditions make reduced bids zero at the limit, prevent penalties from falling as spending rises, and bound their change across a query’s spend.Source: §2 · pp. 12–13
• For the same remaining budget r=3, the penalty is more conservative earlier in the horizon and approaches exp(x −2) on the last day.At day d=2, it also becomes more conservative as remaining horizon budget decreases.Source: §2 · p. 14

3.1. LP-Free Certificate

• A valid LP-free certificate proves α/β-competitiveness, while in the small-bid regime a factor-revealing program lower-bounds the algorithm’s competitive ratio.The certificate uses nonnegative θ_id and λ_t satisfying conditions (3) and (4); the program minimizes over admissible online and offline usages.Source: §3.1 · p. 17

3.2. Penalty Functions from the Perfect-Utilization Setting

• Under perfect utilization, recursive equalization yields Algorithm 1’s horizon-aware penalties, with continuation values interpreted through a capped mean-one exponential random variable.Here OPT exhausts each advertiser’s nominal daily budget; partial utilization can produce a strictly worse competitive ratio. The equalization makes the pseudo-reward independent of feasible current-day usage.Source: §3.2 · pp. 18, 20
• When r = 1, this recovers the 1 − 1/e guarantee of Balance in the classical Adwords problem; more generally, cancellation equalizes the last-day pseudo-reward across all feasible values of x2.The passage names this the equalization property.Source: §3.2 · p. 20

3.3. Optimality of Algorithm 1 in the Perfect-Utilization Setting

• In perfect utilization, Algorithm 1 is optimal at competitive ratio V_D(D)/D, and no online algorithm can exceed this bound.The upper bound is established against deterministic fractional online algorithms; the passage notes that it also applies to randomized algorithms.Source: §3.3 · p. 22
• The matching upper bound adaptively repeats a single-day upper-triangular instance, allowing OPT to use every nominal daily budget while restricting the online algorithm’s allocation.The proof fixes an arbitrary deterministic fractional online algorithm; the paper states that its upper bound also applies to randomized algorithms.Source: §3.3 · p. 22
• A single-day staged adversary removes the advertiser receiving the smallest allocation at each stage, bounding online allocations harmonically while allowing OPT to exhaust every advertiser’s nominal daily budget.The construction extends the classical 1 −1/e upper-bound construction; with spending limit κ, its asymptotic allocation bound is based on a capped mean-one exponential variable.Source: §3.3 · pp. 23–24
• The upper bound partitions advertisers by cumulative usage into slabs, applies separate single-day blocks with relaxed spending limits, and lets slab widths shrink to eliminate relaxation error.As slab sizes vanish, the construction yields the target value VD(D).Source: §3.3 · pp. 24, 25, 27
• Algorithm 1 is optimal in the perfect-utilization setting, achieving competitive ratio VD(D)/D.The proof combines its lower bound with a matching upper-bound construction.Source: §3.3 · p. 26

4.1. Asymptotic Optimality of Algorithm 1

• For every fixed δ, Algorithm 1’s competitive ratio converges to 1−exp(−δ) as D →∞, matching the asymptotic guarantee established for the perfect-utilization penalty functions.Theorem 2 gives a finite-horizon guarantee that supports this convergence.Source: §4 · p. 28, §4.1 · p. 30

4.2. Exact Characterization for D = δ = 2

• At D = δ = 2, the exact general-setting competitive ratio is approximately 0.701, below the perfect-utilization value V2(2)/2 ≈0.729.The optimal ratio is 1 − exp(−h∗), where h∗ uniquely solves (1 + h∗)exp(h∗−2) = 1.Source: §4 · p. 28, §4.2 · p. 31
• The general-setting optimal first-day penalty switches from an exponential penalty to the more conservative perfect-utilization penalty at sufficiently high first-day usage.The second-day optimal penalty remains exponential; the first-day choice balances differing offline-utilization patterns.Source: §4.2 · pp. 31–32
• The matching upper bound uses a remaining-budget threshold h∗ to select advertisers receiving second-day arrivals, limiting online usage while allowing OPT another nominal daily budget.Advertisers above the threshold receive no second-day arrivals; those at or below it have already spent at least 2 − h∗ of their horizon budget.Source: §4.2 · p. 33
• The threshold argument also rules out an advantage from deliberately withholding first-day usage: reducing usage cannot increase the algorithm’s contribution to ALG − (1−exp(−h∗))OPT.This follows from the monotonicity of ψ.Source: §4.2 · pp. 34–35

5. Conclusion

• For every fixed δ, Algorithm 1 achieves the optimal worst-case guarantee asymptotically as D →∞, matching the guarantee without a horizon spending limit.The conclusion states that the algorithmic loss due to the horizon spending limit vanishes as the number of days grows.Source: §5 · p. 36
• The power of budget flexibility beyond the small-bid regime and the exact finite-horizon optimum in the general setting remain open.The latter may require balancing candidate penalty functions across remaining-horizon budgets.Source: §5 · p. 37

A.1. Validity of the Penalty Functions in (2)

• The penalty function takes values in [exp(−δ),1] and reaches 1 at the end of its domain.Source: §A.1 · p. 40
• The derivative argument establishes that each penalty function is non-decreasing over its domain.Source: §A.1 · p. 40
• The penalty function is 1-Lipschitz, completing the stated validity checks.Source: §A.1 · p. 40

A.2. Proof of Lemma 2

• In the small-bid regime, a reduced-bid algorithm with valid penalty functions has competitive ratio at least Γf, the lower bound supplied by the factor-revealing program.Source: §A.2 · pp. 41, 43
• The proof relates query-level reduced bids to integrated penalty contributions over realized usage, with actual charges potentially smaller when a query exhausts an effective spending limit.Source: §A.2 · p. 41
• Boundary-query discrepancies are bounded by tracking how many such queries each advertiser receives and their normalized usage contributions.Except possibly for the query exhausting remaining horizon budget, a boundary query occurs on a day with effective spending limit at least one.Source: §A.2 · p. 43

A.3. Proof of Lemma 4

• H_d,r(x) is constant for every x in [0,c(r)], establishing the equalization property.The lemma identifies this constant as V_D−d+1(r).Source: §A.3 · p. 44
• The constant value of H_d,r(x) is V_D−d+1(r).This is the exponential reinterpretation in Lemma 4.Source: §A.3 · p. 44
• Applying the exponential trick with h(·)=f(· | r,d) uses f(c(r) | r,d)=1 and the constancy of H.The proof concludes that H is constant over [0,c(r)].Source: §A.3 · pp. 44–45

A.4. Asymptotic Property of the Harmonic Bound

• The harmonic bound H_N(U_N) converges in distribution to a mean-one exponential random variable when U_N is uniform on [N].With spending limit κ, the average capped harmonic bound converges to E[min{Z,κ}].Source: §A.4 · p. 45
• For fixed κ, the capped harmonic bound converges in expectation because x↦min{x,κ} is bounded and continuous.The argument applies convergence in distribution to the capped function.Source: §A.4 · p. 45
• 1−e^−κ is the asymptotic upper bound yielded by the single-day upper-triangular block.The bound follows after taking B→∞ for fixed N and then N→∞.Source: §A.4 · p. 46

Appendix B: Tight Characterization of the Thought Experiment

• The reduced-bid algorithm’s competitive ratio in the thought experiment is lower-bounded by 1−exp(−δ).This is the lower-bound direction for the exact characterization.Source: Appendix B · p. 46
• 1−exp(−δ) is the exact optimal competitive ratio in the single-day thought experiment and an upper bound in the main setting.The thought experiment is analyzed day by day because the algorithm has no horizon spending limit and receives a fresh normalized budget δ each day.Source: Appendix B · p. 46, Appendix E · p. 47

Appendix E, it is sufficient to consider an arbitrary deterministic fractional online algorithm.

• The upper-bound proof suffices for arbitrary deterministic fractional online algorithms and combines with the lower bound to establish the exact ratio.It applies the single-day upper-triangular construction with κ=δ and the harmonic-bound limit.Source: Appendix E · pp. 46–47

Appendix C: A Limitation of Direct Generalizations of Balance

• Direct exponential generalizations of Balance cannot improve upon the classical 1−1/e guarantee.For the scaled exponential penalty family with β≥1, the stated upper bound is strictly below 1−1/e when β>1.Source: Appendix C · pp. 47–49
• The extended penalty scales the classical Balance penalty by β and uses the current-day spending limit r.The stated family has β≥1; choosing r=β=1 recovers classical Balance in a single day.Source: Appendix C · p. 47
• The construction uses two advertisers and adaptive arrivals in the small-bid regime, with shared queries followed by advertiser-1-only queries.The shared queries are compatible with both advertisers; the later unit-bid queries are compatible only with advertiser 1.Source: Appendix C · p. 48
• Every shared query is assigned to advertiser 1 when advertiser 2 is active, because advertiser 1’s reduced bid is higher.The argument proceeds by induction over the shared queries.Source: Appendix C · p. 49
• Advertiser 1 reaches its effective daily limit and gains no value from the remaining advertiser-1-only queries, yielding a competitive-ratio upper bound of ρ(β).The argument uses the normalized horizon-spending constraint S≤D and lets ϵ→0.Source: Appendix C · pp. 48–49
• G(β) increases and ρ(β)=1/(1+G(β)) decreases, so ρ(β)≤1−1/e for every β≥1.The inequality is strict when β>1.Source: Appendix C · p. 49

Appendix D: From Primal-Dual to LP-Free Analysis

• Direct pairwise primal-dual analysis recovers only the 1 −1/e guarantee in this setting.The classical analysis is associated with Buchbinder et al. 2007 and Devanur et al. 2013.Source: Appendix D · p. 50
• Varying local guarantees by advertiser-day is less transparent because penalties and their domains depend on remaining horizon budgets shaped by earlier online usage.The passage motivates seeking an amortized certificate instead of characterizing each local factor directly.Source: Appendix D · pp. 50–51
• Amortizing across days for each advertiser leads to the LP-free framework of Goyal et al. (2025), used in Section 3.1.Source: Appendix D · p. 51

Appendix E: Why deterministic fractional algorithms are sufficient for upper bounds

• Deterministic fractional online algorithms suffice for upper bounds on randomized algorithms because conditional expected allocations preserve feasibility and expected reward.The construction assigns each query according to the randomized algorithm's conditional expected fractions.Source: Appendix E · p. 52

Appendix F: Additional Details for the Proof of Theorem 1

• Φ_d is non-decreasing and 1-Lipschitz.Source: Appendix F · p. 52
• Parameter choices in the prescribed order yield the V_D(D)/D + ε upper bound for every ε > 0.The choices make the error arbitrarily small by selecting M, ξ, N, and then B in sequence.Source: Appendix F · pp. 52–53
• For sufficiently large slabs, the proof uses convergence of H_n(U_n) to an Exp(1) random variable to relate an expectation to Φ_d(ℓ_m).The passage states that each slab of size at least K satisfies the resulting bound.Source: Appendix F · p. 54
• Slabs smaller than K contain fewer than MK advertisers and contribute at most DMK in total.Source: Appendix F · p. 54

Appendix G: Additional Details for the Proof of Theorem 3

• For fixed x, the minimum over λ is attained at λ ∈ {0, 1/2, 1}.The proof evaluates the expression at these three values using the listed (o1, o2) choices.Source: Appendix G · p. 55
• For (o1, o2) = (1, 0), the proof verifies the lower bound 1 − e^-h*.Source: Appendix G · p. 55
• For (o1, o2) = (1, 1), F*(x) + 2 − f*(x | 2,1) − e^(x−2) is at least 2(1 − e^(−h*)) when h* < 2 and x ≤ 2 − h*.Source: Appendix G · p. 55