PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Stochastic Allocation with Increasing Returns

Shuo Sun, Yunduan Lin

arXiv:2609.34121v2cs.DSmath.OC

TL;DR

The paper asks how to allocate customers online when assignments build future rewards but arrivals may stop early, a setting less explored than fixed- or diminishing-return allocation. It analyzes the resulting online allocation problem and shows that classical approaches can fail arbitrarily badly, while homogeneous bonuses admit a tight 1/2 competitive ratio.

  • Problem

    Online allocation research has primarily considered fixed rewards or diminishing returns, leaving how to account for reward buildup under uncertain arrivals largely unexplored.

    Source: §1 · p. 2

  • Method

    The paper studies full-compatibility allocation with uncertain arrivals, where each assignment earns a base reward and a nondecreasing bonus based on prior assignments to that product.

    Source: §2 · p. 8

  • Results

    Greedy and natural LP-based rounding can perform arbitrarily poorly even with homogeneous bonuses, while homogeneous bonuses admit a tight 1/2 competitive ratio.

    Source: §1.1 · pp. 3–4, §3.1 · p. 10

  • Takeaways & Limitations

    Increasing returns make online decisions depend on coordinating reward buildup while retaining value if arrivals stop early.

    Source: §1 · p. 3

    The model assumes full compatibility: every arriving customer can be assigned to any product with remaining capacity.

    Source: §2 · p. 8

Abstract

from arXiv · show

We study online allocation with increasing returns, where an uncertain number of customers arrive sequentially and can be irrevocably assigned to any product with remaining capacity. Each assignment earns a base reward plus a bonus that is nondecreasing in the number of previous assignments to the same product. Prior work has focused primarily on fixed or diminishing returns. Under increasing returns, the central challenge is that concentrating assignments can unlock large future rewards, while a different product may be preferable if arrivals stop early. We show that classical approaches, including greedy and natural LP-based rounding algorithms, can perform arbitrarily poorly, even with homogeneous bonuses. We evaluate performance through competitive ratios relative to the hindsight offline optimum. For homogeneous bonuses, we establish a tight competitive ratio of $1/2$. For arbitrary heterogeneous bonuses, however, no online algorithm can guarantee a competitive ratio greater than $1/m$, where $m$ is the number of products. By imposing discrete concavity on the bonus functions, we limit the concentration of rewards in later assignments and restore constant guarantees. Under this structure, we develop a re-solving framework that repeatedly selects a planning horizon, constructs a feasible allocation plan from the current state, and executes its assignments in a specific order. For arbitrary arrival distributions, we design distribution-oblivious deterministic and randomized algorithms with competitive ratios of $0.2537$ and $0.3864$, respectively. For known increasing-failure-rate (IFR) arrival distributions, we exploit distributional information to obtain a deterministic $1/2$-competitive algorithm.

1. Introduction

The paper studies online allocation when assignments build future rewards but arrivals may stop before that buildup pays off. It characterizes guarantees across bonus structures and arrival information, and develops algorithms that coordinate allocation plans and execution.

1. Introduction

  • Accumulated adoption, network externalities, reputation, and learning by doing are among the mechanisms through which later activity can become more valuable.The introduction presents these as distinct settings sharing the feature that early activity contributes to later rewards.Source: §1 · pp. 1–2

