1/e Probability for Selecting the Best Pieces in Linear Matroids

Introduction: The “secretary,” but for linear algebra rules

If you’ve ever tried to make smart decisions while new information trickles in—without being able to undo earlier choices—you already understand the vibe of the matroid secretary problem. Elements show up in a random order, you see each one’s weight and (in some models) its structure, and you must instantly accept or reject it while keeping what you’ve accepted independent. The goal is to capture as much value as possible compared to an all-knowing optimum.

Now the cool part: a recent research paper settles a long-standing question for a big family of problems. Based on new research from the original paper, Bérczi, Dughmi, Livanos, Soto, and Verdugo prove that the optimal (1/e)-style probability guarantee—best possible even in the classic secretary problem—can be achieved for linear matroids. In particular, they show a strong secretary guarantee: each element of a fixed optimal basis is selected with probability at least (1/e), not just “in expectation overall.”

This isn’t just a tweak. The paper proves the result under two different information settings, including a notably realistic one: when a linear representation over a finite field is revealed online, one vector at a time. That means you don’t know the matroid’s dependencies in advance—you learn them gradually, as the vectors arrive.

Why This Matters: Near-optimal “best-item coverage” under hard constraints

This result is significant right now because it pushes a boundary that matters across algorithmic decision-making: Do you really need to settle for “good on average,” or can you guarantee that every truly important component has a provable chance to get picked? The strong secretary conjecture answers that question affirmatively for linear matroids.

Why the timing feels meaningful: modern systems often live in “online” modes. Think of streaming features, incremental allocations, or dynamically discovered constraints. You don’t always get to see the full structure upfront. This paper addresses exactly that by handling the online representation model, where the algorithm learns the vectors (and thus the linear dependencies) as elements arrive.

A concrete scenario where this could apply today: imagine you’re building an adaptive selection system over an environment where “feasibility” means something like linear independence (e.g., ensuring selected observations provide genuinely new information rather than redundant combinations). If each candidate arrives with a quality score and a feature vector in a known coordinate system (over a finite field—common in coding/communication abstractions), you need an online method that maintains independence while trying to “cover” the true optimal set. A guarantee like “each element of an optimal basis is picked with probability ≥ (1/e)” is exactly the kind of robust coverage property that’s useful for downstream reliability—especially when later steps depend on whether specific key components were selected.

And how does it compare to previous AI research? In a broad sense, this contributes to the same meta-problem many AI-adjacent systems face: learning under uncertainty with irrevocable actions. But unlike most ML work that focuses on regret or average performance, this is about fine-grained probability guarantees. It’s closer in spirit to rigorous worst-case online optimization than to heuristic policy learning. In fact, the paper builds on earlier secretary work and LP-driven algorithm design in a way that’s very “engineering-friendly”: probability assignments are carefully engineered to satisfy structural constraints.

The matroid secretary problem: selecting value without breaking independence

At heart, the matroid secretary problem generalizes the classic secretary problem. Instead of selecting just one element, you select a set that must be independent in some matroid.

Here’s the basic online setup (same across models):
- You have a ground set of elements (E).
- Each element (e) has a nonnegative weight (w(e)).
- Elements arrive in uniformly random order.
- When an element arrives, you immediately decide whether to accept it.
- You must keep the accepted set independent.
- Your performance is compared to the value of an optimal independent set (in matroids, optimal sets are tied to maximum-weight bases).

A common simplification in the paper is assuming weights are distinct, so the optimum basis is unique on any prefix set (Y \subseteq E). Then “strong secretary” doesn’t just ask for a good expected total weight—it asks for a probability guarantee for each element in an optimal basis.

To make that precise: a strong secretary style algorithm is probability-competitive in the sense that, for each element (e) in a chosen optimal basis, the probability (e) gets selected is bounded below by a constant fraction of the classic best-case probability.

In the classic secretary problem (rank one), the optimal probability guarantee is (1/e). The strong secretary conjecture asked whether something similarly strong holds for every matroid.

