Generalized Prophet Inequalities for Online Auctions

1.1 Background and Motivation

• The model includes utility maximizers, value maximizers, and intermediate agents with complex valuations, alongside stochastic budgets and objectives.The motivating applications include autobidding and auctions for website recommendation spots.Source: §1.1 · p. 2

Budget Reduction.

• Budgeted guarantees follow by capping valuations at budgets and changing objectives to value maximization in realizations where the original valuation exceeds the budget.The transformation addresses the fact that capping valuations alone can change which outcome an agent chooses.Source: Budget Reduction · p. 3

Utility-Bounded Prices

• Utility-bounded pricing rules yield liquid-welfare guarantees, and budgets and value maximizers worsen their guarantees by at most a factor of 2.The paper introduces utility-bounded prices to capture pricing rules whose analysis trades off revenue and utility.Source: Utility-Bounded Prices · p. 3

XOS Combinatorial Auctions

• For XOS valuations, half-pricing has competitive ratio 2 in the classic setting; for budgeted utility maximizers with liquid-welfare benchmark, the bound at δ = 1/2 is tight at 4.For every δ ∈ (0, 1), the paper constructs a matching lower bound.Source: XOS Combinatorial Auctions · pp. 3–4

Subadditive Combinatorial Auctions

• For subadditive auctions, dynamic bundle prices are 6(2 − σmin)-competitive, yielding a 12-competitive guarantee when agents have budgets.The framework also extends balanced prices to budgeted MPH-k auctions with an upper bound of 4k, and to matroid-constrained auctions with a 4-approximation or an 8-approximation for submodular valuations using computationally efficient prices.Source: Subadditive Combinatorial Auctions · pp. 4–5

1.3 Further Related Work

• The paper relates its price-sensitivity bounds to prior work whose budget-free reduction bounds depend on both σmin and σmax.The paper states that its bounds for σ ∈ [0, 1] depend only on σmin.Source: §1.3 · p. 5

• Feasible outcome profiles are downward closed: removing any subset of agents from a feasible profile leaves a feasible profile.The formulation represents each agent’s outcome in an outcome profile and permits partial profiles for subsets of agents.Source: §2 · p. 6
• A pricing rule assigns nonnegative prices to outcomes; arriving agents choose outcomes that maximize their objectives, subject to feasibility.Prices may depend on earlier agents’ outcomes, and infeasible outcomes receive infinite prices.Source: §2 · p. 6
• Each agent has a monotone valuation, budget, and price sensitivity drawn from a product distribution, and the valuation class is assumed closed under budget capping.An agent’s objective is valuation minus price scaled by price sensitivity, subject to return-on-spend and budget constraints.Source: §2 · p. 6
• Social welfare is the benchmark without budgets, while budgeted settings use liquid welfare, based on budget-capped valuations.When budgets are infinite, liquid welfare coincides with social welfare.Source: §2 · pp. 6–7

3.1 Budget-Reduction

• Budget reduction caps each valuation at its budget and sets price sensitivity to zero for agents whose chosen bundle reaches their budget; budget-free instances remain unchanged.Other agents retain their original price sensitivity in the proxy instance.Source: §3.1 · p. 7
• The proxy objective of the chosen bundle lower-bounds the proxy utility of any feasible alternative, allowing utility-maximizer lower-bound arguments to extend to the general setting.The paper notes such arguments in [FGL15] [DKL+24].Source: §3.1 · p. 8

3.2 Utility-Bounded Prices

• Definition 3.2 specifies a (λ,µ)-utility-bounded pricing rule using a distribution Yτ for each realization; when ALG=OPT, the rule is simply called utility-bounded.REV denotes the pricing rule’s expected revenue over D.Source: §3.2 · p. 8
• When µ>σmin, expected revenue is bounded above by the expected liquid welfare achieved by the pricing rule, supporting the second branch of the guarantee.When µ≤σmin, the revenue term is non-positive and the first branch applies.Source: §3.2 · pp. 8–9
• The competitive ratio deteriorates to at most C(2−σmin), and budgets worsen guarantees by at most a factor of 2, where C=max{1,µ}.This applies to a pricing rule that is Cλ-competitive in the budget-free utility-maximizing setting.Source: §3.2 · p. 9

4.1 XOS Combinatorial Auctions

• For XOS valuations, the upper bounds extend to stochastic agent objectives, while matching lower-bound constructions can use additive valuations and deterministic objectives.For budgeted instances, additive valuations, deterministic objectives, and deterministic budgets suffice to match the more general upper bound.Source: §4.1 · p. 12
• For the XOS half-pricing rule, the competitive ratio is 4−2σmin without budgets and remains 4 with budgets for all Σ.The upper bounds are tight; the half-pricing rule is not optimal for budget-free instances when σmin lies strictly between 0 and 1.Source: §4.1 · pp. 12–13

4.2 Subadditive Combinatorial Auctions

