The Strong Secretary Conjecture is True for Linear Matroids

arXiv:2609.20797 · cs.DS · Submitted 2026-09-17 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "The Strong Secretary Conjecture is True for Linear Matroids".

Jane: Here's the gist of the paper. The paper proves that a constant fraction of the optimal weight can be guaranteed in the matroid secretary problem for linear matroids by establishing a 1/e guarantee under both known-matroid and online-representation models The result holds both when the matroid is known in advance and when a linear representation over a finite field is given online Each element of a fixed optimal basis is selected with probability at least 1/e.

Tom: The Core Result The central finding is the proof of a 1/e guarantee for the matroid secretary problem on linear matroids.

Jane: This result is established in two models: the known-matroid model and the online-representation model.

Tom: In the known-matroid model, where the entire matroid is known before arrival, an algorithm can select each element of a fixed optimal basis with probability at least 1/e.

Title and authors: Tom: So, as we wrap up this discussion on "The Strong Secretary Conjecture is True for Linear Matroids," we should quickly look at who wrote this. The paper is by Kristóf Bérczi, Shaddin Dughmi, Vasilis Livanos, and José A. Soto.

Jane: They are deep in the world of matroid theory and secretary problems, which means they’re experts on these kinds of combinatorial structures that deal with independence and selection rules.

Lu: What's notable about the authors is their work connecting these concepts to online mechanisms, which is exactly where this paper focuses its attention.

Meng: I don't see any specific industry experience listed for them, so I’m curious if they’ve actually built production systems using this kind of online selection logic.

Lalam: The authors are clearly pushing the boundaries in how we handle uncertainty when the structure itself is revealed over time, which is a hard problem to solve generally.

Tom: It's about proving a strong conjecture for linear matroids, which is significant because it’s a large class of problems we often deal with in data science.

Jane: The title itself suggests that they are settling this conjecture for the class of linear matroids, meaning they are giving a definitive answer to that question within their mathematical framework.

Lu: They aren't just proving it for one specific type of matroid; they are showing the result extends to broader classes, which is what makes the paper have real theoretical weight.

Meng: If this proof doesn't translate easily into an efficient algorithm, then it’s great math but useless in a real-world sense. What about efficiency?

Lalam: The work focuses on proving that a specific type of guarantee, the one over e probability-competitiveness, is achievable through an ordinal approach <ref:2609.20797#pg1>.

Tom: An ordinal approach suggests a sequence of decisions based on partial information, which is very relevant for streaming data scenarios where you only see what has arrived so far.

Jane: That sounds like it’s designed to work even when the full picture isn't available at the start. It’s about making good choices with incomplete information.

Lu: The authors are using tools like Rado's theorem, which is a classic in matroid theory, to find finite-field representations of matroids where they might not exist otherwise.

Meng: Finding a representation is one thing; keeping the algorithm running efficiently while that representation is being revealed sequentially sounds like the real test.

Lalam: The paper addresses this by using an online mechanism where the algorithm learns the representation vector by vector as elements arrive, which keeps things moving.

Tom: So they’re not just proving a static property about a matroid; they’re showing how to solve the problem sequentially as data streams in.

Jane: That sequential learning aspect is what makes this paper relevant to modern machine learning pipelines that deal with continuous data feeds.

The paper's summary: Tom: To summarize "The Strong Secretary Conjecture is True for Linear Matroids," the main point is they proved a one over e guarantee for linear matroids in two different settings <ref:2609.20797#pg1,The Strong Secretary Conjecture is True for Linear Matroids>.

Jane: That guarantee means that even when you don't know the matroid beforehand, you can still ensure you pick a set whose total weight is at least one over e times the optimal weight <ref:2609.20797#pg1>.

Lu: The paper establishes this under two conditions: first when the entire matroid is known in advance, and second when a representation over a finite field is revealed online.

Meng: So we have one scenario where we know everything upfront, and another where things are happening dynamically as they happen. That’s a huge difference in terms of how you design your system.

Lalam: In the known-matroid model, it extends more generally to matroids that admit a finitary modular extension, which means it covers a wider family of structures than just simple linear ones.

Tom: So if you have any matroid that fits that description, this result applies to you as well. It’s not just for the simplest examples.

Jane: The core finding is that each element of a fixed optimal basis can be selected with a probability of at least one over e in the known-matroid model <ref:2609.20797#pg1,each element of a fixed optimal basis>.

Lu: And in the online representation model, they show an ordinal algorithm always selects an independent set with a probability of at least one over e for every element in the optimal set OPT(E) <ref:2609.20797#pg1>.

Meng: That sounds like they’ve cracked a tough problem about how to maintain performance under uncertainty. That's what I care about when we think about real deployment.

Lalam: This guarantee implies that the expected weight of the selected set is at least w(OPT(E)) divided by e in the online model.

Tom: So, if you’re running a system where you have an online representation, that paper tells you exactly how much performance loss to expect compared to the best possible outcome.