What “linear matroid” changes—and why it’s the sweet spot

A matroid is called linear if its independence structure comes from vectors. Concretely, there’s a field (\mathbb{F}) and a representation ({ve : e \in E}) such that:
- A set (I \subseteq E) is independent iff the corresponding vectors ({ve : e \in I}) are linearly independent over (\mathbb{F}).

This representation viewpoint matters because many algorithms get easier when dependencies have a geometry. Instead of abstract independence tests, you reason about spans and subspaces.

And this paper leverages linear geometry in a careful way: their algorithm doesn’t merely accept elements greedily. It controls how the accepted vectors “grow” the span over time—using subspace dimension bounds to preserve probability guarantees.

The two online models: known matroid vs online representation

One reason the paper is compelling is that it proves the (1/e) guarantee in two distinct “information worlds.”

Comparison of the information models

The online-representation model is especially close to “realistic streaming structure.” You don’t know the dependencies ahead of time, but every element comes with enough information to update the span you’ve built so far.

The authors emphasize that their result works for linear matroids both:
1) when the whole matroid is known, and
2) when only the vector representation is gradually revealed.

And they also note that, in the known-matroid model, the result extends further to a broader class: matroids admitting a finitary modular extension (more on that later).

The algorithmic heart: sample-and-probability, tuned by span constraints

The classic secretary algorithm has a familiar shape:
- pick a sample of first (k) elements and reject them,
- then from the remaining elements, accept an element if it seems like the “best so far.”

For rank one, the probability that the best element gets selected with the right timing works out to an optimal (1/e) guarantee.

For linear matroids, “best so far” becomes “improving relative to the optimal basis of the prefix.” The paper generalizes the conditional acceptance probability target:

The target acceptance probability (matroid version)

Let (X) be the set of first (i) arriving elements, and let (e) be an element that is in the optimal basis of (X).
If (e) arrives last among those (i) elements, the algorithm aims to accept (e) with probability:
[
\frac{k}{i-1}.
]
(And the paper arranges (k) around (n/e) so that when you average over possible arrival positions, the final probability for each optimal-basis element reaches at least (1/e).)

But here comes the subtlety: in a matroid, accepting (e) affects future feasibility through the span of accepted vectors. You can’t just set a simple probability rule independent of history.

So their main algorithmic trick is to maintain a controlled distribution over the current accepted span, and then assign acceptance probabilities in a way that:
- preserves independence,
- and keeps a specific “dimension invariant” upper bound valid for every relevant subspace.

Independence and “keeping the span under control”

When an element arrives, accepting it means adding its vector to the accepted set—so independence requires that the vector is not in the current span.

The paper explicitly builds acceptance probabilities that become zero when the arriving element would be a linear dependency (i.e., when accepting it would violate independence).

But there’s more: even when an element is “improving” (meaning it belongs to the optimal basis of the current prefix), you still need to accept it with the right probability without breaking the global dimension constraints.

The dimension invariant inequality: a subspace bookkeeping system

This is where the proof becomes genuinely matroid-geometry-flavored.

The algorithm maintains some auxiliary state so that, after processing a set (X), the span (\langle ALG\rangle) of accepted vectors is distributed in a controlled way. In particular, for every subspace (L), they require an inequality bounding:
- how much of (L) is already covered by the accepted span.

Intuitively, think of (L) as a “direction set,” and (\langle ALG\rangle) as the directions you’ve already locked in. The inequality ensures you don’t over-cover some directions too early, because that would reduce your ability to accept the right elements later.

This invariant is preserved by carefully choosing acceptance probabilities, which the authors compute by solving a (large) linear program at each step of their recursive distribution construction.

Why linear programs show up

The acceptance probabilities must satisfy several competing requirements simultaneously:
1) valid probability bounds (([0,1])),
2) zero probability for non-improving elements,
3) independence preservation (don’t accept vectors already in the span),
4) expected acceptance behavior matching the target (\frac{k}{i-1}),
5) and the dimension invariant constraints for all subspaces.

