PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Strong Matroid Secretary Conjecture and Beyond

Hamed Abdi, Kiarash Banihashem, MohammadTaghi Hajiaghayi, Danny Mittal

arXiv:2609.19118v1cs.DS

TL;DR

The strong matroid secretary conjecture asks whether every matroid admits the rank-one guarantee of 1/e. The paper constructs a linear-matroid secretary algorithm using subspace intersection-dimension bounds and a single-sample prophet algorithm whose output is a fair thinning of an optimum. Linear matroids admit an ordinal secretary algorithm with expected weight at least OPT(w)/e, and every matroid admits a polynomial-time 1/64-competitive ordinal secretary algorithm.

  • Problem

    The strong matroid secretary conjecture asks whether every matroid admits the rank-one guarantee of 1/e.

    Source: §1 · p. 1

  • Method

    The paper constructs a linear-matroid secretary algorithm using subspace intersection-dimension bounds and a single-sample prophet algorithm whose output is a fair thinning of an optimum.

    Source: §1.1 · pp. 3–4, §1.2 · p. 5

  • Results

    Linear matroids admit an ordinal secretary algorithm with expected weight at least OPT(w)/e, and every matroid admits a polynomial-time 1/64-competitive ordinal secretary algorithm.

    Source: §1.1 · pp. 3–4

  • Takeaways & Limitations

    The results establish the conjectured guarantee for linear matroids and a constant ordinal secretary guarantee for arbitrary matroids.

    Source: §1.1 · pp. 3–4

    The single-sample prophet guarantee assumes an arrival order fixed independently of the samples and actual values.

    Source: §2 · p. 6

Abstract

from arXiv · show

The strong matroid secretary conjecture asserts that every matroid admits a $1/e$-competitive secretary algorithm, matching the classical single-choice guarantee. We formulate a finite linear program whose value is the optimal ordinal competitive ratio of any fixed matroid; for all matroids of positive rank on seven elements and nearly all on eight, this value exceeds $1/e$. The same computations suggested that the optimal ratio is monotone under truncation of the matroid; we prove this for uniform matroids, where the ratio is strictly increasing in the rank, and refute it for a graphic matroid. Guided by this evidence, we prove the conjecture for every linear matroid, a class that includes graphic matroids, regular matroids, laminar matroids, and gammoids, giving a $1/e$-competitive ordinal secretary algorithm. The algorithm maintains bounds on the expected intersection dimension of the accepted span with every ambient subspace. Uncrossing and separation show that these bounds can be preserved while admitting each current greedy-basis element with a prescribed probability and the construction uses finite linear programs. For every matroid, we also give a single-sample prophet algorithm with competitive ratio $1/2$ in any fixed arrival order independent of the samples and values. Its output, including the selected values, has exactly the law of an independent fair thinning of an optimum from a fresh product draw. The algorithm uses $O(n^2)$ independence queries on $n$ elements. Both constants are tight in their respective models. We also give a self-contained black-box reduction that converts a single-sample prophet ratio $\alpha$ into a secretary ratio $\alpha^2/16$, preserving polynomial running time. Our single-sample algorithm consequently yields a $1/64$-competitive ordinal secretary algorithm for arbitrary matroids.

1 Introduction

The paper studies whether every matroid admits the rank-one secretary guarantee of 1/e, and develops algorithms that establish this guarantee for linear matroids and a constant ratio for arbitrary matroids. It also gives a finite linear program for fixed-matroid ordinal ratios and a single-sample prophet algorithm.

1.3 Related work

  • Before this work, the best general-matroid guarantee was of order 1/log log r, while the best graphic-matroid guarantee was 1/3.95, approaching 1/e as girth grows.The 1/e guarantee was already known for uniform and transversal matroids.Source: §1 · p. 2

1.1 Our results

  • A finite linear program computes the optimal ordinal ratio for a fixed matroid; computations on all positive-rank seven-element matroids and nearly all eight-element matroids exceeded 1/e.The computations motivated a truncation-monotonicity conjecture, proved for uniform matroids and refuted for a graphic matroid.Source: §1 · p. 2, §1.1 · p. 4
  • Every linear matroid admits a 1/e-competitive ordinal secretary algorithm, while every matroid admits a polynomial-time 1/64-competitive ordinal algorithm.The linear-matroid construction is finite but has no asserted polynomial running-time bound; the general guarantee follows from a reduction from the single-sample prophet algorithm.Source: §1.1 · pp. 3–4
  • The single-sample prophet algorithm achieves a tight 1/2 ratio in every fixed arrival order independent of samples and values, using O(n^2) independence queries.Its output has the law of an independent fair thinning of an optimum from a fresh draw.Source: §1.1 · pp. 3–4

