Source-linked AI summary
Settling the Matroid Secretary Problem
Zhiyi Huang
TL;DR
The Matroid Secretary Problem asks how to select valuable independent elements arriving in random order when values are unknown in advance. The paper constructs an ordinal online algorithm that matches an auxiliary survival process. It achieves an e-probability-competitive guarantee for general matroids with expected polynomial time and oracle complexity.
Problem
The Matroid Secretary Problem asks for irrevocable online selection of independent elements with unknown nonnegative values, and the general-matroid e-probability-competitive guarantee was the Strong Matroid Secretary Conjecture.
Source: §1 · pp. 1–2Method
Results
Each element of OPT is accepted with probability 1/e, with expected polynomial time and oracle complexity using comparisons and independence queries on arrived elements.
Source: Online Algorithm · p. 8, §5.2 · p. 12Takeaways & Limitations
The Strong Matroid Secretary Conjecture is resolved in its most stringent form for the unknown-matroid model.
Source: §1 · p. 2The auxiliary survival process is not online because survival depends on later arrivals, so the algorithm must implement its distribution online.
Source: §1 · p. 2
Abstract
from arXiv · showhide
This paper settles the Matroid Secretary Problem with an $e$-probability-competitive algorithm. The algorithm is ordinal and accesses arrived elements only through comparison and independence oracles, and has expected polynomial time and oracle complexity.
1 Introduction
The Matroid Secretary Problem asks how to select valuable independent elements arriving in random order when their values are initially unknown. The paper resolves the Strong Matroid Secretary Conjecture with an e-probability-competitive ordinal algorithm, using an auxiliary survival process and an efficient online implementation.
1 Introduction
- The problem assumes nonnegative values unknown in advance and independent uniform arrival times; decisions are immediate and irrevocable, and accepted elements must remain independent.Competitive performance compares expected accepted value with the offline optimum.Source: §1 · p. 1
- Constant-competitive algorithms were known for many matroid families, while the general-matroid guarantee had improved to O(log log r) [20] and.Recent work gave e-probability-competitive algorithms for linear matroids [8] and [1], but the general-matroid result remained open.Source: §1 · pp. 1–2
- An e-probability-competitive ordinal algorithm for the unknown-matroid model has expected polynomial time and oracle complexity.The algorithm accesses arrived elements through comparisons and independence queries.Source: §1 · p. 2
- The auxiliary process keeps elements of the optimum arriving by time p with survival probability ln σ_e / p, where σ_e is when the element leaves the arrived-elements optimum.The process is not online because survival depends on later arrivals.Source: §1 · p. 2
- The online algorithm rejects all elements before p, then probabilistically accepts arrivals joining the current optimum to match the survival process.Its accepted set matches the process distribution, including conditionally at each time t ≥ p given arrivals by t.Source: §1 · p. 2
- A uniformly distributed latent vector couples the online algorithm to the survival process, implementing its acceptance rule without computing the intractable probability ratio directly.This implementation has expected polynomial time and oracle complexity.Source: §1 · p. 2
2 Preliminaries
The preliminaries specify the matroid, order, oracle access, and probability-competitiveness model. They also establish basic rank, closure, and optimal-set properties used later.
Model
- The model uses a finite matroid and a total order; loops may be omitted, and OPT(S) is the optimal independent set restricted to S.OPT is obtained by greedily scanning elements in decreasing order and adding an element when it is not spanned by those already selected.Source: §2 · pp. 2–3
- Elements arrive independently at uniform times, and the algorithm uses independence and comparison oracles on arrived elements to make irrevocable decisions while maintaining independence.It is Γ-probability-competitive when each element of OPT is accepted with probability at least 1/Γ.Source: §2 · p. 3
Matroid Basics
- Rank is the size of a largest independent subset; e is spanned by S when adding it does not increase rank, and cl(S) collects elements spanned by S.Closure is monotone under set inclusion.Source: §2 · p. 3
- Optimality is inherited by subsets: if e is optimal in T and belongs to S ⊆ T, then it is optimal in S.The closure exchange property makes spanning symmetric between e and f relative to S; an element outside cl(T) does not change whether f is spanned by X ⊆ T.Source: §2 · p. 3
3 Auxiliary Survival Processes
The auxiliary survival process assigns each element an arrival time and a survival probability determined by when it becomes spanned. A lemma relating survival distributions under enlarged filtrations supplies the main tool for the online simulation.
3 Auxiliary Survival Processes
- The survival process draws independent uniform arrival times, then lets elements in the early set survive independently according to their spanning times.For threshold p, the survival probability is ln(σ_e/p).Source: §3 · p. 4
- For an element in the optimum at horizon t, the probability of survival is its probability of arriving by p multiplied by its conditional survival probability.The proof identifies these factors as p/t and ln(t/p), respectively.Source: §3 · p. 4
- The main lemma relates the distribution of survivors under a filtration to that under the filtration with an additional element, enabling online simulation.The analysis introduces background filtrations to condition on the arrival of the largest element and proceeds by induction on set size.Source: §3 · pp. 4–5
- Adding elements to a filtration can only make an element spanned earlier; the exchange property also relates the spanning times of two elements when either is added.These spanning-time relations support the comparison of survival distributions in the main lemma.Source: §3 · p. 5
4 Online Algorithm
The online algorithm rejects arrivals before its threshold and then probabilistically accepts elements that join the current optimum. Its accepted set matches the auxiliary survival distribution, yielding the paper’s probability-competitive guarantee.
4 Online Algorithm
- The algorithm rejects arrivals before p, rejects later elements outside the current optimum, and otherwise accepts with a probability chosen to match the survival process.The resulting accepted set is always independent.Source: §4 · p. 7
- Conditional on the elements that have arrived by time t, the accepted set follows the survival-process distribution.The proof matches the two processes’ evolution from their common empty-set condition at t = p.Source: §4 · p. 7, Online Algorithm · p. 8
Online Algorithm.
- With p = 1/e, each element in the offline optimum is accepted with probability 1/e, giving an e-probability-competitive ratio.The conclusion follows from the distributional match at t = 1 and the survival probability in Lemma 3.1.Source: Online Algorithm · p. 8
5 Efficient Implementation
This section implements the acceptance rule using coupled latent-space transports, achieving 1/e acceptance probability for every element in OPT with comparisons and independence queries on arrived elements and expected polynomial time and oracle complexity. It analyzes the recursive-call costs of the forward and reverse kernels and verifies the adjoint identity, survivor preservation, and monotonicity.
5.1 Latent Space for Survival Processes
- A clipped-arrival latent vector sampled uniformly on [0,t]^S maps to the survival-process distribution D_S,t,F.Coordinates above p encode arrival times, while coordinates at or below p are clipped to p and recycled for survival randomness.Source: §5.1 · p. 9
5.2 Efficient Online Algorithm
- For a uniform input, the forward kernel succeeds with probability p σ_e,F and returns a uniform output conditional on success; the coupled kernels preserve survivors and the reverse kernel is monotone.There are at most |S| reverse events while the arrived set is S, and the simulation has expected polynomial time and oracle complexity.Source: §5.2 · pp. 9–12
- The online simulation almost surely maintains the survival-process survivor set, while forward and reverse event transports cancel so the full latent vector remains uniform at every time.The simulation uses successful forward-kernel calls at arrivals and reverse-kernel calls when rejected elements reach their reverse times.Source: §5.2 · pp. 11–12
- With p = 1/e, the final accepted set gives every element in OPT acceptance probability 1/e using only comparisons and independence queries on arrived elements, in expected polynomial time and oracle complexity.The final accepted set follows distribution D_E,1.Source: §5.2 · p. 12
5.3 Proof of Lemma 5.2
- The proof constructs the forward and reverse kernels recursively: failed forward branches discard probability mass, while reverse calls invert scalar maps and reverse the recursive-call order.The construction follows the cases in the proof of Lemma 3.2.Source: §5.3 · pp. 13–14
- Matching successful forward and reverse branches verifies the adjoint identity, survivor preservation, and monotonicity.The recursive calls use corresponding filtrations, preserving the survivor set on S − f and moving remaining coordinates in the same direction.Source: §5.3 · pp. 15–16
- The forward kernel makes at most |S| + 1 expected calls, with at most one expected call per recursion depth; when e and σe,F ≤ 1, reverse calls are at most e(|S| + 1).Source: §5.3 · p. 16
- Each call uses polynomially many comparison and independence queries, while sampling from the density proportional to ρ takes constant expected time.The largest element is found with comparison queries, and σe,F is computed using independence queries at p and release times in F.Source: §5.3 · p. 16
Declaration of AI Usage
The author reports extensive work with ChatGPT Astra, while stating that the author directed the exploration, verified the proofs, and assumes responsibility for the paper.
Declaration of AI Usage
- The author states that they verified the algorithm and proofs and assume full responsibility for the paper’s contents.Source: Declaration of AI Usage · p. 17
- The author directed ChatGPT Astra to explore constructions and made judgment calls about simulating an offline distribution and pursuing a full resolution.Source: Declaration of AI Usage · p. 17
- The author says the work involved extensive interactions with ChatGPT Astra, which produced partial results during the exploration.Source: Declaration of AI Usage · p. 17