Jane: It sets a high bar for what we can achieve in these kinds of selection scenarios when information is revealed incrementally and imperfectly.

The paper's improvements: Tom: Now, let's talk about how this work improves on previous research, because the authors are building on earlier results like Babaioff et al.

Lu: They improve upon previous bounds which were in the omega(one/ r) expected-weight guarantee by moving to a omega(one/ sqrt r) guarantee, and then later to omega(one/ r) <ref:2609.20797#pg1>.

Meng: Those are improvements on the expected weight guarantees, but this paper is about probability-competitiveness, which requires a much stricter condition—a guarantee for *each* element of the optimum.

Lalam: The strong Matroid Secretary Conjecture asks if that one over e guarantee can be achieved under this stricter criterion for every matroid, and this paper answers yes <ref:2609.20797#pg1>.

Tom: So they are moving from just getting a good average weight to guaranteeing performance for every single element in the optimal set, which is a much stronger statement.

Jane: That shift in requirement is what makes the result so powerful; it moves from an expected value guarantee to a probability-competitiveness guarantee.

Lu: The paper addresses this by using tools like Rado's theorem to find finite-field representations of matroids where they might not exist otherwise.

Meng: Finding those representations seems like the crucial step that unlocks the stronger performance guarantees, so without a representation, it’s just theoretical math for now.

Lalam: The authors show that they can achieve this using an ordinal algorithm, which means their selection strategy is built on a sequence of choices rather than a single guess.

Tom: That sounds like a very controlled way to handle the uncertainty; it’s not throwing pure randomness at the problem; it's guiding the process step by step.

Jane: It means that even when you don't know everything about the matroid, you can use that structure to make decisions sequentially that are guaranteed to be good relative to each other.

Conclusion: Tom: So, wrapping up this discussion on "The Strong Secretary Conjecture is True for Linear Matroids," the key takeaway is that they’ve shown a one over e guarantee holds in both known and online settings for linear matroids <ref:2609.20797#pg1,The Strong Secretary Conjecture is True for Linear Matroids>.

Jane: This means we have a high-performance selection strategy even when you’t dealing with structures that are revealed incrementally.

Lu: The paper provides tools, like the feasibility of the linear program via the Dimension Invariant Inequality, to construct these algorithms reliably.

Meng: For deployment, it confirms that if you can manage the representation step, you can achieve a reliable performance metric under streaming conditions.

Lalam: The ordinal algorithm they developed ensures that for every element in the optimal set, there’s a selection probability of at least one over e <ref:2609.20797#pg1>.

Tom: It's a solid theoretical result that settles this conjecture for linear matroids and gives us concrete bounds on performance.

Jane: We have to remember that this applies specifically to linear matroids, so we shouldn't assume the same guarantees apply to general combinatorial structures without checking that condition first.

Lu: The structure of finitary modular extensions provides a nice extension, showing how these results can be generalized further.

Meng: For me, it’s good to see a concrete result that isn't just some abstract bound; it has actual mathematical machinery behind the numbers.

Lalam: I'm just confident that the paper proves what it claims about the probability of selecting each element of the optimum being at least one over e <ref:2609.20797#pg1>.

Tom: That's exactly what we need to hear when we’re trying to understand how selection algorithms perform in complex environments.

Jane: It’s a big step forward for understanding the limits of what we can guarantee in these secretary problems, and it opens up new avenues for research into online decision-making.

Kristóf Bຕzi, Shaddin Dughmi, Vasilis Livanos, José A. Soto, Victor Verdugo

Eötvös Loránd University · University of Southern California · Universidad de Chile · Pontificia Universidad Catolica de Chile

cs.DS

Submitted: 2026-09-17

Updated: 2026-11-05

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 90/100

The gist: The paper proves that a constant fraction of the optimal weight can be guaranteed in the matroid secretary problem for linear matroids by establishing a 1/e guarantee under both known-matroid and…

Key concepts

Matroid Secretary Problem
This problem involves selecting items from a set (like elements in a matroid) sequentially as they arrive, trying to maximize the total weight of the selected items. The goal is to find an algorithm that performs well even when the selection process is adaptive.
Known-Matroid Model
In this model, the entire structure of the matroid—all its elements and dependencies—is known completely before any selections are made. The paper shows that under this full knowledge, a 1/e guarantee for selecting optimal basis elements is achievable.
Online Representation Model
This scenario occurs when the matroid's structure is revealed piece by piece, typically through its representation over a finite field. The algorithm must make selection decisions based only on the information available at that moment, requiring an ordinal strategy.
Linear Program (LP) Feasibility
The core of the proof involves solving a large linear program to determine optimal acceptance probabilities for selecting elements. The paper proves this LP is feasible by relating it to chains of subspaces and using duality and uncrossing techniques.

Terminology

Summary

The paper proves that a constant fraction of the optimal weight can be guaranteed in the matroid secretary problem for linear matroids by establishing a 1/e guarantee under both known-matroid and online-representation models The result holds both when the matroid is known in advance and when a linear representation over a finite field is given online Each element of a fixed optimal basis is selected with probability at least 1/e. p. 0