1.2 Techniques

  • The secretary reduction turns any single-sample prophet ratio α into an ordinal secretary ratio α^2/16 while preserving polynomial running time.It uses a half-sample filter, low-probability activations, and an exact interleaving to make the virtual arrival order independent of activations.Source: §1.1 · p. 4, §1.2 · p. 5
  • For linear matroids, the algorithm maintains expected intersection-dimension bounds for every subspace and uses uncrossing and separation to preserve them while admitting candidates.The construction yields enough availability to accept each current greedy-basis candidate with the prescribed probability; the argument relies on averaging over the uniformly random arrival order.Source: §1.2 · pp. 4–5

2 Preliminaries

The preliminaries fix the matroid, weight, greedy-basis, and competitive-ratio notation used in the paper. They also specify the secretary and single-sample prophet models and relate weight-prefix guarantees to weighted competitiveness.

2 Preliminaries

  • The ground set and matroid are known in advance, and greedy scanning in decreasing weight with fixed tie-breaking returns an optimum basis.A guarantee on every weight prefix, E|A ∩ H| ≥ c r(H), implies a weighted c-competitive guarantee by summation by parts.Source: §2 · p. 6
  • In the secretary model, weights are fixed before a uniformly random permutation, and an ordinal policy uses only the revealed relative weight order and the fixed tie rule.A c-competitive policy achieves expected weight at least c times the optimum for every nonnegative weight vector.Source: §2 · p. 6
  • In the single-sample prophet model, independent values and samples are drawn per element, and the order is fixed independently of samples, values, and internal coins.The algorithm does not know the value distributions, and the competitive ratio compares expected selected value with the expected optimum.Source: §2 · p. 6

3 The optimal ordinal ratio as a linear program

The section characterizes the optimal ordinal secretary ratio of a fixed matroid by a finite linear program and reports computations supporting the strong conjecture. It also tests truncation monotonicity, proving it for uniform matroids and refuting it for graphic matroids.

The program

  • For every matroid with a nonloop, the finite program computes the optimal ordinal ratio and attains it with an ordinal policy.Its state records the observed weight order and accepted set; the program encodes flow, independence, and competitiveness constraints.Source: §3 · p. 7

Computations

  • Every tested positive-rank matroid on seven elements and nearly all on eight had optimal ratio above 1/e.The computed ratios also exceeded that of the rank-one matroid on the same number of elements, except for the rank-one matroid itself.Source: §3 · p. 7

Truncation monotonicity

  • For uniform matroids, the optimal ratio is strictly increasing with rank, recovering their known 1/e guarantee.The section also notes that the program's size grows faster than exponentially in the number of elements, though matroid symmetries can reduce it.Source: §3 · pp. 7–8
  • Truncation monotonicity fails for graphic matroids: rank-three truncations can have ratio above 0.53, while arbitrarily large-girth examples approach 1/e.The counterexample shows the conjecture can fail even when algorithms observe numerical weights.Source: §3 · p. 8

4 A tight guarantee for matroid secretary on linear matroids

For linear matroids, the section constructs an ordinal secretary policy by maintaining bounds on expected intersection dimensions of the accepted span with every subspace. Chain admission, uncrossing, and separation establish feasibility; an appropriate cutoff gives the 1/e guarantee.

4.1 The algorithm

  • The algorithm rejects the first s arrivals, then recursively computes laws on independent sets and transition rules from observed relative weight orders.Each current greedy-basis element is admitted with prescribed probability, while the averaged updated law must remain bounded.Source: §4.1 · pp. 8–9

4.6 Choosing the cutoff

  • The policy achieves a 1/e-competitive guarantee for every linear matroid, with each element of the optimal basis selected with the same probability.A suitable finite cutoff attains at least 1/e; the construction uses finite linear programs but has no claimed polynomial running-time bound.Source: §4.1 · p. 9, §4.6 · p. 13, §4.5 · p. 13