So the algorithm reduces to feasibility of an LP whose structure depends on subspaces/subspace ranks. The paper’s main technical challenge is proving that this LP is always feasible—i.e., that there always exists a set of acceptance probabilities that simultaneously satisfies all these constraints.

Proving feasibility: uncrossing via supermodularity and chains of subspaces

To prove the LP is feasible, the authors don’t just brute-force it. They use a classic technique from combinatorial optimization: reduce many constraints to a structured subset.

The key idea is that the constraints can be organized using:
- duality (turning “feasibility” into “no violating solution exists”),
- uncrossing (transforming an optimal violating configuration into something more structured),
- and a supermodularity argument that shows the worst constraints can be assumed to line up in a chain.

What “chain of subspaces” means

Instead of considering all pairs of subspaces in arbitrary relationships, the proof can reduce to cases where subspaces are nested:
[
L1 \subseteq L2 \subseteq \cdots \subseteq L_s.
]
Once you’re in a chain, the authors provide an explicit greedy construction of acceptance probabilities that meets the needed bounds.

This is the part of the proof that’s most “magic-looking” at first: the algorithm’s existence hinges on being able to show the constraints can always be satisfied along such a chain, thanks to how the relevant function behaves under intersections and joins.

How the (1/e) guarantee actually drops out

After all the structural work, the final guarantee is pleasingly clean.

They choose sample size:
[
k = \left\lfloor \frac{n}{e} \right\rfloor,
]
and run the sample-and-accept style policy.

Then they focus on a fixed element (e) belonging to a fixed optimal basis (\operatorname{OPT}(E)). For any arrival position (i>k), condition on the event that:
- (e) arrives in position (i),
- and among the first (i) elements, (e) is the last one.

In that conditional world, the algorithm’s LP-based design ensures that the probability of accepting (e) is exactly the target:
[
\frac{k}{i-1}.
]

Because the arrival position of (e) is uniform, they sum/average over positions and use monotonicity/analytic bounds to show:
- the resulting probability is at least (1/e).

So the strong secretary conjecture is resolved for linear matroids in both the online-representation and known-matroid settings—settling the constant probability lower bound for each element of the optimal basis, not just the expected total weight.

Beyond linear matroids: modular extensions that still behave nicely

One more noteworthy feature: in the known-matroid model, the result extends beyond strictly linear matroids.

The paper shows the argument works for matroids that admit a finitary modular extension. In such an extension, flats satisfy modular rank identities, which let the proof swap:
- vector spans → closures,
- dimensions → ranks,
- while keeping the necessary invariants and supermodularity properties intact.

They even discuss which known matroids are covered:
- fully modular extendable matroids include cases beyond linear ones (including some rank-3 or skew-representable component structures),
- but there are also exclusions (e.g., the rank-4 Vámos matroid is not skew-representable and doesn’t admit the needed extension).

Key Takeaways

• Strong secretary solved for linear matroids: the paper proves a probability guarantee matching the classic optimum: each element of a fixed optimal basis is selected with probability ≥ (1/e).
• Two settings covered:
  • known-matroid (only weights online)
  • online-representation (vectors revealed online over a finite field).
• Sample size is tuned to (n/e): they choose (k=\lfloor n/e\rfloor) to make the arrival-position averaging line up with the (1/e) bound.
• The proof uses geometry through subspaces: the algorithm maintains distributions over accepted vector spans and preserves a dimension invariant across all subspaces.
• LP-feasibility is the core technical step: acceptance probabilities are computed by solving a feasibility LP, and feasibility is proven using uncrossing/supermodularity to reduce to chains of subspaces.
• The result goes further than linear matroids in known-matroid: it extends to matroids with finitary modular extensions, not just those with linear representations.

If you want to read the formal statement and technical construction directly, the starting point is the paper here: https://arxiv.org/abs/2609.20797.