1.1. Our Results and Technical Ideas

  • For homogeneous bonuses, a tight 1/2 competitive ratio follows from fixed-order policies that separate base and bonus rewards.Each policy maximizes its corresponding reward component for every arrival count; the better policy achieves the guarantee, and a two-product instance establishes tightness.Source: §1.1 · pp. 3–4
  • For arbitrary heterogeneous bonuses, the optimal worst-case competitive ratio is exactly 1/m, precluding a constant guarantee independent of the number of products.The matching upper bound extends the buildup conflict to m products with substantial bonuses at different assignment thresholds.Source: §1.1 · p. 4
  • A re-solving framework uses offline benchmarks to build feasible plans from the current allocation and orders assignments to preserve value if arrivals stop early.Backward-greedy ordering provides a quadratic prefix-value guarantee: the first h of k assignments earn at least h(h+1)/(k(k+1)) of incremental plan reward.Source: §1.1 · pp. 4–5
  • With discrete-concave bonuses, distribution-oblivious algorithms achieve competitive ratios of 0.2537 deterministically and 0.3864 randomized.The randomized method uses shorter epochs when accumulated reward can attain a benchmark early, and randomly shifts the geometric grid; both guarantees hold for every fixed arrival count.Source: §1.1 · pp. 4–5
  • For known IFR arrival distributions, a deterministic algorithm is 1/2-competitive by selecting planning horizons using the conditional arrival distribution.Its potential is half the expected residual offline reward; the IFR property ensures a plan whose expected reward covers the potential decrease.Source: §1.1 · pp. 5–6

1.2. Related Work

  • Increasing returns are underexplored relative to fixed or diminishing returns, and reward buildup creates a distinct challenge from compatibility constraints.The paper also distinguishes its uncertain-arrival setting from work on unknown rewards, nonstationary arrivals, and promotional allocation over a fixed horizon.Source: §1.2 · pp. 6–7
  • Existing incremental-maximization guarantees rely on accountability, which fails under increasing returns, while this paper uses arrival information to coordinate successive plans.The related objective seeks a single irrevocable sequence whose prefixes approximate offline optima at different cardinalities.Source: §1.2 · p. 7

2. Model and Benchmarks

The model allocates sequential arrivals among capacity-limited products under full compatibility, with assignments earning base rewards and nondecreasing product-specific bonuses. Policies are evaluated against an offline optimum that knows the realized arrival count.

2. Model and Benchmarks

  • Each arriving customer must be immediately and irrevocably assigned to a product with remaining capacity or rejected; every customer is compatible with every such product.The arrival count L follows a distribution supported on {0, 1, ..., Lmax}; the model studies arbitrary and IFR distributions.Source: §2 · p. 8
  • The IFR setting requires a nondecreasing discrete hazard rate, and includes binomial distributions and finite truncations of Poisson and geometric distributions.The paper focuses on full compatibility to isolate increasing returns and arrival uncertainty from compatibility constraints.Source: §2 · pp. 8–9
  • Assigning the next customer to product i earns base reward ri plus bonus fi(k+1), where k customers were previously assigned to i.The bonus function is nonnegative, nondecreasing, and satisfies fi(0)=0.Source: §2 · p. 8
  • The objective is expected total reward, compared with an offline optimum that knows the realized arrival count before selecting allocation counts.An online policy knows capacities, reward functions, and the arrival distribution, but not the realized count; distribution-oblivious policies do not use that distribution.Source: §2 · p. 8

3. Performance Limits under Increasing Returns

Greedy and natural LP-based rounding can fail arbitrarily badly under homogeneous bonuses. The section establishes tight competitive-ratio limits that depend on whether bonuses are homogeneous or heterogeneous.

3. Performance Limits under Increasing Returns

  • Homogeneous bonuses admit a tight 1/2 competitive ratio, while arbitrary heterogeneous bonuses have a tight 1/m ratio for m products.The 1/m bound rules out a constant guarantee independent of the number of products.Source: §3 · p. 9

3.1. Limitations of Greedy and Independent LP-Based Rounding

  • Greedy and natural LP-based rounding can perform arbitrarily poorly, even relative to the optimal online policy, under homogeneous bonuses.Greedy prioritizes immediate marginal rewards, while LP-based rounding uses ex-ante optimization to account for future rewards.Source: §3.1 · p. 9
  • For every ε > 0, some homogeneous-bonus instance makes greedy earn less than ε times the offline optimum.In the illustrated two-product instance, greedy earns 1 while assigning both customers to the second product yields expected reward pM.Source: §3.1 · p. 10

Appendix B.