4.2 The subspace invariant

  • The invariant bounds the expected dimension of the intersection between the accepted span and every ambient subspace.Constraints only on lines generated by ground vectors are insufficient; the proof also needs constraints on other subspaces.Source: §4 · p. 8, §4.2 · p. 10

4.3 Admitting an element along a chain

  • Along a chain of subspaces, nested expensive-state sets give one ordering for placing admission mass while preserving the load bounds.The chain-admission rule requires β + a ≤ 1 and bounds the updated load by β dim U + a when the new vector lies in U.Source: §4.3 · pp. 10–11
  • Uncrossing replaces incomparable subspaces by their intersection and sum, preserving the dimension budget while increasing every load pointwise.A finite increasing potential ensures the replacement process terminates in a chain.Source: Figure 1 · p. 11, §4.3 · p. 11

4.4 Simultaneous extension

  • A minimax and separation argument combines chain bounds to find one transition rule whose uniform average satisfies all subspace constraints.The guarantee applies to the average over arrival identities, not necessarily to each updated row; independence of the candidate set controls the increase.Source: §4.4 · pp. 11–12

4.5 Analysis of the policy

  • The algorithm's randomized transitions implement the recursively defined laws, and every optimal-basis element is accepted with probability c_n(s).Summing the selected optimal-basis weights yields expected weight at least c_n(s) OPT(w).Source: §4.5 · pp. 12–13

5 A tight single-sample prophet inequality

For arbitrary matroids, the section gives a single-sample prophet algorithm whose output has the law of an independent fair thinning of an optimal basis from a fresh draw. The resulting 1/2 guarantee is tight, and the algorithm uses O(n^2) independence queries.

5.1 Algorithm

  • When an arriving value changes the greedy basis, the algorithm tracks the displaced element and refreshes the stored value vector with a probability determined by that element's status.The stored vector retains the product distribution, and the accepted set stays within its greedy basis.Source: §5 · p. 13, §5.1 · pp. 14–15

5.2 The conditional thinning invariant

  • After each fixed arrival prefix, the stored endpoint vector is uniform, and conditional on it the accepted set is an independent fair thinning of the processed greedy-basis elements.The proof uses independent fair orientations of each sample–actual-value pair, including when the two values coincide.Source: §5.2 · pp. 15–16

5.3 Distributional guarantee and optimality

  • The algorithm's output is distributed as an independent fair thinning of the optimal basis of a fresh product draw, yielding expected value 1/2 of the prophet's.The guarantee is tight, even if an algorithm knows the value distributions and receives extra independent samples.Source: §5 · p. 13, §5.3 · p. 16
  • The online algorithm works in any fixed arrival order independent of samples and values and uses O(n^2) independence queries.It caches the current basis and computes at most one replacement basis per arrival.Source: §5.3 · p. 16

6 Secretary guarantees from samples

Section 6 gives a self-contained reduction from single-sample matroid prophet algorithms to secretary algorithms, preserving polynomial running time. Its construction uses a preliminary sample, rare activations, and an online interleaving to obtain the stated guarantee.

6 Secretary guarantees from samples

  • An α-competitive single-sample prophet algorithm yields an α^2/16-competitive secretary algorithm for arbitrary matroids, with polynomial running time.The prophet algorithm need only handle a uniformly random arrival order independent of samples and values, without knowing the permutation in advance.Source: §6 · p. 16

6.1 A preliminary sample

  • E[OPT(w|T)] is at least OPT(w)/2 while E[w(T)] is at most OPT(w), for the eligible set T formed from a preliminary half-sample.Eligibility excludes elements spanned by the sample elements preceding them in weight and tie-priority order.Source: §6.1 · p. 17

6.2 Rare activations and the loss bound

  • Choosing q = α/4 gives expected reward at least α^2 OPT(w)/16; the preliminary sample keeps the quadratic loss bounded against OPT(w).Without the preliminary sample, the same calculation could charge q^2 against total weight, which may be arbitrarily larger than OPT(w).Source: §6.2 · p. 17

