Beyond matroids: Secretary Problem and Prophet Inequality with general constraints

1 Introduction

• The arbitrary downward-closed setting extends beyond matroids, where related secretary and prophet problems had been studied but arbitrary families still lacked nontrivial upper bounds.Optimizing over arbitrary downward-closed families can be computationally intractable even offline, so the algorithms assume access to specified oracles.Source: §1 · pp. 1–2, Our results · p. 2

Our results

• O(log n) competitive ratios are achieved for both Downward-Closed Prophet and Downward-Closed Secretary when item values are in {0, 1}.This improves on the previously known trivial O(n) upper bound for arbitrary downward-closed constraints.Source: Our results · p. 2
• General non-negative valuations reduce to the {0, 1}-valued case with an O(log r) loss, yielding O(log n · log r) ratios for both problems.Here r is the cardinality of the largest feasible set.Source: Our results · p. 2
• A later observation connects the Secretary algorithm's minimal arrival-order assumptions to order-obliviousness, yielding Prophet results through a black-box reduction and a single-sample algorithm.The single-sample algorithm uses one sample per distribution instead of a full distribution description.Source: Our results · p. 2

Non-monotone feasibility constraints

• For non-monotone feasibility constraints, the paper discusses Prophet and Secretary variants and proves near-tight competitive-ratio lower bounds.Source: Non-monotone feasibility constraints · p. 3

1.1 Techniques

• Both algorithms use potential-function analyses, and the Downward-Closed Prophet analysis dynamically changes its potential when adequate progress cannot be guaranteed.The authors suggest this dynamic-potential idea may apply to other potential-function arguments.Source: §1.1 · p. 3

2 Prophet

• O(log n) is the competitive ratio of a deterministic Downward-Closed Prophet algorithm when item values are in {0,1}.Source: §2 · p. 3
• O(log n · log r) is the competitive ratio for general item values, where r is the largest feasible-set cardinality.Source: §2 · p. 3
• The extension separately recovers tail events, where one item has exceptionally high value, and core contributions spread across many items, then runs the better of two algorithms.The tail algorithm selects an item when its value is at least 2OPT. For the core, values below OPT/2r are ignored, the remaining values are partitioned into log r+2 intervals from OPT/2r through 2OPT, and the interval with largest expected contribution is rounded down before running the algorithm guaranteed by Theorem 1.Source: §2 · pp. 3–4

2.1 A dynamic potential function

• A dynamic potential asks whether a restricted prophet, committed to past decisions but omniscient about future realizations, can still reach target τ.As commitments restrict the prophet, the algorithm compares its solution to a lower target.Source: §2.1 · p. 4
• The algorithm marks items good when selecting one does not reduce the probability of reaching τ by more than an n^2 factor; bad items together account for at most a 1/n fraction of that probability.When the chance of seeing a good value-1 item falls below 1/3, lowering τ by 1 at least doubles the target probability; balancing these changes yields O(log n).Source: §2.1 · p. 4
• If no good item with value 1 has appeared by the last good item, the algorithm selects that item as though its value were 1, keeping the expected number of selected zero-value items to at most a constant fraction.Source: §2.1 · p. 5

Notation

• The selected set W contains items chosen so far, while ℓW is the index of the last selected item.Source: Notation · p. 5
• F_T contains feasible sets whose intersection with the items through max T is exactly T.Source: Notation · p. 5
• X_i is item i's random value, z_i its observed realization, and V is the value of the offline optimum.Source: Notation · p. 5
• τ is the current target value, and π is the probability of reaching τ given the current selected set and history.Source: Notation · p. 5, Algorithm · p. 6
• π_j is the probability of reaching τ if item j is selected next; a future item is good when π_j ≥ n^-2 · π.Source: Notation · p. 5
• A is the event that at least one good item has value 1.Source: Notation · p. 5

Algorithm

• After updating W, the algorithm lowers τ until Pr[A] ≥ 1/3 or |W| > τ; when Pr[A] is high enough, it waits for a good feasible item with value 1 and adds it to W.Source: Algorithm · p. 5
• If the last good item is reached without observing any good item of value 1, the algorithm adds that last good item to G and subtracts 1 from τ.Source: Algorithm · p. 5

• Concentration of the optimum is needed, but proving it for a maximum over an arbitrary family of set sums is nontrivial.Source: Concentration · p. 7
• Ledoux's inequality is selected because its exponent's denominator depends on the expected supremum rather than absolute item-value bounds.Source: Concentration · p. 7
• Represent each item as a vector whose set-coordinate is its value when included and zero otherwise; each coordinate function then sums to the value of its set.Source: Concentration · p. 7
• The proof assumes OPT ≥ log n without loss, since otherwise a trivial greedy algorithm achieves expected value Ω(OPT/log n).Source: Concentration · p. 7

• When Pr[A] ≤ 1/3, subtracting 1 from τ doubles π.Source: Main lemma · p. 8
• The proof argues that reaching τ without selecting any item from G has negligible probability relative to reaching τ overall.Source: Main lemma · p. 8
• If no item in G has value 1, the first item contributing to the optimum must be outside G, making it unlikely the optimum still reaches τ.Source: Main lemma · p. 8
• Most probability of reaching τ comes from event A, in which at least one good item has value 1, but this alone does not ensure Pr[A] is large.The proof notes that reaching τ may itself be unlikely and those events need not be independent.Source: Main lemma · pp. 8–9
• Conditioning on A can contribute at most 1 to the optimum, and the proof decomposes A into disjoint events A_j indexed by the first good item with value 1.Source: Main lemma · p. 9
• Changing an item's value can reduce the final solution by at most 1, and conditioning on B_j can only lower the probability of reaching the target.Source: Main lemma · p. 9