The appendix examines LP-based allocation and contrasts guarantees under homogeneous and heterogeneous bonuses. Homogeneity supports a tight 1/2 guarantee, while arbitrary heterogeneity limits the tight ratio to 1/m.

Appendix B.

  • The mean-demand LP uses y_i,k for the relaxed probability that product i receives at least k assignments.Its arrival input is the expected number of arrivals, E[L].Source: Appendix B · p. 10
  • An arrival-aware, time-indexed LP with independent rounding can still perform arbitrarily poorly, even relative to the optimal online policy.Independent rounding may disperse assignments across products and prevent coordinated buildup.Source: Appendix B · p. 11

3.2. Homogeneous Bonuses: A Tight 1/2 Guarantee

  • The two fixed-order rules reflect competing priorities: base reward favors larger r_i, while bonus reward favors concentrating assignments on larger-capacity products.With a common nondecreasing bonus, filling in nonincreasing capacity order maximizes the bonus component for each arrival count.Source: §3.2 · p. 11
  • Under homogeneous bonuses, choosing the better of base-ordered and capacity-ordered fill achieves a tight 1/2-competitive ratio.For each realized arrival count, the two rules maximize the base-reward and bonus-reward components, respectively.Source: §3.2 · p. 12
  • The homogeneous 1/2 bound is tight: the optimal online-to-offline ratio in the construction is 1/(2−p), approaching 1/2.Arrival counts of one or two favor conflicting first assignments, and even the optimal online policy cannot avoid the loss.Source: §3.2 · p. 12

3.3. Heterogeneous Bonuses: A Tight 1/m Competitive Ratio

  • For arbitrary heterogeneous bonuses, a 1/m-competitive algorithm exists, and no online algorithm can guarantee a strictly greater ratio.The construction establishes tightness as the number of products grows.Source: §3.3 · p. 13
  • In the heterogeneous tightness construction, distinct reward thresholds create conflicting buildup targets, and the optimal worst-case ratio approaches 1/m.Each product offers a lump-sum reward at a different assignment level; the offline benchmark can choose a product after observing arrivals.Source: §3.3 · pp. 13–14

4. Algorithms under Increasing Discrete-Concave Bonuses

Under discrete-concave increasing bonuses, this section develops re-solving allocation algorithms for arbitrary arrival distributions and known IFR arrivals, using repeated planning and fractional allocation. It analyzes their competitive guarantees and remaining limits.

4. Algorithms under Increasing Discrete-Concave Bonuses

  • Discrete-concave bonuses are nondecreasing with nonincreasing successive increments, limiting reward backloading while retaining heterogeneous increasing returns and restoring constant competitive guarantees.The assumption applies to per-assignment bonuses, not cumulative rewards, so repeated assignments remain complementary.Source: §4 · pp. 14–15

4.1. The Re-solving Framework

  • The re-solving framework plans feasible assignments toward offline benchmarks in successive epochs, then orders them to protect rewards when arrivals stop early.It can exploit the arrival distribution when available, unlike incremental maximization, which targets uniform performance across stopping counts.Source: §4.1 · p. 16
  • Backward-greedy ordering guarantees that executing fraction h/ha of a plan retains at least its square of incremental reward, with a tight example for one product with f(k)=k and zero base reward.The bound holds for any feasible additional allocation from any current state, allowing repeated application as plans are re-solved.Source: §4.1 · p. 17
  • Discrete concavity also bounds the offline optimum’s growth by at most quadratically in the arrival count.This comparison helps evaluate benchmarks across planning horizons.Source: §4.1 · p. 17

4.2. Algorithms under General Arrivals

  • 0.3864 and 0.2537 are the competitive ratios of the randomized and deterministic distribution-oblivious algorithms, respectively, under general arrival distributions.The randomized approach uses fractional allocation planning, shorter re-solving epochs, a randomly shifted geometric grid, and joint rounding; the deterministic algorithm uses an integer geometric schedule.Source: §4.2 · p. 18, §4.2.1 · p. 20, §4.2.2 · p. 21