• The subadditive construction prices each available bundle using expected liquid welfare from the remaining online problem, and its pricing rule is (1, 1)-utility-bounded.The rule is defined for each arriving agent and current remaining-item set.Source: §4.2 · p. 13
• Dynamic personalized bundle prices achieve a competitive ratio of at most 6(2−σmin) for subadditive agents.The guarantee extends to stochastic budgets and the liquid-welfare benchmark because budget-capped subadditive valuations remain subadditive.Source: §4.2 · p. 14

5 Balanced Prices

• Balanced prices are defined for budget-free settings because objective-dependent prices and a budget reduction suffice to address budgeted settings under additional assumptions.Preservation under the reduction requires the allocation rule and pricing rule to agree across the original and reduced instances.Source: §5 · pp. 14–15
• If ALG and pricing rule p are both preserved under budget reduction, then scaled pricing rule δp is utility-bounded with respect to ALG, provided 0 < δ and δ(β1 + β2) < 1.Source: §5 · p. 15
• Utility-boundedness combines proxy-utility and revenue bounds to relate agents’ feasible deviations to welfare and revenue.The proof generalizes both bounds to budget-constrained settings.Source: §5 · p. 15
• For XOS auctions, the budget-free balanced-price result yields the same utility-bounded guarantee for scaled prices as the earlier analysis.The example uses α=1, β1=1, and β2=0.Source: §5 · p. 16

6 Conclusion

• For budget-free XOS auctions, the half-pricing rule’s competitive ratio interpolates linearly between 2 and 4 with the least price-sensitive agent’s price sensitivity.The conclusion also states tight bounds for a natural class of pricing rules in XOS settings.Source: §6 · p. 16
• Utility-bounded prices connect value maximizers with budget-constrained agents, and the half-pricing rule is not optimal under intermediate objectives.The framework includes balanced pricing and allocation rules preserved under budget reduction.Source: §6 · p. 16
• The conclusion reports constant competitive ratios up to subadditive valuations and leaves open whether a 2-competitive pricing rule exists beyond utility maximizers.Source: §6 · p. 16

A.1 Combinatorial Auctions with MPH-k valuations

• An MPH-k valuation is a maximum over positive hypergraph-k valuations, whose nonnegative hypergraph representations have rank at most k.The section introduces this valuation class as its setting.Source: §A.1 · p. 18
• Capping an MPH-k valuation at a finite budget produces another MPH-k valuation.The proof constructs supporting positive hypergraph-k valuations for the capped valuation.Source: §A.1 · pp. 18–19
• The pricing construction uses supporting hypergraph-k valuations of the budget-capped profile for the selected allocation to define item prices.The prices are preserved under the budget reduction when the allocation rule is OPT.Source: §A.1 · p. 19
• The posted-price mechanism has competitive ratio at most 4k for budgeted MPH-k agents with price sensitivities in Σ, using δ = 1/(2k).The section also says budget constraints barely worsen the upper bound for large k compared with the budget-free social-welfare ratio.Source: §A.1 · p. 19

A.2 Matroid Constrained Auctions

• The matroid pricing rule uses supporting additive valuations of the budget-capped profile for the liquid-welfare-optimal allocation, and assigns infinite price when adding a bundle violates independence.The budget-free balanced-pricing result is carried over using the budget reduction.Source: §A.2 · p. 20
• The posted-price mechanism achieves a competitive ratio of 4 for budgeted XOS agents under matroid constraints.The bound is minimized at δ = 1/2.Source: §A.2 · p. 20
• For submodular valuations, greedy allocation yields an 8-approximation to expected optimal liquid welfare, up to additive sampling error.The construction is computationally feasible under the stated oracle assumptions.Source: §A.2 · p. 20

Proof of Lemma 5.4

• The proof compares an agent's chosen outcome with an optimal allocation under the feasibility constraint induced by the current realization.It samples a second valuation and budget profile to define that comparison allocation.Source: Proof of Lemma 5.4 · p. 21
• The proposed deviation satisfies the RoS and budget constraints and is feasible by exchange compatibility.The proof then sums the resulting inequalities over agents.Source: Proof of Lemma 5.4 · p. 21
• Under the budget reduction, the expected welfare of the reduced instance equals the original expected liquid welfare for the preserved allocation rule.The proof uses this correspondence to convert the proxy-utility inequality into liquid-welfare terms.Source: Proof of Lemma 5.4 · p. 22

Proof of Lemma 5.5

• Lemma B.2 states a lower bound on revenue for the pricing rule δp when the pricing rule satisfies Theorem 5.3's conditions.The displayed bound itself is not specified in the supplied passage.Source: Proof of Lemma 5.5 · p. 22
• The proof begins by applying the first property of balanced prices.It then takes expectations and rewrites them as in the proof of Lemma 5.4, using preservation under the reduction.Source: Proof of Lemma 5.5 · p. 22