Where the paper says it

Soto d Victor Verdugo e September 17th, 2026 Abstract We prove a 1/e guarantee for the matroid secretary problem on linear matroids, therefore settling the strong secretary conjecture in this class of matroids. The result holds both when the matroid is known in advance and when a linear representation over a finite field is given online.

The Core Result

The central finding is the proof of a 1/e guarantee for the matroid secretary problem on linear matroids. This result is established in two models: the known-matroid model and the online-representation model. p. 0

Where the paper says it

The result holds both when the matroid is known in advance and when a linear representation over a finite field is given online. In the known-matroid model, the result extends more generally to matroids admitting a finitary modular extension.

In the known-matroid model, where the entire matroid is known before arrival, an algorithm can select each element of a fixed optimal basis with probability at least 1/e. p. 0
Where the paper says it

In the known-matroid model, the result extends more generally to matroids admitting a finitary modular extension. Each element of a fixed optimal basis is selected with probability at least 1/e.

For linear matroids in this model, the result extends to those admitting a finitary modular extension. p. 0
Where the paper says it

The result holds both when the matroid is known in advance and when a linear representation over a finite field is given online. In the known-matroid model, the result extends more generally to matroids admitting a finitary modular extension.

Online Representation Model

In the online-representation model, where a representation of the matroid over a finite field is revealed online, an ordinal algorithm is shown to always select an independent set with probability at least 1/e for every element of OPT(E). This guarantee implies that the expected weight of the selected set is at least w(OPT(E))/e. p. 1

Where the paper says it

For nonnegative weights, this implies an expected weight of at least c times w(OPT(E)). In the classical secretary problem, which corresponds to a rank-one matroid, the optimal probability guarantee is 1/e.

The algorithm maintains auxiliary information, specifically a distribution µY supported on the subspaces of ⟨Y⟩, which is defined recursively. p. 3
Where the paper says it

In addition to its state, our algorithm maintains some auxiliary information for every set Y ⊆ X. Specifically, it stores a distribution µY supported on the subspaces of ⟨Y ⟩, which is defined recursively.

Algorithm Construction and Feasibility

The algorithm relies on solving a large linear program (LP) to determine acceptance probabilities pY(e, W). The feasibility of this LP is established by reducing it to chains of subspaces using duality and uncrossing techniques. p. 1

Where the paper says it

The above requirements placed on acceptance probabilities lead to a large linear program (LP), and the main technical step in our proof is to establish its feasibility. Duality and uncrossing reduce the feasibility argument to chains of subspaces, for each of which we give an explicit feasible solution.

Lemma 1 relates the feasibility of the LP to the Dimension Invariant Inequality (1). p. 5
Where the paper says it

Define gp(L) := −(i − k) dim(L) + X e∈Y ue(L) + X e∈Y EW∼µY −e [pY (e, W)∆e(W, L)] . (3) The following lemma relates gp(L) to the Dimension Invariant Inequality for a subspace L under the distribution µY .

The proof of Lemma 3 demonstrates that this construction yields a well-defined algorithm where all entries are rational. p. 8
Where the paper says it

By our fixed choice rule, pX has rational entries, and (2) then implies that µX has rational entries. Thus, pX and µX are well-defined, and (v) holds.

Generalization to Known Matroids

The result extends to known matroids that are restrictions of finitary modular matroids. Corollary 1 states that in the known-matroid model, every linear matroid admits an ordinal 1/e-probability-competitive algorithm. p. 2

Where the paper says it

Singla [38] recently resolved the original Matroid Secretary Conjecture: he gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary Conjecture remains open.

This is achieved by using Rado's theorem to find a finite-field representation of the matroid.

Extension to Finitary Modular Extensions

The guarantee is extended to matroids admitting a finitary modular extension. Corollary 2 shows that such a matroid admits an ordinal 1/e-probability-competitive algorithm. p. 2

Where the paper says it

Singla [38] recently resolved the original Matroid Secretary Conjecture: he gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary Conjecture remains open.

This extension relies on replacing vector spans with closures in the extension M' and using modular rank identities. The final step shows that the required distribution over deterministic ordinal policies can be recovered from the known matroid M.

AI Disclosure

The proof relied on a conversation with ChatGPT-6 Astra which identified the supermodularity of gp and proposed the uncrossing argument used to prove the feasibility of the LP. The resulting proof was initially drafted with assistance from ChatGPT-6 Astra. p. 0

Where the paper says it

Each element of a fixed optimal basis is selected with probability at least 1/e. Concurrent Discovery Disclosure: The proof of the main result in this manuscript was obtained in a conversation with ChatGPT-6 Astra on Tuesday, September 15, 2026 at 1:02 AM PDT.

The formulation of acceptance probabilities through a linear program was motivated by Buchbinder et al. p. 1
Where the paper says it

