Prophet Inequalities with Limited Information

1.1 Our results

• The k-uniform matroid single-sample guarantee is asymptotically optimal as a function of k.Its analysis models samples and values as correlated positive and negative steps in a random walk.Source: §1.1 · p. 2, §1.3 · p. 4
• The paper gives single-sample guarantees of 1/16 for transversal matroids and 1/8 for graphic matroids.Source: §1.1 · p. 2
• A 1/6.75-competitive constant-sample prophet inequality is given for constant-degree bipartite matchings.The online algorithm uses a constant number of samples.Source: §1.1 · p. 2

1.2 New Results in Mechanism Design

• For asymmetric bidders, the paper constructs truthful, approximately optimal auctions in certain multidimensional settings without learning virtual values.The analysis extends existing machinery to analyze expected virtual surplus without computing virtual values.Source: §1.2 · p. 3
• The paper gives approximately optimal single-sample sequential posted-price mechanisms for all matroid settings.These improve on previously known mechanisms limited to k-uniform settings and identical bidder distributions.Source: §1.2 · p. 3
• Single-sample order-oblivious posted-price mechanisms are constructed for the prophet-inequality environments, including several matroid families; matching settings use constant samples.The mechanisms do not require full distribution knowledge or the ability to compute virtual values.Source: §1.2 · p. 3

1.3 Our techniques

• A black-box reduction converts order-oblivious secretary algorithms into single-sample prophet inequalities for transversal, graphic, and laminar matroids.For k-uniform matroids, a correlated-random-walk analysis supports the asymptotically optimal guarantee; for constant-degree matching, sufficient thresholds need not track the prophet’s thresholds.Source: §1.3 · pp. 3–4
• Limited-information prophet inequalities are not provided for settings such as arbitrary matroids or intersections of arbitrary matroids.The paper identifies these as settings where full-information results exist but limited-information results do not.Source: §1.3 · p. 4

• The offline benchmark selects a maximum-weight feasible set, while an online algorithm must accept or reject each revealed item irrevocably and keep accepted items feasible.Source: §2 · p. 4
• Prophet-inequality guarantees compare expected online reward with the offline optimum under independent values, and must hold regardless of the elements’ reveal order.Source: §2 · pp. 4–5
• A constant-sample prophet algorithm sees a fixed number of distribution samples; the paper’s results generally use one sample, except matching results.Source: §2 · p. 5
• Secretary problems instead use adversarially chosen values revealed in random order, whereas prophet problems use random values presented in adversarial order.Source: §2 · p. 5

3 Prophet Inequalities from Secretary Algorithms

• Order-oblivious algorithms first observe a random-permutation prefix without accepting, then retain their guarantee when the remaining elements arrive in any order.Source: §3 · p. 5
• The reduction gives single-sample inequalities for graphic, transversal, and laminar matroids, and for general matroids with identical distributions.Source: §3 · pp. 5–6
• The simulated secretary algorithm uses randomly permuted samples for its observation phase, while the corresponding values are processed online.Source: §3 · p. 6
• An order-oblivious secretary algorithm yields a single-sample prophet inequality with the same competitive ratio.Source: §3 · pp. 5–6

4 Single-Sample Prophet Inequalities for k-Uniform Matroids

• The algorithm uses correlated random walks, pairing upward sample steps with downward value steps, to analyze selection of the top k values.Source: §4 · p. 7

4.1 The Rehearsal Algorithm

• Each of k slots has a threshold; an arriving value fills the highest-threshold available slot it qualifies for, or is rejected if none qualifies.Source: §4.1 · p. 7
• The threshold construction modifies the intuitive sample-rank rule by repeating selected sample thresholds so the probability of selecting the highest-value items is sufficiently close to 1.Source: §4.1 · p. 7
• The Rehearsal Algorithm achieves a single-sample competitive ratio of 1 - O(1/sqrt(k)) for k-uniform matroids.Source: §4.1 · p. 7, §4 · p. 7

5 Bipartite Matching Environments

