PaperlayerView exact revision on arXiv

Source-linked AI summary

Single-Sample Prophet Inequalities: A Combinatorial to Single-Item Reduction

Shuchi Chawla, Trung Dang

arXiv:2610.03660v1cs.GTcs.DS

TL;DR

Single-sample prophet inequalities ask whether an online algorithm can make irrevocable allocation decisions using only one sample from an unknown distribution. This paper reduces combinatorial allocation to single-item prophet inequalities using supporting prices and free disposal, obtaining improved XOS guarantees and extensions to divisible capped-XOS valuations.

  • Problem

    For multidimensional online allocation with unknown distributions, it remains open whether one sample can support guarantees through a common principle rather than valuation-specific constructions.

    Source: §1 · p. 3

  • Method

    The paper uses supporting prices and a free-disposal value to separate buyer-side combinatorial constraints from item-side supply constraints.

    Source: §1 · p. 3

  • Results

    Approximately 1/10.4 is the single-sample guarantee for XOS valuations, improving on the prior factor of 576; the framework also extends to divisible capped-XOS valuations.

    Source: §1 · p. 4, §7 · p. 35

  • Takeaways & Limitations

    The reduction provides a modular framework for combinatorial prophet inequalities in the stronger Game of Googol model, with divisible capped-XOS extensions.

    Source: §7 · p. 35

    For a single divisible item with monotone concave valuations, the described approach is insufficient to obtain a competitive ratio of 1/2.

    Source: §5.3 · p. 33

Abstract

from arXiv · show

We study single-sample prophet inequalities for online combinatorial allocation. Our main contribution is a general reduction from combinatorial to single-item prophet inequalities for valuation classes admitting suitable supporting prices. The reduction uses a free-disposal value to separate buyer-side combinatorial constraints from item-side supply constraints, yielding a modular framework that applies in the stronger Game of Googol model. This framework yields a $\frac{1}{6\sqrt{3}}\approx\frac{1}{10.4}$-competitive single-sample prophet inequality and a $(\beta_{k-1}/4)$-competitive $k$-sample prophet inequality for XOS valuations, where $\beta_k$ is the competitive ratio of a $k$-sample single-item prophet inequality, improving upon the work of [DKL+24]. Both results extend directly to divisible resources with capped-XOS valuations. Along the way, we obtain new results for online free disposal and an optimal single-sample prophet inequality for fractional knapsack in the Game of Googol model.

1 Introduction

The introduction asks whether one sample can support strong guarantees for multidimensional online allocation, where prior methods were tailored to particular valuation classes. It presents a supporting-price reduction that separates buyer-side allocation from item-side competition and yields improved guarantees.

1.2 Related Work

  • Prior multidimensional single-sample results used valuation-specific constructions, while this work seeks a common principle for such settings.Earlier work had established a constant-factor guarantee for general XOS valuations, with ratio 1/576 in the Game of Googol model.Source: §1 · p. 3, §1.2 · p. 7

1 Introduction

  • A general reduction for valuations with suitable supporting prices represents multidimensional allocations through per-item contributions, lifting single-item guarantees to combinatorial allocation.The reduction separates buyer-side constraints from item-side supply constraints using free disposal.Source: §1 · pp. 3–4

1.1 Technical Overview and Results

  • The framework gives XOS valuations a single-sample guarantee of approximately 1/10.4, improving on the prior factor of 576, and its guarantees hold in the Game of Googol model.The framework also yields guarantees for divisible capped-XOS valuations; the divisible free-disposal optimization has an efficient implementation under additional concavity and oracle assumptions.Source: §1 · p. 4, §1.1 · p. 6
  • Supporting prices anchor each buyer’s provisional allocation, while the free-disposal value measures the supporting-price value retained after item-side conflicts are resolved.Provisional allocations enforce buyer-side constraints; excess item claims can be discarded to restore supply feasibility.Source: §1.1 · p. 4
  • For XOS valuations, free-disposal value is represented as monotone submodular maximization under a partition matroid, making buyer-wise greedy the corresponding greedy algorithm.The free-disposal analysis uses random-order arrivals, while the actual buyers in the prophet-inequality instance may arrive adversarially.Source: §1.1 · p. 5, §1.2 · p. 8
  • A coordination sample records the free-disposal algorithm’s state before each buyer, enabling buyer-local outputs that preserve independence across buyers.A separate sample supplies the item-wise prophet inequalities; the paper also optimizes the split probability when deriving a single-sample guarantee.Source: §1.1 · p. 5
  • For divisible resources, capped-XOS valuations admit a continuous free-disposal algorithm, and resolving each item’s supply competition becomes fractional knapsack.The paper establishes an optimal 1/2 single-sample guarantee for fractional knapsack in the Game of Googol model.Source: §1.1 · p. 6, §1.2 · p. 8