6.3 Exact online simulation

  • The interleaving makes R an independent Bernoulli-q sample and Σ a uniform order independent of R, so the simulated prophet inputs have the required independent product-draw law.The reduction is online, preserves polynomial running time, and its instantiation is ordinal for secretary weights.Source: §6.3 · p. 18
  • With k independent samples per distribution, the reduction gives ratio α^2/(16k) by choosing q = α/(4k).This extension uses the expected prophet guarantee, not a conditional guarantee after fixing endpoint pairs.Source: §6.3 · p. 18

A An exact linear program for ordinal matroid secretary

Appendix A presents an exact linear program for the optimal ordinal secretary ratio of a matroid. It establishes the program’s value and describes objective and symmetry reductions that preserve it.

A An exact linear program for ordinal matroid secretary

  • The appendix gives the full linear program and proves that its optimum is the matroid’s optimal ordinal secretary ratio, including attainment and policy extraction.The computational motivation and comparison with earlier linear-program formulations are in Section 3.Source: A An exact linear program for ordinal… · p. 20
  • The program is first presented uncompressed, with a direct probabilistic meaning for every variable.The section establishes correctness before describing reductions.Source: A An exact linear program for ordinal… · p. 20
  • The appendix distinguishes weighted and per-element objectives and describes symmetry and state reductions that preserve the optimum.Source: A An exact linear program for ordinal… · p. 20

A.1 States and variables

The state variables encode what an ordinal policy can know after a prefix of arrivals: the observed labels, their relative weight order, arrival order, and accepted set. The appendix defines transition variables for the next label and its decision.

A.1 States and variables

  • For an ordinal policy, the observation after t arrivals is the observed set, its relative weight order, and the order in which those elements arrived.The arrival order is uniformly random and independent of the weight order.Source: §A.1 · p. 20
  • For fixed policy, weight order, and t-element set S, the probability that the first t arrivals form S and yield accepted set A depends on the weight order only through its restriction to S.The arrivals within S are uniform over its t! orders, so the policy’s decisions depend only on their arrival order and relative weights.Source: §A.1 · p. 21
  • Each p_σ,A variable represents the joint probability that the first |σ| arrivals form S_σ and the accepted set is A.It includes the probability of the observed set; it is not a conditional probability.Source: §A.1 · p. 21
  • The y_σ,e,A and z_σ,e,A variables record reaching the prefix before e arrives and whether e is accepted or rejected.Different relative weight orders on the same set retain separate state variables; states with dependent accepted sets are omitted.Source: §A.1 · p. 21

A.2 The program

The program’s objective uses linear functions of state and transition variables to represent acceptance probabilities and competitiveness. Its constraints encode arrival flow, independence, state transitions, and the prefix form of the competitive-ratio condition.

A.2 The program

  • For each weight order and element, a linear function of the variables gives the probability that the element is accepted.Its summands represent disjoint observed-set and accepted-set possibilities at the element’s arrival.Source: §A.2 · p. 21
  • Constraint (16b) assigns probability 1/(n − |σ| + 1) to the next arrival being e from state (σ − e, A), then splits that flow between acceptance and rejection.Source: §A.2 · pp. 21–22
  • Constraint (16c) forbids dependent acceptances, while (16d) partitions ways of reaching a state by the last label’s decision.Source: §A.2 · p. 22
  • Constraint (16e) imposes c-competitiveness through every weight-order prefix, which is equivalent to the weighted form for ordinal policies.Source: §A.2 · pp. 21–22
  • The flow constraints imply that the total mass of a state equals the probability that the first |σ| arrivals form S_σ.Source: §A.2 · p. 22

A.3 Correctness

The linear program (16) has optimal value equal to the best ordinal secretary ratio for the matroid. Its feasible solutions correspond to ordinal policies, and an optimal solution yields an optimal policy.

A.3 Correctness

  • The optimal value of program (16) is ρ(M), and an optimal solution yields an optimal ordinal policy.Every feasible solution with objective value c yields a c-competitive policy whose decisions use the current weight order, arriving label, and accepted set.Source: §A.3 · pp. 22–23
  • A c-competitive ordinal policy induces a feasible solution of program (16) with objective value c.The policy's acceptance probabilities define the variables, and its competitiveness supplies the program's prefix constraints.Source: §A.3 · pp. 22–23
  • The policy constructed from a feasible solution accepts an arriving element with probability yσ,e,A/(yσ,e,A + zσ,e,A), taking the probability as zero when the denominator vanishes.The policy accepts only when adding the element preserves independence.Source: §A.3 · p. 22
  • Induction over observed-set size shows that the constructed policy realizes the program's state and transition probabilities, so its prefix constraints guarantee c-competitiveness.The initial state follows from (16a); each next arrival's transitions match y and z, and summing transitions gives the state probabilities.Source: §A.3 · pp. 22–23

