PaperlayerView exact revision on arXiv

Source-linked AI summary

Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs

Paul Dütting, Michal Feldman, Thomas Kesselheim, Brendan Lucier

arXiv:1612.03161v2cs.GTcs.DS

TL;DR

The paper addresses stochastic allocation problems where values and demands are uncertain, and develops a general price-based framework for prophet inequalities and posted-price mechanisms. It unifies prior results and yields improved guarantees, including an O(d) approximation for combinatorial auctions and a (4k −2+ ǫ)-approximate mechanism for MPH-k valuations.

  • Problem

    Online allocation must maximize welfare when agents’ values, demands, and preferred bundles are private and drawn from distributions.

  • Method

    The framework derives sufficient conditions for prices in full-information instances and extends their approximation guarantees to stochastic settings through balanced prices and price-based algorithms.

  • Results

    The framework unifies existing prophet-inequality results and gives new guarantees, including an O(d) approximation for combinatorial auctions and a (4k −2+ ǫ)-approximate static posted-price mechanism for MPH-k valuations.

  • Takeaways & Limitations

    The framework provides a common route for constructing posted-price mechanisms across combinatorial allocation settings and connects prophet inequalities with mechanism smoothness.

  • Takeaways & Limitations

    Open questions include gaps between known upper and lower approximation bounds and unresolved separations between prophet inequalities and posted-price implementations.

Abstract

from arXiv · show

We present a general framework for stochastic online maximization problems with combinatorial feasibility constraints. The framework establishes prophet inequalities by constructing price-based online approximation algorithms, a natural extension of threshold algorithms for settings beyond binary selection. Our analysis takes the form of an extension theorem: we derive sufficient conditions on prices when all weights are known in advance, then prove that the resulting approximation guarantees extend directly to stochastic settings. Our framework unifies and simplifies much of the existing literature on prophet inequalities and posted price mechanisms, and is used to derive new and improved results for combinatorial markets (with and without complements), multi-dimensional matroids, and sparse packing problems. Finally, we highlight a surprising connection between the smoothness framework for bounding the price of anarchy of mechanisms and our framework, and show that many smooth mechanisms can be recast as posted price mechanisms with comparable performance guarantees.

1 Introduction

The paper develops a general price-based framework that transfers full-information balanced-price guarantees to stochastic online allocation, unifying prior prophet-inequality results and yielding new approximations.

  • 1 Introduction: The framework asks whether complex sequential allocations can be approximated by posted prices when agents have private, distributed preferences.The motivating concert problem includes multi-seat demands, heterogeneous values, and heterogeneous seat preferences.
  • 1.2 A Framework for Prophet Inequalities: Balanced prices for full-information instances directly imply price-based prophet inequalities for stochastic settings with only distributional knowledge.The construction posts appropriately scaled expected full-information prices.
  • 4 New and Improved Prophet Inequalities: For bundle-size d combinatorial auctions, polynomial-time approximation improves from O(d^2) to O(d) by applying the theorem to a fractional relaxation.The direct greedy-based approach gives O(d^2), while the fractional-relaxation approach achieves O(d).
  • 1.2 A Framework for Prophet Inequalities: The framework unifies existing proofs and supports composition: XOS auctions obtain a 2-approximation from single-item prices, while subadditive valuations obtain O(log m).The XOS result follows from (1,1)-balanced prices and the composition theorem.
  • 4 New and Improved Prophet Inequalities: Theorem 1.1 gives a (4k −2+ ǫ)-approximate static posted-price mechanism for MPH-k combinatorial auctions, computable with demand and MPH-k queries.This improves the prior polynomial-time guarantee from O(k^2) to O(k), and yields 2 for XOS valuations.
  • 4 New and Improved Prophet Inequalities: The framework also gives a (5 + ǫ)-approximation for knapsack, improving to (3+ǫ) when demands are at most half capacity, and an (8d+ǫ)-approximation for d-sparse PIPs.These are computable using static prices.

2 General Model and Notation

The model describes sequential allocation under feasibility constraints, with independently drawn private valuations and quasilinear utilities. Posted-price mechanisms provide a truthful online allocation format in which agents sequentially choose utility-maximizing feasible outcomes.

  • Each agent has an outcome space containing a null outcome, and feasible allocations form a subset of the joint outcome space.
  • Valuations are bounded, independently drawn from publicly known distributions, and utilities equal value minus payment.
  • The welfare-maximizing rule OPT selects a feasible outcome maximizing total valuation, while ALG denotes any feasible allocation rule.
  • A pricing rule assigns outcome prices conditional on partial allocations and charges infinity for infeasible outcomes.
  • A posted-price mechanism approaches agents sequentially, offering menus based on prior allocations; order-oblivious mechanisms do not require a specific order.
  • An online allocation depends only on current and earlier values, and a prophet inequality bounds its stochastic competitive ratio.