Organization of the paper

  • The paper proceeds from the model and free-disposal value to the reduction, free-disposal algorithms, single-item inequalities, and combined guarantees.Additional proofs and extensions appear in the appendices.Source: Organization of the paper · p. 8

2 Preliminaries

The preliminaries define online allocation and the Game of Googol model, then state the supporting-price assumptions and free-disposal objective used in the reduction. They also describe the single-item limited-demand setting.

2.1 Online Combinatorial Allocation, Prophet Inequalities, and the Game of Googol

  • Buyers arrive sequentially and receive irrevocable, supply-feasible allocations; in GoG, an adversary supplies k+1 instances randomly assigned as samples and real input, and GoG guarantees imply sample-based guarantees.The k=1 case is called a single-sample combinatorial prophet inequality.Source: §2.1 · pp. 9–10

2.2 Assumptions on Valuation Functions

  • The framework assumes normalized, monotone valuations with supporting prices; this condition is equivalent to XOS for indivisible items and capped-XOS for divisible items.For divisible items, the capped-XOS equivalence is stated for normalized, monotone valuations.Source: §2.2 · pp. 10–11

2.3 Free-Disposal Value

  • Free-disposal value measures the supporting-price value retained by trimming supply-infeasible provisional allocations, whose objective is compared with the hindsight optimum.Provisional allocations satisfy buyer constraints but may conflict on supply.Source: §2.3 · p. 12
  • Free-disposal value decomposes into per-item hindsight optima, corresponding to fractional knapsack for divisible items, and also has a per-item layer-cake representation.Source: §2.3 · p. 12

2.4 Single-Item Prophet Inequality

  • The single-item section studies uniform-reward limited-demand buyers; its indivisible case is classical prophet selection, while fractional knapsack has a known tight 1/2 guarantee.The buyer's pair consists of a unit reward and demand.Source: §2.4 · p. 13

3 A General Reduction from Combinatorial to Single-Item PI

This section develops a modular reduction from combinatorial to single-item prophet inequalities, separating buyer-side feasibility from item supply through free-disposal allocation and supporting prices. Its one-sample construction combines free disposal with a single-item Game of Googol algorithm, with guarantees based on the component algorithms and polynomial running time when they run in polynomial time.

3 A General Reduction from Combinatorial to Single-Item PI

  • The reduction uses buyer-feasible provisional allocations and supporting prices, then resolves item conflicts with single-item prophet inequalities to obtain an ex-post feasible allocation.The free-disposal value bridges the stages by measuring supporting-price value retained after item conflicts; buyer-local provisional decisions, conditional on a shared sample, preserve independence across buyers.Source: §3 · pp. 13–14
  • An α-competitive random-order free-disposal algorithm and a β_k-competitive k-sample single-item algorithm yield an (αβ_k/2)-competitive (k + 1)-SCombPI.This is Theorem 3.1’s guarantee in the Game of Googol setting.Source: §3 · p. 14

3.1 Reducing (k + 1)-SCombPI to k-SPI

  • With k + 1 samples, one coordination sample drives provisional allocations and the other k samples feed per-item k-SPI instances, yielding an αβ-competitive reduction when PAlloc is α-competitive.The coordination sample is also used to transform each of the k samples into provisional allocations; the algorithm’s output is feasible.Source: §3.1 · pp. 14, 16

3.2 Constructing a Competitive Buyer-Local Provisional-Allocation Algorithm

  • The buyer-local PAlloc construction replaces each buyer’s sample valuation with its real valuation in a coupled FDAlg execution, inheriting half of FDAlg’s random-order guarantee.The executions share internal randomness and may use a random internal order independently of real buyer arrivals; thus an α-competitive FDAlg gives an α/2-competitive buyer-local PAlloc.Source: §3.2 · pp. 16, 18