A.4 Two objectives

The full weighted competitive ratio and the requirement to select each greedy-basis element with a minimum probability are distinct objectives. On U2,3, their optima are 3/4 and 2/3, respectively.

A.4 Two objectives

  • On U2,3, the full weighted competitive ratio is 3/4, while the per-element probability objective has optimum 2/3.The per-element objective requires each element of the current greedy basis to be selected with probability at least c; the full objective instead imposes prefix constraints.Source: §A.4 · p. 23

A.5 Symmetry and state reductions

Three reductions make the program tractable for larger instances without changing its value: simplifying constraints, exploiting automorphisms, and merging states with identical future independence options. They do not yield a polynomial-size formulation or a uniform bound across matroids.

A.5 Symmetry and state reductions

  • Only rank-increasing prefixes need constraints because nonnegativity makes the constraint for a prefix imply it for an extension of unchanged rank.Source: §A.5 · p. 23
  • Averaging over matroid automorphisms preserves the worst-case guarantee, allowing ordered subsets and weight orders to be reduced to automorphism representatives.Source: §A.5 · p. 23
  • Accepted sets can be merged when their labeled remaining minors coincide, since those states allow exactly the same future decisions.The reductions preserve program value, and past selections remain recorded in the acceptance flows.Source: §A.5 · p. 23
  • These reductions neither produce a polynomial-size formulation nor establish a uniform competitive bound over all matroids.The program is a tool for computing and testing rather than proving the strong conjecture.Source: §A.5 · p. 23

B Ordinal secretary ratios under truncation

The conjecture that optimal ordinal secretary ratios are nondecreasing under rank truncation holds strictly for uniform matroids but fails in general. A graphic-matroid counterexample also refutes the conjecture without an ordinal restriction.

B Ordinal secretary ratios under truncation

B.1 Uniform matroids

The section reduces the uniform-matroid secretary ratio to a top-k selection problem, then proves that its optimum strictly increases with rank. Consequently, every uniform matroid has an ordinal ratio of at least 1/e.

B.1 Uniform matroids

  • The weighted ordinal ratio for Uk,n equals r(n, k), the optimal expected fraction of the top k elements captured.The top-k problem becomes an optimal stopping problem with k slots and posterior probabilities as rewards.Source: §B.1 · p. 24
  • For every n and 2 ≤ k ≤ n, the optimal ordinal ratio is strictly higher at rank k than at rank k − 1.The proof bounds separately the changes in posterior rewards and selection capacity.Source: §B.1 · pp. 25–26
  • Every uniform matroid has an ordinal secretary ratio of at least 1/e, by monotonicity from the rank-one classical secretary problem.The rank-one cutoff rule supplies the 1/e guarantee.Source: §B.1 · p. 26

B.2 A graphic counterexample

A graphic matroid provides a counterexample to monotonicity under truncation: its rank-three truncation has a ratio above 0.53, while the matroid’s ratio is below 0.53. The argument combines a three-choice lower bound with a pairwise single-secretary upper bound.

B.2 A graphic counterexample

  • For the cited graphic matroid, ρ(M(3)) > 53/100 while unrestricted ρ(M) < 53/100; with N=QL=2100 and rank N+1, some k from 4 through N+1 satisfies ρ(M(k)) < ρ(M(k−1)).Source: §B.2 · pp. 26–27
  • A three-choice policy on the rank-three truncation rejects an initial phase, accepts records, then accepts arrivals among the best three observed so far.Its limiting performance is lower-bounded using the eligibility probabilities and the probability that a slot remains.Source: §B.2 · pp. 26–27
  • The upper bound embeds independent two-value single-secretary instances on the edge pairs of K2,N and applies their bound conditionally on the other pairs.A forest can contain both edges of at most one pair, limiting the extra selected edge; the heavier edge from each pair forms a forest.Source: §B.2 · p. 27
Loading 2609.19118v1…