3 A Framework for Prophet Inequalities

The framework characterizes full-information prices through balancedness conditions and transfers those guarantees to stochastic posted-price mechanisms. Its proof combines utility and revenue bounds, with refined weak balancedness supporting additional applications.

  • Exchange-compatible residual sets allow outcomes feasible after a partial allocation to be compared with the original allocation.
  • An (α, β)-balanced pricing rule imposes sufficient value and price bounds relative to an allocation rule and exchange-compatible residual sets.
  • Balancedness is useful because full-information pricing conditions extend to Bayesian settings.
  • Theorem 3.1 scales prices by δ = α/(1+αβ), producing welfare at least 1/(1+αβ) of the expected welfare of ALG.
  • The proof separately lower-bounds expected utility and revenue, then combines them through quasilinearity to obtain social welfare.
  • Weakly (α, β1, β2)-balanced prices yield welfare at least 1/[α(2β1+4β2)] times ALG when β1+β2 ≥ 1.

4 New and Improved Prophet Inequalities

The framework produces new and improved price-based prophet inequalities across combinatorial auctions, knapsack, fractional knapsack, and related packing settings. Fractional relaxations and sampling make several guarantees computationally efficient.

  • Combinatorial Auctions with Bounded Bundle Size: For bundles of size at most d, fractional relaxation improves the polynomial-time approximation from O(d^2) to O(d).
  • Combinatorial Auctions with Bounded Bundle Size: Static anonymous item prices yield a (4d−2−ε)-approximate posted-price mechanism computable with polynomially many demand queries.
  • Combinatorial Auctions with Bounded Bundle Size: Theorem 3.2 yields a (4d−2)-approximation for the fractional allocation problem, with ε-approximate prices computable by sampling.
  • Knapsack: For knapsack with requests at most half the capacity, a single static anonymous per-unit price gives a (3+ε)-approximate polynomial-time posted-price mechanism.
  • Knapsack: Without the size restriction, selecting between two pricing schemes by sampling gives a (5+ε)-approximate price-based prophet inequality.
  • Fractional Knapsack: Fractional knapsack admits a (2+ε)-approximate polynomial-time posted-price mechanism, improving the prior bound of approximately 11.657.

5 From Price of Anarchy to Prophet Inequalities

The paper connects mechanism smoothness to posted-price prophet inequalities. Under monotone critical prices and suitable smoothness conditions, smoothness guarantees can be converted into comparable pricing guarantees, with broader black-box reductions for binary settings.

  • Smoothness does not generally suffice for comparable posted-price guarantees, but typical smoothness proofs can yield such reductions under additional conditions.
  • For binary single-parameter problems, smoothness and non-decreasing critical prices imply balanced prices whose guarantee is within a constant factor of the mechanism’s Price of Anarchy.
  • Theorem 5.1 sets prices using the maximum of an agent’s value and its critical price, obtaining (1, (μ+1+λ)/λ)-balanced prices.
  • Outcome smoothness uses target outcomes from deviations; with non-decreasing critical prices, these critical prices yield an O(λ/μ)-approximation matching the original mechanism’s Price of Anarchy guarantee.
  • Theorem 5.2 extends the conversion to modified feasibility spaces and produces a pricing rule that is (λ, μ/λ)-balanced with respect to an algorithm recovering OPT with probability λ.
  • For binary single-parameter settings, an O(γ) smoothness-based Price of Anarchy guarantee yields an O(γ^2)-approximate prophet inequality.
  • For matroids, the framework gives a 4-approximation and, with stronger monotonicity, an improved factor of 2 matching the known prophet inequality.

6 Conclusions and Open Problems

The framework establishes prophet inequalities and posted-price mechanisms for multi-dimensional settings, while leaving approximation, pricing-power, and framework-extension questions open.

  • The paper introduces a general framework for establishing prophet inequalities and posted-price mechanisms in multi-dimensional settings.
  • The best achievable approximation remains open for settings including intersections of two matroids and subadditive combinatorial auctions.For two matroids, the stated bounds are 2 and 6; for subadditive auctions, the upper bound is logarithmic in m while the lower bound is 2.
  • It is unknown whether some prophet inequalities cannot be implemented using posted prices, including questions about anonymous, personalized, item, bundle, static, and dynamic prices.
  • Open directions include randomized dynamic pricing, seller-side costs beyond feasibility constraints, removing price monotonicity, improving reduction factors, and understanding balancedness in large markets.

A Classic Prophet Inequality via Balanced Prices