3.3 From Two Samples to One Sample

  • For the single-sample case, the framework reduces the prior factor-3 loss from to a loss of 2 or less by assigning buyers coordinating or competition roles.The construction assumes a smooth competitive ratio for the free-disposal algorithm, depending on the fraction of buyers zeroed out.Source: §3.3 · p. 18
  • For every q in [0, 1], the expected free-disposal value of replayed allocations is at least (1−q) times that of the full-sample allocations.At q = 1/2, this recovers the half-value real-versus-sample replay comparison; the real side consists of competing buyers and the sample side of coordinating buyers.Source: §3.3 · p. 19
  • With q = 1/2, Algorithm 3 is (αβ/4)-competitive when FDAlg is α-competitive and SSPI is β-competitive.More generally, Theorem 3.6 gives a guarantee using q that maximizes (1−q)Γ(q), where Γ is FDAlg’s smooth competitive ratio and β is SSPI’s competitive ratio.Source: §3.3 · pp. 19–20

3.4 Computational Considerations

  • Given oracle access to FDAlg, k-SPI, and SSPI, Algorithms 1–3 run in polynomial time if those component algorithms can be implemented efficiently.This yields efficient (k + 1)-sample and single-sample combinatorial prophet inequality algorithms under that condition.Source: §3.4 · p. 20

4 Random-Order Free-Disposal Algorithms

This section develops free-disposal algorithms for XOS valuations that exploit random buyer order, and gives divisible-item guarantees under stronger valuation assumptions, including an adversarial-order guarantee. It also establishes a (1 − 1/e)-competitive free-disposal algorithm through primal-dual progress, dual feasibility, and the existence of a fixed point that makes the algorithm well-defined.

4.1 Indivisible-Item Free-Disposal Algorithm

  • For random-order XOS buyers, Algorithm 4 is 0.5096-competitive; under adversarial order, no efficient algorithm exceeds 1/2 unless NP = RP.Algorithm 4 is also Γ-smooth-competitive for Γ(q) = q - q^2/2 and runs in polynomial time with polynomially many demand and supporting-price queries.Source: §4.1 · pp. 20–21

4.2 Divisible-Item Free-Disposal Algorithms

  • For divisible items, capped-XOS buyers get 0.5096-competitive and Γ-smooth guarantees in random order; DR-submodular concave buyers get (1 - 1/e) ≈ 0.6321 competitiveness under adversarial order.For capped-XOS valuations, polynomial-time implementation with polynomially many supporting-price queries is guaranteed when valuations are also concave.Source: §4.2 · p. 23

4.2.1 A Continuous Extension of Buyer-Wise Greedy

  • The continuous buyer-wise greedy algorithm reduces to finite submodular maximization by encoding its possible outputs and the hindsight optimum as configurations.There are at most n! + 1 possible choices per buyer; when valuations are concave, the greedy choice can be found in polynomial time to arbitrary additive accuracy.Source: §4.2.1 · pp. 24, 26

4.2.2 A (1 −1/e)-Competitive Algorithm

  • Algorithm 6 uses an online primal-dual analysis that establishes approximate reverse weak duality at each iteration and dual feasibility at termination.The algorithm’s stated guarantee is (1 - 1/e) ≈ 0.6321 under adversarial buyer arrivals for DR-submodular and concave valuations.Source: §4.2 · p. 23, §4.2.2 · pp. 26–27
  • At every iteration, the primal increment is at least γ times the dual increment.This approximate reverse weak-duality guarantee supports the algorithm’s competitive analysis.Source: §4.2.2 · p. 27
  • At termination, β_i + ⟨x, α(n)⟩ ≥ v_i(x) for every x ∈ [0, 1]^m and buyer i.This establishes dual feasibility for all buyers and feasible x.Source: §4.2.2 · p. 28
  • For every valid pre-update state, a fixed point satisfying Condition 1 exists, making the algorithm well-defined.The proof applies Kakutani’s fixed-point theorem, using DR-submodularity for continuity and concavity of the valuations.Source: §4.2.2 · pp. 28–29
  • The algorithm is (1 − 1/e)-competitive, as Theorem 4.7 follows from Lemmas 4.10–4.12.The subsection title identifies the competitive ratio; the proof of Theorem 4.7 follows directly from those three lemmas.Source: §4.2.2 · pp. 27–29

