How do you choose before every offer arrives?
- What it is
- A paper claims an online algorithm can choose a strong feasible set even when options appear one by one.
- Who did it
- Hamed Abdi, Kiarash Banihashem, MohammadTaghi Hajiaghayi, and Danny Mittal
- What it could mean
- Choosing now can mean missing the best offer that arrives later. If this holds, it gives a sharp guarantee for making good choices under a specific mathematical kind of constraint—not every real-world marketplace.
See the check plan
Evidence & validation
From announcement to evidence
Discovery recorded. State of Proof has not yet examined this claim.
Read the original work
On the Strong Matroid Secretary Conjecture and Beyond ↗See the proposed checks
Inspect the exact theorem statements and define their arrival-order, value, representation, and oracle assumptions; verify that the linear-matroid 1/e theorem is not conflated with the separate arbitrary-matroid prophet or 1/64 reduction claims. No code needs to be run for this first source review.
No proof docket yet
A docket is the public record of checks and open questions. This paper does not have one yet; the check plan above describes work still to do.
Explore existing proof dockets →
- What it claims
- The abstract claims a 1/e-competitive ordinal secretary algorithm for every linear matroid, maintaining expected-intersection-dimension bounds while selecting online. It separately claims a 1/2 single-sample prophet algorithm for arbitrary matroids and a black-box 1/64 secretary reduction. This is a newly posted, concrete advance on structured online selection, not a blanket result for all allocation problems.
- Why this could matter
- How do you choose before every offer arrives? Hiring, booking, and bidding all share a cruel timing problem: accept too early and a better option may appear; wait too long and nothing remains. This paper claims a sharp online-selection rule for a structured family of feasible choices.
- If it holds up
- Enabling: it would settle the strong secretary guarantee for linear matroids, giving algorithm designers a precise benchmark for online selection under that structure.
- If it does not
- The sharp guarantee or its scope would need revision, revealing which arrival, independence, or representation assumption carries more weight than claimed.
- Impact horizon
- Enabling · Online algorithms · Combinatorial optimization · Decision-making under uncertainty
- Version
- submitted 2026-09-16 17:43:06 UTC
- Why we tracked it
- a fresh, source-backed online-selection theorem with a precise claimed guarantee. Intake is not a verification of the algorithm, its constants, or an application to any operational allocation problem.
- Highest-risk dependency
- A linear-matroid feasible set is not automatically a real capacity, pricing, authority, or lifecycle model. The guarantee's online-information and representation assumptions determine what it says; a claimed 1/e result does not make it an all-purpose offer-selection rule.
- Available artifacts
- arXiv exposes PDF, experimental HTML, and TeX source. The inspected primary record identifies no Lean/Rocq/Coq/Isabelle development, code repository, certificate, or replay package. AI involvement is not established by this source.
- Current boundary
- Intake record only; examination not started.