The framework re-derives the classic single-item prophet inequality by using a fixed posted price as a (1,1)-balanced pricing rule.

  • The appendix establishes a (1, 1)-balanced pricing rule for the classic single-item setting, yielding a factor-2 approximation.
  • The price for allocating the item is maxℓvℓ when it remains unallocated and infinity otherwise, while the price for no allocation is zero.
  • These prices are (1, 1)-balanced with respect to OPT and residual feasibility sets that are either the original constraint or empty.
  • When the item is allocated, the residual optimum is zero and the payment equals the offline optimum; when unallocated, the residual optimum equals the offline optimum.

B Proof of Theorem 3.2

The proof of Theorem 3.2 follows the framework’s utility and revenue decomposition, applying balancedness properties and combining the resulting bounds.

  • The proof defines the residual allocation x′(v, v′) as the welfare-maximizing allocation for valuation profile v′ over Fx(v).
  • Sampling an independent valuation profile v′ provides the utility bound used in the proof.
  • Property (b) upper-bounds the final term pointwise for every valuation pair v and v′.
  • Replacing v′ with ˜v and combining the resulting inequalities completes the utility-side bound.
  • Property (a) supplies the revenue bound, which is then combined with the utility bound by distinguishing whether β2 ≥ 1.
  • The combination uses nonnegative utilities and the inequality ui(v) ≥ ρui(v) for 0 ≤ ρ ≤ 1, with δ set to 1.

C Composition Results

Balanced prices compose across preferences and separate markets, extending the framework to maximum-over-valuations and additive multi-market settings, including weakly balanced rules.

  • The composition results apply to XOS composition and can extend to general approximation algorithms under mild conditions.
  • Closure under Maximum: Supporting valuation profiles are pointwise dominated by the original valuation and agree with it on the selected allocation.
  • Closure under Maximum: Consistency requires the allocation rule’s selected outcome under the supporting profile to achieve at least as much supporting-profile value as the original outcome.
  • Closure under Maximum: The optimal allocation rule is consistent because the original optimum remains feasible under the supporting valuation profile.
  • Closure under Maximum: Theorem C.1 transfers balancedness to a supporting valuation profile for a consistent allocation rule.
  • Closure under Addition: The joint problem uses the product allocation space and product feasibility constraint across the component markets.
  • Closure under Addition: For additive preferences across separate allocation problems, component pricing rules combine into a joint (α, β)-balanced pricing rule.
  • Both composition theorems can be generalized to weakly balanced pricing rules.

D Proof of Theorem 1.1

The appendix establishes balanced pricing results for MPH-k valuations, including XOS as a special case, and explains computational guarantees based on oracle access and fractional allocations.

  • Combinatorial Auctions with MPH-k Valuations: MPH-k valuations are a maximum over positive hypergraph-k functions, while XOS valuations coincide with the MPH-1 special case.The MPH hierarchy includes all valuations and subsumes several important valuation classes.
  • Existential O(k) Result: Prices are formed from supporting hypergraph weights and extended linearly to bundles and fractional allocations.The construction uses weights of supporting hyperedges containing each item.
  • Existential O(k) Result: (1, 1, k −1)-balanced prices exist for arbitrary allocation rules and MPH-k valuation profiles.For XOS valuations, this specializes to (1, 1)-balanced prices.
  • Computational O(k) Result: A (4k −2)-approximate price-based prophet inequality can be computed for MPH-k valuations with demand and MPH-k oracle access.The resulting posted-price mechanism allows agents to purchase fractional allocations at posted prices.
  • Computational O(k) Result: The configuration LP computes a welfare-maximizing fractional allocation, and balanced prices remain valid when feasibility is extended to fractional allocations.The fractional construction uses the optimal LP solution and scales prices over fractional outcomes.

E Proof of Theorem 1.3

For d-sparse linear packing programs, the appendix constructs prices from an offline allocation and proves balancedness for both fractional and integral feasibility.

  • Theorem E.1: Weakly (1, 0, d)- and (2, 0, d)-balanced prices exist for fractional and integral solutions, respectively.The programs have unit capacities and column sparsity bounded by d.
  • Theorem E.1: The prices can be computed by running the allocation algorithm ALG once.The pricing scheme uses x∗ = ALG(v) and assigns per-unit prices through the packing constraints.
  • Pricing constructions: The fractional pricing scheme is weakly (1, 0, d)-balanced, whereas the integral scheme is weakly (2, 0, d)-balanced.The two guarantees correspond to the fractional and integral feasible solution spaces.
  • Pricing Integral Problems based on Fractional Solutions: The framework also permits pricing integral problems from optimal fractional solutions, preserving the stated approximation guarantees relative to the fractional optimum.This extension uses distributions over exchange-compatible outcome profiles.

F Proof of Theorem 1.4

