Source-linked AI summary
Matroid Prophet Inequalities
Robert Kleinberg, S. Matthew Weinberg
TL;DR
The paper asks how prophet inequalities extend when online and offline selection must satisfy matroid constraints, and how these guarantees apply to mechanism design. It develops threshold-based online algorithms and proves a factor-2 guarantee for matroids and O(p)-scale guarantees for intersections of p matroids, with corresponding revenue approximations.
Problem
The paper studies extending single-selection prophet inequalities to multiple selections under matroid constraints and applying the resulting bounds to Bayesian mechanism design.
Method
The paper constructs monotone threshold-based online selection algorithms, including a fictional second phase with independently sampled weights, and analyzes them through matroid feasibility.
Results
The algorithms achieve at least half the prophet’s expected reward for matroids and at least 1/(4p − 2) for intersections of p matroids; the latter ratio is tight up to a constant factor.
Takeaways & Limitations
The results yield 2-approximation and (4p − 2)-approximation guarantees for Bayesian optimal revenue in matroid and p-matroid-intersection settings, respectively.
Takeaways & Limitations
The mechanism-design interpretation assumes regular value distributions; non-regular distributions require ironing and randomized pricing, while order-aware algorithms remain an open question beyond the stated setting.
Abstract
from arXiv · showhide
Consider a gambler who observes a sequence of independent, non-negative random numbers and is allowed to stop the sequence at any time, claiming a reward equal to the most recent observation. The famous prophet inequality of Krengel, Sucheston, and Garling asserts that a gambler who knows the distribution of each random variable can achieve at least half as much reward, in expectation, as a "prophet" who knows the sampled values of each random variable and can choose the largest one. We generalize this result to the setting in which the gambler and the prophet are allowed to make more than one selection, subject to a matroid constraint. We show that the gambler can still achieve at least half as much reward as the prophet; this result is the best possible, since it is known that the ratio cannot be improved even in the original prophet inequality, which corresponds to the special case of rank-one matroids. Generalizing the result still further, we show that under an intersection of p matroid constraints, the prophet's reward exceeds the gambler's by a factor of at most O(p), and this factor is also tight. Beyond their interest as theorems about pure online algorithms or optimal stopping rules, these results also have applications to mechanism design. Our results imply improved bounds on the ability of sequential posted-price mechanisms to approximate Bayesian optimal mechanisms in both single-parameter and multi-parameter settings. In particular, our results imply the first efficiently computable constant-factor approximations to the Bayesian optimal revenue in certain multi-parameter settings.
1 Introduction
The paper extends prophet inequalities from single selections to matroid-constrained online selection and then to intersections of matroids. It also connects these guarantees to sequential posted-price mechanisms and Bayesian mechanism design.
- A prophet inequality compares an online player using current and past observations with a prophet who knows the entire sequence and selects its maximum.
- A matroid-constrained online algorithm achieves at least half the expected weight of the maximum-weight basis, and the factor 2 is best possible.
- The rank-one algorithm uses threshold T = E[max_i X_i]/2 and accepts the first observed weight exceeding T.
- For intersections of p matroids, an online algorithm achieves at least 1/(4p − 2) of the expected maximum feasible weight, with the ratio tight up to a constant factor.
- In BMUMD settings, the results yield truthful mechanisms that 2-approximate Bayesian optimal revenue for matroids and (4p − 2)-approximate it for p-matroid intersections.
2 Preliminaries
The preliminaries define Bayesian online selection over downward-closed feasibility systems and formalize online algorithms through their observed input prefixes and selection decisions. They focus on fixed-order and weight-adaptive adversaries and introduce threshold-based analysis for matroids.
- A Bayesian online selection instance has a ground set, a downward-closed feasible-set system, and independent non-negative element weights drawn from specified distributions.
- For a weight assignment, MAX(w) is the maximum-weight feasible set and OPT(w) is its weight.
- An online algorithm maps ordered element-weight sequences to feasible selections while making decisions consistently for sequences sharing the same observed prefix.
- Monotone deterministic online algorithms can be represented by thresholds depending only on prior observations, with infinite thresholds for infeasible additions.
- The main result achieves 1/2 OPT against a fixed-order adversary and 1/(4p − 2) OPT against an online weight-adaptive adversary.
- The paper studies matroids, whose independent sets satisfy the exchange axiom; maximal independent sets are bases, and rank measures maximum independent-set cardinality.
3 Algorithms for Matroids
This section develops a simple threshold-based approach for matroids, proving that α-balanced thresholds yield approximation guarantees and constructing such thresholds with α = 2.
- 3.1 Detour: The rank-one case: In the rank-one case, setting T = E[max_i X_i]/2 and accepting the first observation at least T gives the original factor-2 prophet inequality.The proof lower-bounds the algorithm’s expected reward by T while relating the prophet’s expectation to 2T.
- 3.2 A property guaranteeing α-approximation: The paper defines α-balanced thresholds by comparing the selected set A with an independently weighted maximum-weight basis partitioned into C(A) and R(A).The partition is chosen so A ∪ R(A) remains a basis and w′(R(A)) is maximized.
- 3.2 A property guaranteeing α-approximation: An algorithm with α-balanced thresholds achieves an expected reward of at least 1/α times OPT, even against online weight-adaptive adversaries.
- 3.3 Achieving 2-balanced thresholds: The general matroid algorithm accepts element x_i exactly when its observed weight w_i meets the threshold T_i, assigning T_i = ∞ when feasibility would be violated.The threshold construction is designed to establish the balanced-threshold properties.
- 3.3 Achieving 2-balanced thresholds: Matroid exchange and submodularity establish the structural properties needed to prove the 2-balanced-threshold condition.The proof uses the residual set R(A), its characterization as a maximum-weight basis of M/A, and submodularity of w′(R(S)).
4 Matroid intersections
For intersections of p matroids, the paper extends the balanced-threshold framework by combining per-matroid residual and cost sets, obtaining an O(p)-type approximation guarantee.
- 4.1 A generalization of α-balanced thresholds: For p matroids, the feasible sets are the intersection I = ∩_j I_j, and each matroid receives its own residual set R_j(A) and cost set C_j(A).The combined sets are R(A) = ∩_j R_j(A) and C(A) = ∪_j C_j(A).
- 4.1 A generalization of α-balanced thresholds: An algorithm with α-balanced thresholds for α ≥ 2 obtains the stated approximation guarantee against weight-adaptive adversaries under an intersection of p matroids.
- 4.1 A generalization of α-balanced thresholds: Choosing α = 2p yields an approximation guarantee of 1/(4p−2) for the intersection of p matroids.The paper notes that α = 2p is nearly optimal and always at least 2.
- 4.1 A generalization of α-balanced thresholds: The thresholds sum contributions from all matroid constraints, while infeasible elements receive infinite thresholds.The proof of the resulting bounds follows the single-matroid analysis and sums the per-matroid inequalities.
5 Lower Bounds
The paper gives matching lower-bound constructions showing that the factor 2 for matroids and the O(p) factor for intersections of p matroids cannot be improved.
- Matroid lower bound: 2 is tight for matroids: with two elements, the prophet gains 2 − 1/n in expectation while the gambler gains at most 1.The first element always has weight 1; the second has weight n with probability 1/n and 0 otherwise.
- p-matroid intersection lower bound: For intersections of p matroids, the gambler’s expected payoff is less than 2, whereas the prophet’s expected payoff is Θ(q), with q between p/2 and p.The construction uses independently activated elements with probability 1/q and yields a fully active row with constant probability.
- p-matroid intersection lower bound: The feasibility system in the intersection construction is representable as the intersection of q matroids, and q ≤ p.Each constraint is a partition matroid indexed by x ∈ Z_q.
- Tightness: Because the prophet obtains Θ(p) while the gambler obtains less than 2, no algorithm can achieve an approximation factor better than O(p).The construction therefore matches the paper’s upper-bound order for intersections of p matroids.
6 Interpretation as OPMs
The paper interprets its prophet-inequality algorithms as pricing tools for sequential posted-price mechanisms, connecting multi-parameter mechanisms to a related single-parameter copies domain. Under regular valuations, this yields revenue approximations tied directly to the prophet-inequality factor.
- Mechanism-design setting: BMUMD instances contain services partitioned among bidders, with allocations required to satisfy downward-closed feasibility constraints.The analysis assumes each bidder’s service values are independent random variables.
- Mechanism-design setting: The related domain Icopies replaces each multi-parameter bidder with separate single-service bidders while preserving the same feasibility constraints.This reduction supports comparison between mechanisms for the original and copies domains.
- Pricing construction: The construction uses prophet-algorithm thresholds T(A, x) to define posted prices for services based on the previously allocated set A.Prices are obtained from thresholds that the online algorithm would use at the relevant step.
- Pricing construction: Mechanism M_copies uses a weight-adaptive adversary and dynamic programming to choose an ordering that minimizes its expected revenue.The table entry V(A, i) records expected future revenue conditional on the already allocated set A; computing it requires exponential time and space.
- Mechanism properties: M_copies is not an OPM under the cited definition because a service’s price may depend on earlier bidders’ bids, although prices within each bidder’s service set are predetermined before that bidder’s bids are revealed.It retains the key within-bidder pricing property used for multi-parameter analysis.
- Revenue guarantees: 2 is the revenue approximation for matroid feasibility, while 4p − 2 is the approximation for intersections of p matroids.These guarantees apply to independent regular valuations and compare against the optimal deterministic mechanism.
A Proof of Proposition 3
The proof combines inequalities for α-balanced thresholds to derive a lower bound on the algorithm’s expected weight relative to the optimum.
- Final bound: Summing the inequalities yields E[w(A)] ≥ (α − p)/(α(α − 1)) OPT.The derivation uses T_i + (w_i − T_i)+ = w_i for all x_i ∈ A.
- Proof structure: The proof establishes three inequalities for any α-balanced thresholds before combining them.Equation (22) follows from the threshold definition, while (23) uses the same observations as an earlier equation and (24) uses the threshold property.
- Proof structure: The proof concludes once inequality (24) is established for arbitrary α-balanced thresholds.This completes the argument for the proposition.