The probability is over both the preceding arrival order and the internal randomness of the algorithm. The above requirements placed on acceptance probabilities lead to a large linear program (LP), and the main technical step in our proof is to establish its feasibility.

The authors state that the randomized policy constructed from M' provides a feasible distribution with t ≥ 1/e. The resulting algorithm depends only on the known matroid M and has the required probability guarantee. p. 2
Where the paper says it

Singla [38] recently resolved the original Matroid Secretary Conjecture: he gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary Conjecture remains open.

The authors note that the idea of assigning acceptance probabilities equal to k/(i − 1) in a correlated way predates generative AI. p. 6
Where the paper says it

The second restricts acceptance to elements of OPT(Y ) and assigns zero acceptance probability whenever e ∈ W, so that accepting e preserves independence. For each e ∈ OPT(Y ), the third sets the expected value of pY (e, W) over W ∼ µY −e equal to the target value k/(i − 1).

The formulation of these probabilities through a linear program was motivated by the approach of Buchbinder et al. p. 2
Where the paper says it

Linear programming has also been used to design and analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for generalized secretary problems.

While trying to prove the statement for binary matroids, the authors discussed the problem with ChatGPT-6 Astra on September 14–15, 2026. p. 0
Where the paper says it

Each element of a fixed optimal basis is selected with probability at least 1/e. Concurrent Discovery Disclosure: The proof of the main result in this manuscript was obtained in a conversation with ChatGPT-6 Astra on Tuesday, September 15, 2026 at 1:02 AM PDT.

On September 15, 2026 (1:02 AM PDT), Astra identified the supermodularity of gp and proposed the uncrossing argument used to prove the feasibility of the LP. p. 0
Where the paper says it

Each element of a fixed optimal basis is selected with probability at least 1/e. Concurrent Discovery Disclosure: The proof of the main result in this manuscript was obtained in a conversation with ChatGPT-6 Astra on Tuesday, September 15, 2026 at 1:02 AM PDT.

The resulting proof, which forms the basis of Section 3, was initially drafted with assistance from ChatGPT-6 Astra. p. 0
Where the paper says it

Each element of a fixed optimal basis is selected with probability at least 1/e. Concurrent Discovery Disclosure: The proof of the main result in this manuscript was obtained in a conversation with ChatGPT-6 Astra on Tuesday, September 15, 2026 at 1:02 AM PDT.

The argument was subsequently checked in full by the authors, who are responsible for its verification and final presentation. p. 1
Where the paper says it

In particular, no representation need be supplied as part of the input, and the result applies to matroids representable over an arbitrary field. The same argument extends to known matroids that are restrictions of finitary modular matroids, whose lattices of flats satisfy the modular rank identity.

References

[1] H. Abdi, K. Banihashem, M. Hajiaghayi, and D. p. 2

Where the paper says it

A stronger notion is probability-competitiveness, which requires a guarantee for each element of the optimum. Bateni, Hajiaghayi, and Zadimoghaddam [8] obtained an Ω(1/ log2 r) probabilitycompetitive guarantee, and Soto, Turkieltaub, and Verdugo [40] improved it to Ω(1/ log r).

Mittal. On the strong matroid secretary conjecture and beyond, 2026. p. 0
Where the paper says it

The Strong Secretary Conjecture is True for Linear Matroids Kristóf Bérczi a Shaddin Dughmi b Vasilis Livanos c José A. Soto d Victor Verdugo e September 17th, 2026 Abstract We prove a 1/e guarantee for the matroid secretary problem on linear matroids, therefore settling the strong secretary conjecture in this class of matroids.

[3] M. Babaioff, M. p. 0

Where the paper says it

We are sharing our manuscript nonetheless in case our exposition is of independent utility to the community, and we hope this experience stimulates broader discussion about concurrent discovery in the AI era. 1 Introduction The Matroid Secretary Problem, introduced by Babaioff, Immorlica, and Kleinberg [5], extends the classical secretary problem from selecting a single element to selecting an independent set of a matroid.

Dinitz, A. Gupta, N. Immorlica, and K. p. 0
Where the paper says it

We are sharing our manuscript nonetheless in case our exposition is of independent utility to the community, and we hope this experience stimulates broader discussion about concurrent discovery in the AI era. 1 Introduction The Matroid Secretary Problem, introduced by Babaioff, Immorlica, and Kleinberg [5], extends the classical secretary problem from selecting a single element to selecting an independent set of a matroid.

Talwar. Secretary problems: Weights and discounts. p. 2
Where the paper says it

Linear programming has also been used to design and analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for generalized secretary problems.

[4] M. Babaioff, N. p. 0

Where the paper says it

We are sharing our manuscript nonetheless in case our exposition is of independent utility to the community, and we hope this experience stimulates broader discussion about concurrent discovery in the AI era. 1 Introduction The Matroid Secretary Problem, introduced by Babaioff, Immorlica, and Kleinberg [5], extends the classical secretary problem from selecting a single element to selecting an independent set of a matroid.

p. 0
Where the paper says it