4.2.1. Allocation Planning and a Deterministic Algorithm.

  • The deterministic algorithm fills shortfalls relative to an offline optimal allocation and secures a 0.2537 competitive ratio using geometric benchmark levels and backward-greedy execution.With grid ratio γ=3, the guarantee holds at every fixed stopping count, and therefore for any arrival distribution.Source: §4.2.1 · pp. 18–20

4.2.2. A Randomized Algorithm.

  • The randomized algorithm shortens re-solving epochs and randomly shifts geometric benchmarks, then jointly rounds a fractional allocation path into feasible integral assignments.Its distribution-oblivious guarantee is 0.3864 under general arrivals.Source: §4.2 · p. 18, §4.2.2 · p. 21
  • 0.3864: The randomized algorithm is 0.3864-competitive for arbitrary arrival distributions, with its guarantee holding for every fixed stopping count in expectation over its internal randomization.The section also establishes an upper bound of 0.5703 on the competitive ratio under general arrivals.Source: §4.2.2 · pp. 24–25

4.3.1. Allocation Planning.

  • At each epoch, the allocation-planning rule evaluates candidate horizons using the conditional residual-arrival distribution and chooses a plan executed in backward-greedy order.Its score lower-bounds both the current epoch’s expected reward and the potential carried into a subsequent epoch; a residual-value lemma bounds the offline value preserved after completing a plan.Source: §4.3.1 · pp. 26–27

4.3.2. Performance Guarantee.

  • 1/2: Under IFR arrivals, Algorithm 3 with any ρ in (0, 1/2] is ρ-competitive, yielding a 1/2-competitive algorithm at ρ = 1/2.The key planning-score guarantee establishes that some horizon’s score is at least the current potential for ρ ≤ 1/2.Source: §4.3.2 · pp. 27–28
  • 1/2-competitive performance is guaranteed by Algorithm 3 for known IFR arrivals.The proof establishes the guarantee by setting ρ = 1/2; IFR information lets plans account for the likelihood of future buildup opportunities.Source: §4.3.2 · p. 29
  • 0.6608 is an upper bound on the best IFR competitive ratio, compared with 0.5703 for general arrivals.The IFR construction combines geometric arrivals, products with varying capacities, and linear bonuses; the gap between upper and lower bounds remains open.Source: §4.3.2 · p. 29
  • 1/4 is Algorithm 3’s deterministic guarantee for any known arrival distribution, weaker than the distribution-oblivious guarantees of 0.2537 and 0.3864.The planning-score guarantee holds for general distributions when ρ ≤ 1/4; the 1/2 guarantee relies on an IFR moment inequality.Source: §4.3.2 · p. 29

5. Conclusion

  • Discrete concavity restores constant guarantees for heterogeneous bonuses by limiting reward backloading, and the re-solving framework combines allocation planning with assignment ordering.The framework achieves distribution-oblivious guarantees for general arrivals and stronger performance under IFR arrivals.Source: §5 · p. 30
  • Open questions include optimal competitive ratios under discrete concavity, whether broader reward structures permit constant guarantees, and how compatibility constraints interact with increasing returns.The conclusion notes that current upper bounds do not match the algorithmic guarantees and that full compatibility isolates the buildup trade-off from compatibility trade-offs.Source: §5 · p. 30

A.1. Dynamic Programming for the Offline Benchmark

The offline benchmark is computed exactly by dynamic programming over products and assignment counts, with maximizing choices enabling recovery of an optimal allocation.

A.1. Dynamic Programming for the Offline Benchmark

  • The recurrence in Proposition 3 computes the exact offline optimum for each feasible assignment count.The value for an arrival count ℓ is U(ℓ) = F_m(min{ℓ,B}); storing maximizing choices recovers an optimal allocation.Source: §A.1 · p. 34
  • The recursion considers assigning s customers to the current product and combines that reward with the best value for the remaining products.An optimal allocation is recovered by tracing the maximizing choices backward through the products.Source: §A.1 · p. 34
  • The dynamic program has O(m(B + 1)) states and runs in O(m(B + 1)^2) time with O(m(B + 1)) space.Recovering an allocation for a given arrival count takes O(m) time.Source: §A.1 · p. 34