5 Single-Sample Single-Item Prophet Inequalities

This section establishes optimal single-sample guarantees for indivisible items and fractional knapsack, then extends the approach to general concave divisible items. The concave-item guarantee approaches 1−1/e over 2 as the discretization grows.

5.2 Single-Sample Prophet Inequality for Fractional Knapsack

  • The section treats fractional knapsack as the divisible-item case, where each buyer is represented by an item with a density and a weight.The algorithm samples a density threshold from the sample’s optimal fractional knapsack and accepts feasible fractions; the proof compares the algorithm’s density-above-threshold allocation with the prophet’s.Source: §5.2 · pp. 29–30

5.1 Single-Sample Prophet Inequality for an Indivisible Item

  • The indivisible-item and fractional-knapsack cases each admit a polynomial-time 1/2-competitive single-sample algorithm, and 1/2 is optimal in both cases.The fractional-knapsack result is proved in the Game of Googol setting; the earlier result cited for that setting does not apply there.Source: §5.1 · p. 29, §5.2 · p. 30

5.3 Single-Sample Prophet Inequality for a Concave Divisible Item

  • A natural threshold-based generalization of the fractional-knapsack algorithm achieves at most 7/16 = 0.4375 for concave divisible items, below 1/2.This motivates a different algorithm for the concave case.Source: §5.3 · p. 33
  • Theorem 5.8 states that, for the concave divisible-item case, as M →∞, Algorithm 9’s competitive ratio approaches (1−1/e)/2, approximately 0.3161.Source: §5.3 · p. 34

6 Applications

The applications instantiate the reduction with random-order free-disposal algorithms and single-item prophet inequalities. They yield approximately 1/10.40-competitive guarantees for indivisible XOS and divisible capped-XOS settings.

6 Applications

  • Approximately 1/10.40-competitive guarantees are obtained for both indivisible items under XOS valuations and divisible items under capped-XOS valuations.For the divisible setting, polynomial-time implementation is stated when the valuation functions are concave; the indivisible algorithm is polynomial time.Source: §6 · p. 35

7 Conclusion

The conclusion presents a modular reduction built from a random-order online free-disposal algorithm and a single-sample prophet inequality for one resource. It reports improved guarantees for indivisible XOS and new guarantees for divisible capped-XOS valuations in the Game of Googol model.

7 Conclusion

  • The reduction separates provisional allocation under buyer-side constraints from resolving competition for each resource, yielding improved indivisible-XOS and new divisible capped-XOS guarantees in the Game of Googol model.Its two ingredients are a random-order online free-disposal algorithm and a single-sample prophet inequality for one resource.Source: §7 · p. 35
  • The framework may apply to settings such as k-selection when suitable free-disposal and single-sample single-item algorithms are available.The paper cites single-sample k-selection algorithms for i.i.d. sample and real values as one such example.Source: §7 · p. 35

A Extension to Subadditive Valuations

The appendix extends single-sample guarantees from XOS to subadditive buyers by replacing each valuation with an XOS approximation. The resulting guarantee loses a factor of H_m.

A Extension to Subadditive Valuations

  • Subadditive valuations may lack the exact supporting prices required by the reduction, so the proof replaces them with XOS approximations.The approximation is supplied by a classical result for normalized, monotone subadditive valuations.Source: A Extension to Subadditive Valuations · p. 36
  • An α-competitive single-sample inequality for XOS buyers yields an α/H_m = Ω(α/log m)-competitive inequality for subadditive buyers over m items.The approximation applies to normalized, monotone subadditive valuations.Source: A Extension to Subadditive Valuations · p. 36
  • The algorithm runs the XOS prophet inequality on transformed sample and real valuations, whose allocated-bundle values do not exceed the original valuations.Feasibility is preserved because the allocation is exactly the one chosen by the XOS algorithm.Source: A Extension to Subadditive Valuations · p. 36

B Deferred Proofs from Section 2