We are sharing our manuscript nonetheless in case our exposition is of independent utility to the community, and we hope this experience stimulates broader discussion about concurrent discovery in the AI era. 1 Introduction The Matroid Secretary Problem, introduced by Babaioff, Immorlica, and Kleinberg [5], extends the classical secretary problem from selecting a single element to selecting an independent set of a matroid.

Immorlica, D. p. 0
Where the paper says it

We are sharing our manuscript nonetheless in case our exposition is of independent utility to the community, and we hope this experience stimulates broader discussion about concurrent discovery in the AI era. 1 Introduction The Matroid Secretary Problem, introduced by Babaioff, Immorlica, and Kleinberg [5], extends the classical secretary problem from selecting a single element to selecting an independent set of a matroid.

Kempe, and R. p. 1
Where the paper says it

Kleinberg [31] studied the multiple-choice secretary problem, in which up to k elements may be selected. Later, Babaioff, Immorlica, and Kleinberg [5] introduced the Matroid Secretary Problem; see also the journal version with Kempe [4].

Kleinberg. Matroid secretary problems. p. 2
Where the paper says it

Related LP formulations have since been used in secretary problems with advice and in sample-driven optimal stopping [14, 21]. Matroid information model.

[5] M. Babaioff, N. Immorlica, and R. p. 0

Where the paper says it

We are sharing our manuscript nonetheless in case our exposition is of independent utility to the community, and we hope this experience stimulates broader discussion about concurrent discovery in the AI era. 1 Introduction The Matroid Secretary Problem, introduced by Babaioff, Immorlica, and Kleinberg [5], extends the classical secretary problem from selecting a single element to selecting an independent set of a matroid.

Kleinberg. Matroids, secretary problems, and online mechanisms. p. 0
Where the paper says it

Soto d Victor Verdugo e September 17th, 2026 Abstract We prove a 1/e guarantee for the matroid secretary problem on linear matroids, therefore settling the strong secretary conjecture in this class of matroids. The result holds both when the matroid is known in advance and when a linear representation over a finite field is given online.

[11] N. Buchbinder, K. p. 2

Where the paper says it

Linear programming has also been used to design and analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for generalized secretary problems.

Jain, and M. p. 2
Where the paper says it

Linear programming has also been used to design and analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for generalized secretary problems.

Singh. Secretary problems via linear programming. p. 2
Where the paper says it

Linear programming has also been used to design and analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for generalized secretary problems.

[36] R. Rado. Note on independence functions. p. 2

Where the paper says it

The information available about the matroid gives rise to two standard variants [16,26]. In the known-matroid model, the ground set and the entire independence structure are available before the arrival process, and only the weights are revealed online.

p. 2
Where the paper says it

The information available about the matroid gives rise to two standard variants [16,26]. In the known-matroid model, the ground set and the entire independence structure are available before the arrival process, and only the weights are revealed online.

[40] J. A. Soto, A. Turkieltaub, and V. p. 2

Where the paper says it

A stronger notion is probability-competitiveness, which requires a guarantee for each element of the optimum. Bateni, Hajiaghayi, and Zadimoghaddam [8] obtained an Ω(1/ log2 r) probabilitycompetitive guarantee, and Soto, Turkieltaub, and Verdugo [40] improved it to Ω(1/ log r).

p. 2
Where the paper says it

A stronger notion is probability-competitiveness, which requires a guarantee for each element of the optimum. Bateni, Hajiaghayi, and Zadimoghaddam [8] obtained an Ω(1/ log2 r) probabilitycompetitive guarantee, and Soto, Turkieltaub, and Verdugo [40] improved it to Ω(1/ log r).

Verdugo. Strong algorithms for the ordinal matroid secretary problem. p. 2
Where the paper says it

Singla [38] recently resolved the original Matroid Secretary Conjecture: he gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary Conjecture remains open.

p. 2
Where the paper says it

Singla [38] recently resolved the original Matroid Secretary Conjecture: he gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary Conjecture remains open.

[16] A. Cristi, P. Dütting, R. p. 2

Where the paper says it

For example, the 1/e guarantee of Kesselheim, Radke, Tönnis, and Vöcking [30] for transversal matroids uses this bipartite representation. Similarly, the strongest previous guarantees for graphic matroids use the graph representation [7, 10], whereas Dütting, Paes Leme, Pál, and Patel [22] recently obtained a 1/36 utility-competitive guarantee using only independence queries on arrived elements.

Kleinberg, R. p. 0
Where the paper says it

We are sharing our manuscript nonetheless in case our exposition is of independent utility to the community, and we hope this experience stimulates broader discussion about concurrent discovery in the AI era. 1 Introduction The Matroid Secretary Problem, introduced by Babaioff, Immorlica, and Kleinberg [5], extends the classical secretary problem from selecting a single element to selecting an independent set of a matroid.

Paes Leme, and N. p. 2
Where the paper says it