B.1. Supporting Material for Section 3.1

The counterexamples show that greedy and independent LP rounding can perform arbitrarily poorly, even when products share a common bonus function.

B.1. Supporting Material for Section 3.1

  • As M grows, greedy’s reward of 1 is at most 2/M of the feasible online policy’s expected reward M/2.The instance has two products, a first customer arriving for sure, and a second arriving with probability 1/2.Source: §B.1 · pp. 34–35
  • For the LP-rounding example, the mean-demand LP has a uniquely optimal solution with equal assignments to product 2 and none to product 1.The instance uses a common bonus with f(1) = 0 and f(2) = 3.Source: §B.1 · p. 35
  • Independent rounding assigns every arriving customer to product 2 and earns expected reward 3p, while assigning the first customer to product 1 earns 1 for sure.The supplied comparison identifies the latter as a feasible online policy.Source: §B.1 · p. 35

B.2. Supporting Material for Section 3.2

Fixed-order fill policies separate base rewards from bonuses, yielding a 1/2 guarantee under homogeneous bonuses; a constructed family shows that this ratio is tight.

B.2. Supporting Material for Section 3.2

  • A fixed-order fill algorithm’s expected reward can be computed in O(B + Lmax) time.The calculation uses arrival-count tail probabilities, which can be obtained by a backward cumulative sum.Source: §B.2 · p. 35
  • Base-ordered fill maximizes base rewards, while capacity-ordered fill majorizes feasible allocations and maximizes the common cumulative bonus.The two componentwise bounds yield a realization-wise guarantee before taking expectations.Source: §B.2 · pp. 36–37
  • A 1/2 competitive ratio is achievable and tight under homogeneous bonuses.The proof combines componentwise bounds for each realized arrival count; a family of instances makes the online-to-offline ratio approach 1/2.Source: §B.2 · pp. 36–38
  • In the tightness construction, the online optimum is 1, whereas the offline benchmark can choose different products for one versus two arrivals.As the probability of a second arrival tends to zero, the online-to-offline ratio approaches 1/2.Source: §B.2 · pp. 37–38

B.3. Supporting Material for Section 3.3

With arbitrary heterogeneous bonuses, the optimal competitive ratio is exactly 1/m: committing to one product guarantees 1/m, and a matching family rules out a larger universal guarantee.

B.3. Supporting Material for Section 3.3

  • Committing all arrivals to the product with the largest standalone expected reward achieves a 1/m competitive ratio.The guarantee follows by comparing each product’s reward under the realized arrival count with the offline optimum.Source: §B.3 · p. 38
  • The upper bound compares an online algorithm’s first-product choice with an offline allocation that assigns all i arrivals to product i.The resulting construction rules out any universal competitive ratio strictly greater than 1/m.Source: §B.3 · p. 39
  • A truncated geometric arrival-count family with m products makes every online algorithm’s ratio approach 1/m.For this family, product i pays only upon its i-th assignment, and committing to any single product yields expected reward 1.Source: §B.3 · pp. 38–39
  • For m products with arbitrary heterogeneous bonuses, the optimal competitive ratio is exactly 1/m.A universal 1/m guarantee and a matching family of instances establish the two sides of the result.Source: §B.3 · pp. 38–39

C.1.1. Limitations of Greedy and LP-Based Rounding Algorithms.

The section constructs homogeneous-bonus instances showing that greedy and natural LP-based rounding can have arbitrarily small reward relative to the offline optimum.