For multi-dimensional matroid settings, the appendix proves balanced prices for additive, submodular, and XOS valuations, with a polynomial-time route for submodular valuations through greedy allocation.

  • Theorem F.1: (1, 1)-balanced prices exist with respect to OPT for additive, submodular, and XOS valuations.The construction applies to multi-dimensional matroid feasibility constraints.
  • Theorem F.1: The result specializes to (1, 1)-balanced prices in the single-dimensional matroid setting.This is the setting where each agent controls exactly one ground-set element.
  • Proof of Theorem F.2: The pricing rule is proved balanced using monotonicity, telescoping sums, and matroid exchange arguments.Theorem F.2 establishes (1, 1)-balancedness for the pricing rule defined from the optimal allocation.
  • Computational Aspects: For additive valuations, the price construction is polynomial-time because the greedy algorithm is optimal.For submodular and XOS valuations, computing the optimal allocation is NP-hard.
  • Computational Aspects: A greedy allocation yields prices computable in polynomial time and a 4-approximation for submodular valuations.The guarantee follows because greedy is a 2-approximation to OPT for submodular valuations.

G A Smooth Mechanism Without Good Posted Prices

The appendix separates smoothness from posted-price performance by exhibiting a welfare problem with a constant-factor smooth mechanism but no comparably good posted-price mechanism.

  • Separation result: A downward-closed welfare maximization problem admits a (1, 0)-smooth mechanism while every posted-price mechanism has approximation factor Ω(n).The smooth mechanism returns the welfare-optimal allocation and charges zero payments.
  • Smooth mechanism: The smooth mechanism satisfies all agents’ desires by assigning the reported common sequence to every agent.Truth-telling is the required deviation for the (1, 0)-smoothness guarantee.
  • Posted-price limitation: After the first nonempty posted-price purchase, each later agent obtains positive value with probability 1/k.The later agent must have the same uniformly drawn desired value as the first purchased allocation.
  • Posted-price limitation: Because optimal welfare is n, posted-price mechanisms cannot obtain more than an Ω(n) approximation to optimal welfare.The posted-price welfare is bounded by the first successful buyer plus subsequent matches.

H Proof of Theorem 5.2

The proof constructs prices from weakly outcome-smooth mechanisms and uses their properties to establish balancedness. Under the stated permeability and scale-invariance conditions, the pricing rule satisfies both balancedness conditions with explicit parameters.

  • Framework and construction: The proof proceeds by defining weak outcome smoothness, constructing prices from payments, and proving the two balancedness conditions separately.The construction uses an extended outcome space with three copies of each agent, assigning them distinct roles in defining prices.
  • Framework and construction: Scale invariance permits reducing (λ, µ1, µ2)-outcome smoothness to (λ, 0, µ1 + µ2)-outcome smoothness.The reduction preserves the relevant outcome x′ under valuation scaling.
  • Balancedness conditions: The constructed prices satisfy Condition (a) with α = λ when the allocation rule ALG returns OPT(v) with probability λ.This conclusion follows from Lemma H.3 under outcome smoothness on every subinstance and scale-invariant outcomes.
  • Balancedness conditions: If the prices are monotonically increasing, they satisfy Condition (b) with β = µ/λ.The proof bounds the relevant price sum using outcome smoothness and the range of x′(· | z).
  • Permeability connection: For binary single-parameter problems, smoothness implies permeability with γ ≤ (µ + 1)/λ, connecting mechanism smoothness to the price construction.This permeability bound is stated for first-price mechanisms based on allocation rule f.

I.2.2 Proof of Theorem I.2

The proof establishes balancedness for prices generated by a γ-permeable greedy allocation rule. A zero-one valuation argument bounds the relevant combinatorial sets, and layering extends that bound to arbitrary valuations.

  • Layering argument: The zero-one valuation lemma is applied layer by layer to value thresholds, bounding each layer’s covered players by γ times the corresponding greedy set.For each threshold v(j), the proof sets At = x[t], Bt = r(t) ∩ Sj, and C = Tj.
  • Price construction and Condition (a): The pricing rule first establishes Condition (a) with α = γ for any allocation rule ALG and canonical exchange-feasible sets.The prices are constructed by processing players in non-increasing value order and adding feasible players outside the fixed allocation.
  • Zero-one valuation lemma: Permeability gives the combinatorial bound |C| ≤ γ · |B0| for nested sets satisfying the stated feasibility conditions.The proof recursively constructs sets Ct and sums their differences as a telescoping sum.
  • Layering argument: The layering argument proves Condition (b) with β1 = 0 and β2 = γ for the pricing rule generated by the greedy allocation.The resulting statement holds for any allocation rule ALG and the canonical exchange-feasible sets.
  • Welfare-maximizing allocation: For welfare-maximizing allocation, the analogous construction satisfies Condition (a) with α = 1 and Condition (b) with β2 = γ^2.If both greedy and welfare-maximizing rules are permeable, their parameters satisfy γOPT ≥ γGRD.
Loading 1612.03161v2…