• The edge index combines the edge’s ranks at its two endpoints, and incident edges receive distinct indices.Source: §5 · p. 7
• Each edge receives a price from a sample-based threshold, and is accepted only if it exceeds that price and preserves a matching.Source: §5 · p. 8
• PMatching guarantees a 1/6.75 competitive ratio for degree-d bipartite matching environments.Source: §5 · p. 8
• For general bipartite matchings, an analogous algorithm obtains the same competitive ratio using n samples.Source: §5 · p. 8

6 Mechanism Design with Limited Information

• The section introduces limited-information SPMs for matroids and constant-degree matchings, and OPMs for several matroid families and matching settings.The SPM results cover identical regular or distinct MHR distributions; the OPM results include partition, graphic, laminar, and transversal matroids.Source: §6 · pp. 8–9

6.1 Mechanism Design Preliminaries

• The multidimensional reduction maps buyers and goods to a single-dimensional copies environment, where an α-approximate OPM yields a truthful α-approximate mechanism.The cited result states its guarantee relative to the optimal deterministic mechanism; against randomized mechanisms, the stated guarantee is α/5.Source: §6.1 · p. 9

6.2 From Prophet Inequalities to Mechanisms

• Monotone limited-information prophet algorithms induce truthful sequential posted-price mechanisms that approximately maximize welfare.Acceptance depends on previously accepted bidders and samples from the distributions.Source: §6.2 · p. 10

6.3 From Welfare to Revenue: The I.I.D. Case

• The matching algorithm is not comparison-based; substituting greedy matching makes it comparison-based but loses a factor of 2 in its competitive ratio.The section says the welfare-to-revenue reduction for i.i.d. distributions requires a comparison-based mechanism.Source: §6.3 · p. 10
• For i.i.d. regular distributions, combining a comparison-based welfare mechanism with lazy sample reserves yields an α/2 revenue approximation.With monopoly reserves, the theorem gives an α revenue approximation; replacing them with samples relies on a separate result.Source: §6.3 · p. 10

6.4 From Welfare to Revenue: the MHR case

• For MHR distributions, combining a welfare mechanism with lazy sample reserves gives an α/(2e) revenue approximation and an α/2 welfare approximation.The section notes that an analogous welfare-to-revenue result is not known for multidimensional settings.Source: §6.4 · p. 11

6.5 Our mechanisms

• The mechanisms extend to unit-demand and constant-degree matching settings; matching auctions use a constant number of samples, while matroid SPMs can use a single sample.For constant-degree bipartite matching, the section gives MHR and i.i.d.-regular auction results; it also gives a single-sample matroid SPM for MHR distributions.Source: §6.5 · p. 11

A Matroids and Feasibility Constraints

• A matroid is a downward-closed set system containing the empty set and satisfying the augmentation property.Uniform, partition, laminar, graphic, and transversal matroids are described as examples, alongside bipartite matching constraints.Source: A Matroids and Feasibility Constraints · p. 13
• Bipartite matching feasibility requires selected edges to share no vertices; degree bounds limit the number of incident edges per vertex.A matroid-independent set obeys the downward-closure and augmentation conditions stated above.Source: A Matroids and Feasibility Constraints · p. 13

B Omitted Details From Section 6.1

• In single-dimensional mechanism design, monotone allocation rules characterize truthful mechanisms when paired with the corresponding price rule.The appendix also defines MHR distributions through an increasing hazard rate and regular distributions through an increasing virtual value.Source: B Omitted Details From Section 6.1 · p. 14
• An SPM offers bidders sequential take-it-or-leave-it prices; an OPM retains its guarantee even when an adversary chooses the arrival order.The appendix also describes unit-demand allocations as those assigning at most one item to each buyer.Source: B Omitted Details From Section 6.1 · p. 14

C Omitted Proofs and Algorithms from section 3