C.1.1. Limitations of Greedy and LP-Based Rounding Algorithms.

  • For every ε > 0, greedy’s competitive ratio can be below ε on an instance with homogeneous linear bonuses satisfying Assumption 1.The construction makes greedy choose among products with higher immediate reward rather than build up the product that benefits from repeated assignments.Source: §C.1.1 · pp. 39–40
  • The LP-based policy’s poor guarantee persists even though the proposed solution is feasible and uniquely optimal for the LP.The proof establishes the solution’s feasibility and optimality before showing that its independent rounding performs poorly.Source: §C.1.1 · pp. 40–41
  • For every ε > 0, mean-demand LP independent rounding can have reward below ε times the offline optimum under homogeneous linear bonuses.The construction uses an arrival count that is one with certainty and reaches N with probability 1/N^2.Source: §C.1.1 · pp. 40–41

C.1.2. Limitation of Time-Indexed LP and Independent Rounding.

The time-indexed LP tracks assignment levels by arrival position, but independent rounding can still perform arbitrarily poorly. Supporting arguments bound the value of backward-greedy prefixes and use those bounds to compare a current allocation with offline benchmarks.

C.1.2. Limitation of Time-Indexed LP and Independent Rounding.

  • The time-indexed LP tracks the probability that an arrival position contains a particular product-level assignment and imposes within-product precedence.Independent rounding selects products separately across positions, rejects assignments to full products, and rejects arrivals after the sequence length B.Source: §C.1.2 · p. 42
  • Independent rounding of an optimal time-indexed LP solution can earn less than ε times the offline optimum for every ε > 0, even with homogeneous linear bonuses.The LP’s optimal value equals the offline optimum in the construction, so the failure is in rounding rather than the relaxation’s objective value.Source: §C.1.2 · p. 42

C.2. Supporting Material for Section 4.1

  • Under discrete concavity, backward greedy bounds an endpoint marginal by 2/(ai + 1) times the planned assignments’ incremental reward.The proof also establishes that every prefix is feasible from the current allocation.Source: §C.2 · pp. 43–44

C.3.1. Supporting Material for Section 4.2.1.

  • The benchmark-progress argument uses the overlap between the current allocation and the offline optimizer, then applies the prefix-value guarantee to missing assignments.It treats separately whether the overlap size is at most or greater than the preceding benchmark level, and also covers prospective arrival counts above capacity.Source: §C.3.1 · pp. 44–45

C.3.2. Supporting Material for Section 4.2.1.

The proof establishes a pointwise guarantee across stopping counts by tracking progress within geometrically spaced epochs. Evaluating the deterministic certificate at γ = 3 yields a competitive ratio above 0.2537.

C.3.2. Supporting Material for Section 4.2.1.

  • Each epoch’s plan reaches its target benchmark by the checkpoint, while partial execution is bounded using the prefix-value guarantee.The pointwise comparison combines the value secured before the epoch with progress during it.Source: §C.3.2 · p. 45
  • The proof covers initialization and boundary stopping counts, including zero arrivals and counts beyond total capacity.For counts above capacity, the policy attains U(B) = U(ℓ).Source: §C.3.2 · pp. 45–46
  • 0.2537847484... > 0.2537, yielding the deterministic algorithm’s 0.2537-competitive guarantee at γ = 3.The minimum defining the certificate is attained at t* ≈ 1.5177774358.Source: §C.3.2 · p. 46

C.3.3. Supporting Material for Section 4.2.2.

The randomized construction uses a shifted geometric schedule with fractional plans and backward-greedy ordering, then rounds the path to a feasible integral allocation. Averaging its guarantee gives a 0.3864-competitive algorithm.

C.3.3. Supporting Material for Section 4.2.2.

  • A randomly shifted geometric schedule builds fractional plans, and backward greedy orders their assignments to preserve value under partial execution.The fractional benchmark agrees with the original offline benchmark at integer arrival counts.Source: §C.3.3 · pp. 46–47
  • Bipartite dependent rounding preserves each fractional assignment’s conditional expectation while producing an integral path that respects capacities.Cycle updates preserve row and column sums, and the procedure terminates after at most Bm updates.Source: §C.3.3 · p. 48
  • The resulting algorithm runs in polynomial time under the explicit-capacity representation and ideal real arithmetic.The analysis accounts for offline optimizations, backward-greedy ordering, and joint rounding.Source: §C.3.3 · p. 49
  • The passage reports that 0.3864058297... > 0.3864 and concludes that πR(22/5) is 0.3864-competitive, then states that the proof is complete.Source: §C.3.3 · p. 50