The deferred proof establishes the connection between one-sided supporting prices and capped-XOS valuations. Supporting prices yield capped-additive clauses representing the valuation, and capped-XOS clauses provide supporting prices.

B Deferred Proofs from Section 2

  • A valuation with a supporting-price map is capped-XOS: the proof constructs capped-additive clauses whose maximum equals the valuation.The clause indexed by x attains v(x), while the supporting-price property and monotonicity bound the other clauses.Source: B Deferred Proofs from Section 2 · p. 37
  • The two constructions establish the equivalence between capped-XOS valuations and valuations admitting the relevant supporting prices.The forward direction uses supporting-price inequalities and monotonicity; the reverse direction constructs prices from a maximizing capped-additive clause.Source: B Deferred Proofs from Section 2 · p. 37
  • For a capped-XOS valuation, a clause attaining v(x) supplies a supporting-price vector at x.The proof uses the clause’s capped-additive coefficients and the non-increasing ratio min{t, c_i}/t.Source: B Deferred Proofs from Section 2 · p. 37

C Deferred Proofs from Section 3

These deferred proofs justify how sample roles and free-disposal guarantees combine with item-wise prophet inequalities. Random-order free disposal also yields a bound that depends on the sample-role split.

C Deferred Proofs from Section 3

  • The k-sample guarantee applies itemwise because each buyer’s sample and real valuation form a random permutation, which induces a random permutation of the corresponding price-allocation pairs.The local property of PAlloc preserves this permutation when producing the pairs used by the item-wise inequalities.Source: C Deferred Proofs from Section 3 · p. 37
  • The item-wise k-sample guarantee bounds the free-disposal value, and supporting prices relate that value to the algorithm’s expected reward.The proof then takes expectation over the coordination sample and uses the free-disposal algorithm’s α-competitiveness.Source: C Deferred Proofs from Section 3 · p. 38
  • For the random-order free-disposal analysis, E[FD(x1, . . . , xn)] ≥ (1 − q)E[FD(z1, . . . , zn)].The proof obtains this inequality by summing expected marginal-increment comparisons over buyers and telescoping.Source: C Deferred Proofs from Section 3 · p. 39

D Deferred Proofs from Section 4

The deferred proofs analyze random-order greedy under independent retention and establish hardness for online free-disposal allocation through a reduction from online submodular welfare maximization. The hardness follows from the coverage-valuation bound.

D Deferred Proofs from Section 4

  • Lemma D.1 studies greedy on independently retained parts processed in uniformly random order, compared with an optimum for the original instance.The proof realizes this process by assigning each part an independent uniform arrival time.Source: D Deferred Proofs from Section 4 · p. 39
  • Unless NP = RP, no polynomial-time algorithm, even randomized against an oblivious adversary, is (1/2 + ϵ)-competitive for online welfare maximization with coverage valuations.The hardness holds for every constant ϵ > 0.Source: D Deferred Proofs from Section 4 · p. 40
  • A polynomial-time reduction transfers this hardness to online free-disposal allocation by mapping feasible allocations in both directions while preserving hindsight optima.An efficient (1/2 + ϵ)-competitive algorithm for free disposal would imply one for online submodular welfare maximization.Source: D Deferred Proofs from Section 4 · p. 41

E Deferred Proofs from Section 5

The deferred proofs bound the natural single-sample generalization by 7/16 on a constructed instance and establish a rounding comparison between the unrestricted and M-marginal optima.

E Deferred Proofs from Section 5

  • The construction compares the algorithm’s expected reward over fair-coin orientations with the prophet’s two largest real marginals.The sample optimum consists of the two largest sampled marginals, and the threshold is each of those values with probability 1/2.Source: E Deferred Proofs from Section 5 · p. 42
  • 7/16: the natural generalization in the single-sample setting has competitive ratio at most 7/16 on the constructed instance.The proof takes a fixed ϵ in (0, 1/8) and lets M grow, with the ratio converging to 7/16.Source: E Deferred Proofs from Section 5 · pp. 42–43
  • Rounding up the coordinates of an optimal allocation yields OptM ≥ M/(M + n) · Opt.The proof bounds the number of marginal gains by M + n, then takes the largest M gains.Source: E Deferred Proofs from Section 5 · p. 43
Loading 2610.03660v1…