• An order-oblivious secretary algorithm with competitive ratio α yields a single-sample prophet algorithm with the same ratio α.The construction randomly permutes the samples, gives the first k to the secretary algorithm, then presents the remaining values in an arbitrary order.Source: C Omitted Proofs and Algorithms from… · p. 15
• The construction uses a random sample permutation to separate the secretary algorithm's sample inputs from the realized values it considers.The proof compares the resulting expected reward with the prophet's expected reward.Source: C Omitted Proofs and Algorithms from… · p. 15

C.1 Existing order-oblivious secretary algorithms

• The general-matroid algorithm is order-oblivious: it uses a rank-based threshold on the first half of its input and accepts feasible later values above it.For matroids of rank below 12, it instead runs the rank-1 algorithm.Source: §C.1 · p. 15
• Dimitrov and Plaxton’s transversal-matroid algorithm is 1/16-competitive regardless of the order of revealed elements, making it order-oblivious.It uses discarded sample values to build an auxiliary matching before constructing the real matching.Source: §C.1 · p. 15
• The rank-1 secretary algorithm samples an initial segment, sets a threshold at its maximum, and accepts the first later value above that threshold.The section identifies this as a 1/4-competitive order-oblivious algorithm.Source: §C.1 · p. 16
• Replacing Dynkin’s algorithm with its order-oblivious counterpart gives a 1/8-competitive secretary algorithm for graphic matroids.The algorithm partitions edges into blocks by vertex and runs a rank-1 algorithm on each block; the paper also describes the laminar algorithm as order-oblivious in this partitioned sense.Source: §C.1 · p. 16

D Omitted Proofs from Section 5

• PMatching guarantees a 1/6.75 competitive ratio for degree-d bipartite matching environments.The proof reduces the guarantee to a constant lower bound on the probability that neither endpoint is occupied by another accepted edge.Source: D Omitted Proofs from Section 5 · pp. 16–17
• The algorithm samples a price for each edge, then accepts it only if its value meets the price, a coin with probability 1/3 permits acceptance, and adding it preserves a matching.These conditions are represented by events X_e, Y_e, and Z_e.Source: D Omitted Proofs from Section 5 · p. 17
• The proof uses events E1 and E2 to require that no other accepted edge shares either endpoint with the edge under analysis.When both events hold, adding that edge preserves independence, so Z_e holds.Source: D Omitted Proofs from Section 5 · p. 17
• The analysis needs d^2 samples only to establish independence between prices of incident edges; general matchings can instead use |E| samples to make all edge prices independent.The proof identifies a constant lower bound on Pr[E1 and E2] as sufficient for a constant competitive ratio.Source: D Omitted Proofs from Section 5 · pp. 17–18

E Omitted Proofs from Section 6

• For regular, not necessarily identical distributions, lazy single-sample reserves preserve a mechanism’s α revenue competitive ratio.The cited lemma applies to downwards-closed set systems.Source: E Omitted Proofs from Section 6 · p. 18
• For MHR distributions, lazily combining a universally truthful mechanism with monopoly reserves preserves its welfare competitive ratio α as a revenue competitive ratio.The distributions need not be identical.Source: E Omitted Proofs from Section 6 · p. 19
• A comparison-based mechanism with welfare competitive ratio α retains ratio α for revenue when combined eagerly or lazily with monopoly reserves, for identical regular distributions.The theorem applies to any downwards-closed feasibility system.Source: E Omitted Proofs from Section 6 · p. 19
• With identical regular distributions, truthful OPMs use two samples for k-uniform matroids and one sample for graphic, transversal, and laminar matroids.The listed revenue ratios are 1/16 for graphic matroids and 1/32 for transversal matroids; the laminar ratio is given as 1/(24√3).Source: E Omitted Proofs from Section 6 · p. 21
• For a degree d-bipartite matching, the revenue competitive ratio is 1/27 and the welfare competitive ratio is 1/27, using d2 + 1 samples from D.Source: E Omitted Proofs from Section 6 · p. 21
• For non-identical MHR distributions, truthful OPMs attain revenue ratios of 1/(16e) for graphic and 1/(32e) for transversal matroids, using one sample.Source: E Omitted Proofs from Section 6 · p. 21