C.3.4. An Upper Bound under General Arrivals.

Under Assumption 1, this section proves that no online algorithm can exceed a competitive ratio of 0.5703 for general arrival distributions, even with randomization and distributional knowledge. The proof uses a Riemann-sum limit and combines estimates (34) and (35).

C.3.4. An Upper Bound under General Arrivals.

  • 0.5703 is an upper bound on the competitive ratio under general arrivals, even for randomized algorithms that know the arrival distribution.The bound follows by choosing α = 25/16, which gives 2Λ_α/α ≈ 0.5702595242 and finite instances with offline-to-online ratio below 0.57026 + ε.Source: §C.3.4 · pp. 50–51

C.4.1. Supporting Material for Section 4.3.1.

  • For horizons k and h, the residual-value comparison uses assignments unique to the longer optimal plan as a feasible continuation after completing the shorter plan.The unique assignments earn the same incremental rewards from either starting allocation, and backward-greedy ordering gives prefixes a controlled fraction of their total incremental reward.Source: §C.4.1 · p. 53

C.4.2. Supporting Material for Section 4.3.2.

  • For IFR arrivals, the planning-score guarantee reduces residual offline values to quadratic cutoff sequences whose paired-horizon comparisons are nonnegative when ρ ≤ 1/2.The proof decomposes the residual values into a nonnegative linear combination of cutoff sequences and shows the opposite-side cutoff terms offset in expectation.Source: §C.4.2 · p. 54

C.4.3. An Upper Bound under IFR Arrivals.

  • 0.6608 is an upper bound on the competitive ratio under IFR arrivals.The construction uses truncated geometric arrival counts; its proof bounds online reward by expected arrivals and lower-bounds the offline value.Source: §C.4.3 · pp. 56–57

C.3.4. An Upper Bound under General Arrivals.

  • Uniform convergence on δ ≤ ℓ/√m ≤ M makes the restricted sum a Riemann sum, and the limiting integral is finite by the endpoint behavior of g(x).The passage states g(x) ∼ x as x ↓ 0 and g(x) ∼ x²/2 as x → ∞.Source: §C.4.3 · p. 57
  • Using (1 − q)√m = 1 and qB → 0, the proof combines (34) and (35) to complete the argument.The supplied passage does not state the resulting bound.Source: §C.4.3 · p. 57

C.4.4. Extension to General Arrivals.

For general arrival distributions, the section replaces the IFR-specific moment comparison with a weighted analysis across candidate horizons. Under Assumption 1, Algorithm 3 is deterministic and 1/4-competitive when the arrival distribution is known.

C.4.4. Extension to General Arrivals.

  • Without IFR, the analysis weights candidate horizons by arrival probabilities and residual offline values, then uses a cross-horizon inequality and telescoping argument.This yields a 1/4-competitive ratio through the same planning rule.Source: §C.4.4 · p. 57
  • 1/4: Algorithm 3 is deterministic and 1/4-competitive under any arrival distribution when that distribution is known.The planning-score guarantee holds under Assumption 1.Source: §C.4.4 · p. 57
  • The weighted bound across horizons applies to every probability distribution, and its proof represents the cross-horizon sum as an integral before applying Cauchy–Schwarz.The proof uses a Green’s-function representation.Source: §C.4.4 · p. 58
  • The score certificate relies on Assumption 1 rather than IFR, and summing potential inequalities across active epochs yields the competitive guarantee.Each active epoch assigns at least one customer.Source: §C.4.4 · p. 59
Loading 2609.34121v2…