For example, the 1/e guarantee of Kesselheim, Radke, Tönnis, and Vöcking [30] for transversal matroids uses this bipartite representation. Similarly, the strongest previous guarantees for graphic matroids use the graph representation [7, 10], whereas Dütting, Paes Leme, Pál, and Patel [22] recently obtained a 1/36 utility-competitive guarantee using only independence queries on arrived elements.

Patel. Online Matroid Embeddings. p. 3
Where the paper says it

Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings, which map a matroid revealed online into a larger known matroid. They constructed embeddings for binary and laminar matroids and obtained reductions from unknown to known matroids with an arbitrarily small loss in the expected-weight guarantee.

[17] N. B. Dimitrov and C. G. Plaxton. Competitive weighted matching in transversal matroids. p. 2

Where the paper says it

For example, the 1/e guarantee of Kesselheim, Radke, Tönnis, and Vöcking [30] for transversal matroids uses this bipartite representation. Similarly, the strongest previous guarantees for graphic matroids use the graph representation [7, 10], whereas Dütting, Paes Leme, Pál, and Patel [22] recently obtained a 1/36 utility-competitive guarantee using only independence queries on arrived elements.

[38] S. Singla. The matroid secretary conjecture is true, 2026. p. 0

Where the paper says it

The Strong Secretary Conjecture is True for Linear Matroids Kristóf Bérczi a Shaddin Dughmi b Vasilis Livanos c José A. Soto d Victor Verdugo e September 17th, 2026 Abstract We prove a 1/e guarantee for the matroid secretary problem on linear matroids, therefore settling the strong secretary conjecture in this class of matroids.

[41] J. A. Soto, A. Turkieltaub, and V. Verdugo. Strong algorithms for the ordinal matroid secretary problem.

[43] Kesselheim, K. p. 2

Where the paper says it

This additional information has been important in obtaining constant guarantees. For example, the 1/e guarantee of Kesselheim, Radke, Tönnis, and Vöcking [30] for transversal matroids uses this bipartite representation.

Radke, A. Tönnis, and B. p. 2
Where the paper says it

This additional information has been important in obtaining constant guarantees. For example, the 1/e guarantee of Kesselheim, Radke, Tönnis, and Vöcking [30] for transversal matroids uses this bipartite representation.

Vöcking. An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. p. 1
Where the paper says it

We prove that the optimal 1/e guarantee is achievable in the online-representation model, in which a representation of the matroid over a finite field is revealed online. The algorithm knows the number of elements and the underlying finite field in advance, but not the representation.

[46] Rado. Note on independence functions.

[48] Matroid secretary problem in the random-assignment model. p. 3

Where the paper says it

Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which elements are inspected.

[49] Strong algorithms for the ordinal matroid secretary problem. p. 2

Where the paper says it

Singla [38] recently resolved the original Matroid Secretary Conjecture: he gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary Conjecture remains open.

[51] Online Matroid Embeddings. p. 3

Where the paper says it

Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings, which map a matroid revealed online into a larger known matroid. They constructed embeddings for binary and laminar matroids and obtained reductions from unknown to known matroids with an arbitrarily small loss in the expected-weight guarantee.

[53] Secretary problems via linear programming. p. 2

Where the paper says it

Linear programming has also been used to design and analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for generalized secretary problems.

[54] Matroid secretary problem in the random-assignment model. p. 3

Where the paper says it

Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which elements are inspected.

[55] Strong algorithms for the ordinal matroid secretary problem. p. 2

Where the paper says it

Singla [38] recently resolved the original Matroid Secretary Conjecture: he gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary Conjecture remains open.

[56] Online Matroid Embeddings. p. 3

Where the paper says it

Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings, which map a matroid revealed online into a larger known matroid. They constructed embeddings for binary and laminar matroids and obtained reductions from unknown to known matroids with an arbitrarily small loss in the expected-weight guarantee.

[58] Secretary problems via linear programming. p. 2

Where the paper says it

Linear programming has also been used to design and analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for generalized secretary problems.

[61] Matroid secretary problem in the random-assignment model. p. 3

Where the paper says it

Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which elements are inspected.

[63] Strong algorithms for the ordinal matroid secretary problem. p. 2

Where the paper says it

Singla [38] recently resolved the original Matroid Secretary Conjecture: he gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary Conjecture remains open.

[64] Online Matroid Embeddings. p. 3

Where the paper says it

Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings, which map a matroid revealed online into a larger known matroid. They constructed embeddings for binary and laminar matroids and obtained reductions from unknown to known matroids with an arbitrarily small loss in the expected-weight guarantee.

[65] Secretary problems via linear programming. p. 2

Where the paper says it

Linear programming has also been used to design and analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for generalized secretary problems.

[68] Matroid secretary problem in the random-assignment model. p. 3

Where the paper says it

Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which elements are inspected.

[69] Strong algorithms for the ordinal matroid secretary problem. p. 2

Where the paper says it

Singla [38] recently resolved the original Matroid Secretary Conjecture: he gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary Conjecture remains open.

[71] Online Matroid Embeddings. p. 3