F The Free-Order Model

• Because the free-order secretary algorithm satisfies the modified order-oblivious definition, it implies a single-sample prophet inequality for that model.Source: F The Free-Order Model · p. 22
• The algorithm samples a random subset S, finds its maximum-weight basis, then processes remaining elements in an order the algorithm chooses, accepting feasible elements above the current basis weight.The sample size is drawn from Binomial(n, 1/2).Source: F The Free-Order Model · p. 22
• The analysis relates acceptance to costs C(y,S) and C(y,P−{y}); when the former is greater, the algorithm will not have spanned y when processing it.The cost is defined using the weight at which an element enters the span of a weight-ordered set.Source: F The Free-Order Model · p. 22
• The algorithm of [17] obtains a 1/4 competitive ratio for matroids in the free-order model.Each element in the maximum-weight basis is accepted with probability 1/4 under the proof’s sampling and cost comparison.Source: F The Free-Order Model · p. 22

G Analysis of the Rehearsal Algorithm

• The rehearsal algorithm is a single-sample algorithm for the prophet problem on a k-uniform matroid.Source: G Analysis of the Rehearsal Algorithm · p. 23
• The theorem presents a competitive-ratio guarantee for the rehearsal algorithm.Source: G Analysis of the Rehearsal Algorithm · p. 23
• The stated setting is a k-uniform matroid, rather than an unrestricted set system.Source: G Analysis of the Rehearsal Algorithm · p. 23

G.1 Part I: The worst adversarial ordering and defining the random walk RW

• The rehearsal algorithm’s worst-case order reveals values in increasing order.Swapping out-of-order values cannot improve the accepted reward.Source: §G.1 · p. 23
• For analysis, two samples are drawn per item, then coin flips assign one as the value and the other as the sample.The guarantee is analyzed in expectation over those assignments for fixed paired samples.Source: §G.1 · p. 24
• The analysis aims to show that rehearsal achieves (1-O(1/sqrt(k)))·OPT.The section reduces this goal to bounds involving the probabilities that the walk’s right height is zero.Source: §G.1 · p. 24
• The random walk tracks sample/value assignments: values move it down, threshold-setting samples move it up, and some samples leave it unchanged.A sample that sets a repeated threshold can produce a larger upward step.Source: §G.1 · p. 24
• The figure illustrates that a value is accepted when its right height is positive, while its left height counts rejected values to its left.The walk’s heights connect its path to the rehearsal algorithm’s selections.Source: Figure 1 · p. 25, §G.1 · p. 26

G.2 Rehearsal Algorithm Analysis Part II: Bounding the height of the random walk

• For small indices, a fixed-jump walk RW′ dominates RW’s rightward height with high probability, reducing the bound to controlling RW′’s leftward height.The proof establishes high-probability events for the rehearsal-jump location and pairwise walk differences, then couples RW and RW′ to share coin flips.Source: §G.2 · pp. 27, 29
• For small i and j < i, decorrelation lowers the probability that RW′’s rightward height at j is zero, allowing the proof to bound the expected positive leftward height.For an independent walk, the zero-height event is bounded using the reflection principle; removing a negatively correlated pair cannot increase its probability.Source: §G.2 · pp. 27, 30
• For every j < i, the jump either leaves RW(j) − RW(i) unchanged or decreases that difference by 2.Source: §G.2 · p. 27

• An injective map from S1 to S0 shows that removing the chosen pair cannot decrease the probability that H(RW′′) = 0 and RW′′(n) ≤ −m.The proof partitions instances by peak heights and endpoint, then maps instances in S1 into S0.Source: §G.2 · p. 31
• Repeatedly removing the earliest-ending correlated pair yields independent steps with a k jump at the end, while the probability that H(RW′) ≥ 0 only increases and is O(1/k).Source: §G.2 · p. 32
• The rehearsal algorithm is 1 − O(1/k)-competitive, completing the proof of Theorem 10.Source: §G.2 · p. 32