• |W| is at least OPT/(4 log n + 4) when the algorithm terminates.The proof first bounds the target τ by |W| and then relates τ to OPT.Source: Putting it all together · p. 10
• The algorithm terminates after at most O(OPT) decreases to τ.Source: Putting it all together · p. 10
• The algorithm’s expected value is at least |W|/3 because each added item has probability at most 2/3 of being zero-valued.Source: Putting it all together · p. 10

3 Secretary

• O(log n) competitive ratio is achieved deterministically for Downward-Closed Secretary when all values are in {0, 1}.Source: §3 · p. 10
• O(log n · log r) competitive ratio is achieved for general valuations, where r is the maximum feasible-set cardinality.The reduction partitions values into log r buckets and runs the binary algorithm on the last half of the arrivals.Source: §3 · pp. 10–11

3.1 Secretary algorithm

• A sliding window of size n/2 is gradually transformed from an offline solution on the first half into an online solution on the second half.The approach tests each arriving item against the preceding n/2 items to estimate its interaction with future items.Source: §3.1 · p. 11

Notation

• The notation distinguishes the current set W, feasible sets containing W, and offline optimum values restricted to a set of items.Source: Notation · p. 11

Algorithm

• The algorithm observes the first n/2 items without selecting them, then forgets one earlier item before considering each later arrival and adds an item when it contributes to the best feasible set.It initializes τ from the offline optimum on the observed items, scaled by 500 log n.Source: Algorithm · p. 11, §3.2 · p. 12

3.2 Analysis

• In the stated setup, the analysis compares how often the current solution’s value decreases when forgetting σj (“bad” events) with “good” events, when adding σn/2+j increases that value.The analysis uses a martingale version of Bennett’s inequality, which depends on variance rather than absolute bounds on variable values.Source: §3.2 · p. 11, Concentration · p. 13

• Θ(n) is the competitive ratio for Non-monotone Prophet with non-negative values.The upper-bound algorithm selects a feasible set containing an item with the largest expected contribution; a lower-bound construction gives online expected value 1/n while the offline optimum is approximately 1 − 1/e.Source: §4 · p. 14
• Non-monotone Secretary has competitive ratio at most n and at least Ω(n/ log* n).Source: §4 · p. 14
• O(log* n) consistent codewords yield expected online value O(log* n/n), versus offline value 1.The feasible sets encode Hadamard codewords, and the online selections must match the good codeword when its item arrives.Source: §4 · pp. 14–15
• After k log n periods, every pair of codewords disagrees on an observed item with high probability, forcing the algorithm to commit to one feasible subset.Source: §4 · p. 15

• OPT denotes the expected offline optimum, while W is the set selected by the algorithm and F is the family of feasible sets.Source: A List of symbols used in Section 2 · p. 17
• F_W denotes feasible sets containing W; X_i is item i’s random value and z_i its observed realization.Source: A List of symbols used in Section 2 · p. 17
• The listed event terms distinguish good events involving good items or realizations from bad events where preceding good items lack good realizations.Source: A List of symbols used in Section 2 · p. 17

B An Ω(log n/ log log n) lower bound

• An Ω(log n / log log n) lower bound holds for both Downward-Closed Prophet and Downward-Closed Secretary.The proof sketch is attributed to.Source: B An Ω(log n/ log log n) lower bound · p. 18
• Partition the n items into sets of size log n / log log n, with each item independently worth 1 with probability log log n / log n.With high probability, some feasible set has all items valued 1, making the expected offline optimum approximately log n / log log n.Source: B An Ω(log n/ log log n) lower bound · p. 18
• After selecting from any feasible set, the expected total value of its remaining items is below 1, so no online algorithm can achieve expected value above 2.Source: B An Ω(log n/ log log n) lower bound · p. 18

C Naive approaches for Downward-Closed Prophet

• The recursively optimal algorithm selects an item only when doing so increases its expected value, but its recursive structure is difficult to analyze against the offline benchmark.Source: C Naive approaches for Downward-Closed… · p. 18
• Counting maximal feasible sets misses how their intersections differ: sets with little overlap can be more likely to yield the best solution.Source: C Naive approaches for Downward-Closed… · p. 18
• The expected value of the optimum among currently feasible sets is attractive because it relates to the benchmark and concentrates, but it is random and hard to turn into a potential.Source: C Naive approaches for Downward-Closed… · p. 19
• For two disjoint maximal sets of size n/2 with uniform {0,1} values, committing to one set lowers the expected optimum by approximately Θ(√n); using the median has the same issue.Source: C Naive approaches for Downward-Closed… · p. 19
• A target-beating probability can identify good items when it starts high, since bad items together account for at most a 1/n fraction of that probability.Source: C Naive approaches for Downward-Closed… · p. 19
• Concentration bounds can offset probability loss by lowering the target by O(w · log n) after w selections, but future 1s need not be good items when target-beating probabilities are very low.The lower-bound instance illustrates that a good item may account for most of the probability yet occur with probability much smaller than 1.Source: C Naive approaches for Downward-Closed… · p. 19