Where the paper says it

Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings, which map a matroid revealed online into a larger known matroid. They constructed embeddings for binary and laminar matroids and obtained reductions from unknown to known matroids with an arbitrarily small loss in the expected-weight guarantee.

[73] Secretary problems via linear programming. p. 2

Where the paper says it

Linear programming has also been used to design and analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for generalized secretary problems.

[81] Matroid secretary problem in the random-assignment model. p. 3

Where the paper says it

Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which elements are inspected.

[83] Strong algorithms for the ordinal matroid secretary problem. p. 2

Where the paper says it

Singla [38] recently resolved the original Matroid Secretary Conjecture: he gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary Conjecture remains open.

[84] Online Matroid Embeddings. p. 3

Where the paper says it

Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings, which map a matroid revealed online into a larger known matroid. They constructed embeddings for binary and laminar matroids and obtained reductions from unknown to known matroids with an arbitrarily small loss in the expected-weight guarantee.

[85] Secretary problems via linear programming. p. 2

Where the paper says it

Linear programming has also been used to design and analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for generalized secretary problems.

[86] Matroid secretary problem in the random-assignment model. p. 3

Where the paper says it

Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which elements are inspected.

[87] Strong algorithms for the ordinal matroid secretary problem. p. 2

Where the paper says it

Singla [38] recently resolved the original Matroid Secretary Conjecture: he gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary Conjecture remains open.

[88] Online Matroid Embeddings. p. 3

Where the paper says it

Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings, which map a matroid revealed online into a larger known matroid. They constructed embeddings for binary and laminar matroids and obtained reductions from unknown to known matroids with an arbitrarily small loss in the expected-weight guarantee.

[89] Secretary problems via linear programming. p. 2

Where the paper says it

Linear programming has also been used to design and analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for generalized secretary problems.

[115] Online Matroid Embeddings. p. 3

Where the paper says it

Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings, which map a matroid revealed online into a larger known matroid. They constructed embeddings for binary and laminar matroids and obtained reductions from unknown to known matroids with an arbitrarily small loss in the expected-weight guarantee.

[133] Secretary problems via linear programming. p. 2

Where the paper says it

Linear programming has also been used to design and analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for generalized secretary problems.

[135] Matroid secretary problem in the random-assignment model. p. 3

Where the paper says it

Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which elements are inspected.

[138] Strong algorithms for the ordinal matroid secretary problem. p. 2

Where the paper says it

Singla [38] recently resolved the original Matroid Secretary Conjecture: he gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary Conjecture remains open.

[141] Online Matroid Embeddings. p. 3

Where the paper says it

Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings, which map a matroid revealed online into a larger known matroid. They constructed embeddings for binary and laminar matroids and obtained reductions from unknown to known matroids with an arbitrarily small loss in the expected-weight guarantee.

[143] Secretary problems via linear programming. p. 2

Where the paper says it

Linear programming has also been used to design and analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for generalized secretary problems.

p. 2
Where the paper says it

Linear programming has also been used to design and analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for generalized secretary problems.

[145] Matroid secretary problem in the random-assignment model. p. 3

Where the paper says it

Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which elements are inspected.

p. 3
Where the paper says it

Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which elements are inspected.

[148] Strong algorithms for the ordinal matroid secretary problem. p. 2

Where the paper says it

Singla [38] recently resolved the original Matroid Secretary Conjecture: he gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary Conjecture remains open.

p. 2
Where the paper says it

Singla [38] recently resolved the original Matroid Secretary Conjecture: he gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary Conjecture remains open.

[153] Online Matroid Embeddings. p. 3

Where the paper says it

Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings, which map a matroid revealed online into a larger known matroid. They constructed embeddings for binary and laminar matroids and obtained reductions from unknown to known matroids with an arbitrarily small loss in the expected-weight guarantee.

p. 3
Where the paper says it

Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings, which map a matroid revealed online into a larger known matroid. They constructed embeddings for binary and laminar matroids and obtained reductions from unknown to known matroids with an arbitrarily small loss in the expected-weight guarantee.

[154] Secretary problems via linear programming. p. 2

Where the paper says it

Linear programming has also been used to design and analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for generalized secretary problems.

p. 2
Where the paper says it

Linear programming has also been used to design and analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for generalized secretary problems.

[155] Matroid secretary problem in the random-assignment model. p. 3

Where the paper says it

Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which elements are inspected.

p. 3
Where the paper says it

Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which elements are inspected.

[158] Strong algorithms for the ordinal matroid secretary problem. p. 2

Where the paper says it

Singla [38] recently resolved the original Matroid Secretary Conjecture: he gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary Conjecture remains open.

p. 2
Where the paper says it

Singla [38] recently resolved the original Matroid Secretary Conjecture: he gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary Conjecture remains open.

[163] Online Matroid Embeddings. p. 3

Where the paper says it

Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings, which map a matroid revealed online into a larger known matroid. They constructed embeddings for binary and laminar matroids and obtained reductions from unknown to known matroids with an arbitrarily small loss in the expected-weight guarantee.

p. 3
Where the paper says it

Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings, which map a matroid revealed online into a larger known matroid. They constructed embeddings for binary and laminar matroids and obtained reductions from unknown to known matroids with an arbitrarily small loss in the expected-weight guarantee.

[165] Secretary problems via linear programming. p. 2

Where the paper says it

Linear programming has also been used to design and analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for generalized secretary problems.

p. 2
Where the paper says it

Linear programming has also been used to design and analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for generalized secretary problems.

[168] Matroid secretary problem in the random-assignment model. p. 3

Where the paper says it

Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which elements are inspected.

p. 3
Where the paper says it

Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which elements are inspected.

[183] Strong algorithms for the ordinal matroid secretary problem. p. 2

Where the paper says it

Singla [38] recently resolved the original Matroid Secretary Conjecture: he gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary Conjecture remains open.

p. 2
Where the paper says it

Singla [38] recently resolved the original Matroid Secretary Conjecture: he gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary Conjecture remains open.

[185] Online Matroid Embeddings. p. 3

Where the paper says it

Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings, which map a matroid revealed online into a larger known matroid. They constructed embeddings for binary and laminar matroids and obtained reductions from unknown to known matroids with an arbitrarily small loss in the expected-weight guarantee.

p. 3
Where the paper says it

Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings, which map a matroid revealed online into a larger known matroid. They constructed embeddings for binary and laminar matroids and obtained reductions from unknown to known matroids with an arbitrarily small loss in the expected-weight guarantee.

[186] Secretary problems via linear programming. p. 2

Where the paper says it

Linear programming has also been used to design and analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for generalized secretary problems.

p. 2
Where the paper says it

Linear programming has also been used to design and analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for generalized secretary problems.

[188] Matroid secretary problem in the random-assignment model. p. 3

Where the paper says it

Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which elements are inspected.

p. 3
Where the paper says it

Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which elements are inspected.

[189] Strong algorithms for the ordinal matroid secretary problem. p. 2

Where the paper says it

Singla [38] recently resolved the original Matroid Secretary Conjecture: he gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary Conjecture remains open.

p. 2
Where the paper says it

Singla [38] recently resolved the original Matroid Secretary Conjecture: he gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary Conjecture remains open.

[143] Secretary problems via linear programming.

[145] Matroid secretary problem in the random-assignment model.

[148] Strong algorithms for the ordinal matroid secretary problem.

[153] Online Matroid Embeddings.

[154] Secretary problems via linear programming.

[155] Matroid secretary problem in the random-assignment model.

[158] Strong algorithms for the ordinal matroid secretary problem.

[163] Online Matroid Embeddings.

[165] Secretary problems via linear programming.

[168] Matroid secretary problem in the random-assignment model.

[183] Strong algorithms for the ordinal matroid secretary problem.

[185] Online Matroid Embeddings.

[186] Secretary problems via linear programming.

[188] Matroid secretary problem in the random-assignment model.

[189] Strong algorithms for the ordinal matroid secretary problem.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improved AI systems can be equipped with an ordinal online algorithm that always selects an independent set ALG satisfying P [e in ALG] >= 1/e for every e in OPT(E) when a linear representation over a finite field is revealed online.

  2. AI systems operating in the known-matroid model can achieve a 1/e guarantee by computing a finite-field representation of any representable matroid, even if it is not initially given, and then applying the online algorithm described in Theorem 1.

  3. For matroids admitting a finitary modular extension, AI systems can be equipped with an ordinal 1/e-probability-competitive algorithm by using the structure of flats and rank identities derived from the extension M'.

  4. The system can use a fixed chain construction to find acceptance probabilities p in LP(X) such that gp(L), which ensures that the Dimension Invariant Inequality holds for every subspace L.

  5. The system can solve a finite linear program LP(Y) to determine acceptance probabilities pY, where the feasibility of this LP is guaranteed if the distributions µY-e satisfy the Dimension Invariant Inequality (1).

Abstract

We prove a 1/e guarantee for Matroid Secretary on linear matroids: each element of a fixed optimal basis is selected with probability at least 1/e. This settles the strong secretary conjecture for this class of matroids. Our result holds both when the matroid is known in advance and when a linear representation is given online. In the known-matroid model, the result extends to fully modular extendable matroids. We also obtain 1/e guarantees for a more general model on linear matroids, both when the matroid is known and when its representation is revealed online. In XOS Matroid Secretary, agents with XOS valuations over the elements arrive in uniformly random order, and the algorithm must assign each arriving agent a bundle of elements. The bundles must be pairwise disjoint, and their union must be an independent set of the matroid. We obtain an expected total value of at least 1/e times the offline optimum. This model contains Group Matroid Secretary, in which the elements are adversarially partitioned into groups that arrive in uniformly random order, and the algorithm selects a subset of each arriving group. For this special case, we select each element of a fixed optimal basis with probability at least 1/e

Sources

Related papers