d908aaa 9fbb795
% ==========================================================================
% One Sample Suffices for Matroid Prophet Inequalities against an
% Almighty Adversary.
%
% A self-contained rewrite. Every definition, lemma and proof is kept, but
% the ideas are explained in plain words along the way so that a careful
% high-school reader can follow the entire argument.
%
% The result: one independent sample per element is enough to beat any
% arrival-order adversary, even one that sees all samples, all online
% values, and the algorithm's whole random seed.
% ==========================================================================
\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[margin=1in]{geometry}
\usepackage{microtype}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{enumitem,booktabs,array}
\usepackage{xcolor}
\definecolor{linkblue}{RGB}{22,64,95}
\usepackage[colorlinks=true,linkcolor=linkblue,citecolor=linkblue,urlcolor=linkblue]{hyperref}
\usepackage[nameinlink,capitalise,noabbrev]{cleveref}
\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\DeclareMathOperator{\cl}{cl}
\DeclareMathOperator{\rk}{r}
\DeclareMathOperator{\OPT}{OPT}
\newcommand{\Ex}{\mathbb E}
\newcommand{\Prob}{\mathbb P}
\newcommand{\ind}[1]{\mathbf 1_{\{#1\}}}
\newcommand{\given}{\,\middle|\,}
\setlist[itemize]{topsep=4pt,itemsep=2pt,parsep=0pt}
\setlist[enumerate]{topsep=4pt,itemsep=3pt,parsep=0pt}
\allowdisplaybreaks[1]
\title{One Sample Suffices for Matroid Prophet Inequalities\\against an Almighty Adversary}
\author{OpenAI}
\date{September 23, 2026}
\begin{document}
\maketitle
\begin{abstract}
One independent sample per element always suffices for a constant-competitive
prophet inequality on every finite matroid. The guarantee survives the
strongest order adversary, one that sees every sample, every online value,
and the algorithm's whole random seed before choosing the order. The rule
never needs the value distributions, and it achieves the absolute
competitive ratio $2^{-310}$.
\end{abstract}
\section{Introduction}\label{sec:intro}
\paragraph{What a prophet inequality is.}
A gambler is shown a finite set $E$ of items (called \emph{labels} or
\emph{elements}) one at a time in some order. Each item $e$ carries a
nonnegative random value $V_e$. When $e$ appears the gambler sees $V_e$
and must decide, on the spot, to keep it or drop it. A keep is final and
cannot be undone. The kept set must stay \emph{feasible}. A \emph{prophet}
who sees every value in advance could keep the best feasible set. A
prophet inequality asks how large a fraction of the prophet's value an
online rule can guarantee without knowing the future.
\paragraph{What feasibility means here.}
Feasibility is described by a known finite \emph{matroid}
$M=(E,\mathcal I)$. Its members $\mathcal I$ are the \emph{independent
sets}. Informally a matroid is any combinatorial rule of independence that
obeys two axioms:
\begin{itemize}
\item if $I\in\mathcal I$ and $J\subseteq I$ then $J\in\mathcal I$
(subsets of independent sets are independent), and
\item if $I,J\in\mathcal I$ and $|I|<|J|$ then some $e\in J\setminus I$
has $I\cup\{e\}\in\mathcal I$ (exchange).
\end{itemize}
Graph edge-sets without cycles, and linearly independent vectors, are the
two examples to keep in mind. For a value vector $v=(v_e:e\in E)$ the best
feasible value is
\begin{equation}\label{eq:OPT}
\OPT_M(v)=\max_{I\in\mathcal I}\sum_{e\in I}v_e .
\end{equation}
\paragraph{The information the rule gets.}
The rule never learns the distributions. Instead, before any arrival it
receives one independent \emph{sample} $S_e$ for every label, each drawn
from the same law $D_e$ as the true online value $V_e$. The pairs
$(S_e,V_e)$ are mutually independent. The rule also uses its own random
seed $R$, drawn independently of all samples and values. The sample vector
$S$ is the only statistical information available.
\paragraph{The adversary.}
The arrival order is chosen by an \emph{almighty ordering adversary}. This
adversary may inspect the matroid, the distributions, the full sample vector
$S$, the full online vector $V$, and the rule's complete seed $R$ before it
picks the order $\pi$. The rule is never told the order in advance. This
is the harshest information pattern: nothing random the rule owns is hidden.
\paragraph{The main theorem.}
\begin{theorem}\label{thm:main}
There is a measurable online selection rule, depending on no distributions,
with the following property. Let $M=(E,\mathcal I)$ be any finite known
labeled matroid, and let $(S_e,V_e:e\in E)$ be mutually independent
nonnegative random variables with $S_e$ and $V_e$ sharing an arbitrary law
$D_e$. Assume $\Ex[\OPT_M(V)]<\infty$. The rule receives exactly the
sample vector $S$ before arrivals and uses a seed $R$ independent of $S,V$.
For every measurable permutation rule $\pi$ that may depend on $M$, the laws
$(D_e)$, $S$, $V$ and $R$, the rule accepts an independent set $A$, decides
irrevocably at each arrival using only the available history, and
\begin{equation}\label{eq:main-bound}
\Ex\!\left[\sum_{e\in A}V_e\right]\ \ge\ 2^{-310}\,\Ex[\OPT_M(V)] .
\end{equation}
\end{theorem}
The constant is absolute: it does not depend on the matroid, its size, its
rank, or the distributions. The rule is a finite measurable construction.
No running-time bound and no polynomial independence-oracle bound are
claimed. The proof actually gives the stronger constant $2^{-293}$; the
statement above carries deliberate slack.
\paragraph{Why a loss is unavoidable, and why the sample helps.}
With no sample at all, a single-choice prophet inequality guarantees only
$1/2$ of the prophet's value even with known distributions, and this is
sharp. With one sample per element the single-choice problem again admits
$1/2$. The point of the present theorem is that the same one-sample
information, made robust against a full-seed order adversary, yields a
positive constant on \emph{every} matroid at once.
\paragraph{The information pattern in words.}
The unusual demand is the expectation of a \emph{minimum}. A guarantee for
each fixed order would only control $\min_\pi \Ex[\text{reward}]$. We must
control $\Ex[\min_\pi \text{reward}]$: the adversary picks a different order
for each seed, so the order can be tuned to the coins. This is why the
proof first builds a rule for a \emph{hidden fixed} value vector, where the
minimum over orders sits inside the expectation, and only afterwards
transfers that guarantee to the one-sample model.
\paragraph{Context.}
For known distributions, a sharp factor of $1/2$ for arbitrary matroids was
proved by Kleinberg and Weinberg \cite{KW12}, following the single-choice
factor-two bound credited to Garling (see Krengel and Sucheston
\cite{KS77}). For unknown distributions, Azar, Kleinberg and Weinberg
\cite{AKW14} introduced the limited-information sample framework and the
reduction from order-oblivious secretary rules. In the single-choice setting
Rubinstein, Wang and Weinberg \cite{RWW20} obtained the optimal one-sample
fraction $1/2$, and Caramanis et al. \cite{CDF22} developed a
greedy-ordered sample-pair method. For general matroids, Lachish
\cite{Lachish14} and Feldman, Svensson and Zenklusen \cite{FSZ15} first
gave one-sample guarantees with a doubly logarithmic loss in the rank.
Fu et al. \cite{FLTWWZ24} then obtained a constant using
$O(\log^4(2+n))$ samples per element, and \cite{FSZ26} improved the
sample dependence. Those constant results allow an almighty adversary,
but with a sample budget that grows with the matroid. The present theorem
uses a single sample. Recent constant results for ordinary random-order
matroid secretary selection are in \cite{Singla26,Huang26}.
\paragraph{Proof strategy in one breath.}
Round the values down to powers of a large base $B$ so there are only a few
``weight levels''. Process levels from low to high. For each level, a
sparse mask of revealed samples builds \emph{flats} (matroid-closed sets)
that capture many high-value samples per unit of rank; a second sparse mask
of revealed samples adds \emph{guards} that protect those captures one step
ahead. Slice these nested flats into two-step \emph{layers}, and within each
layer greedily keep arriving labels that are independent of everything kept
so far. Nesting makes the union feasible for \emph{every} arrival order.
Three independent losses are then bounded: competition from lower levels
(Section~\ref{sec:safety}), the fact that revealed samples are sacrificed
(Section~\ref{sec:transfer}), and the gap between the model path and the
final guarded path (Section~\ref{sec:accounting}). A simple separate branch
handles the case where one label dominates the optimum. A final coupling
carries the fixed-vector guarantee to the one-sample model.
\section{A fixed-vector formulation}\label{sec:setup}
Throughout, $M=(E,\mathcal I)$ is a finite labeled matroid. For a set
$X\subseteq E$, its \emph{rank} $\rk(X)$ is the size of a largest independent
subset of $X$, and its \emph{closure} is
$\cl(X)=\{e\in E:\rk(X\cup\{e\})=\rk(X)\}$. A set is a \emph{flat} when it
equals its own closure. We say $X$ \emph{spans} $A$ when
$A\subseteq\cl(X)$. Write $L=\cl(\varnothing)$ for the set of \emph{loops}
(elements that are in no independent set), and put
\[
\rk(A\mid P)=\rk(A\cup P)-\rk(P),\qquad
\OPT_M(w)=\max_{I\in\mathcal I}\sum_{e\in I}w_e .
\]
Inside a closure, a rank argument, or a map on flats, a sum of sets means
their union. A set is \emph{independent over $P$} when its conditional rank
over $P$ equals its size. We fix one total order on the labels, used only to
break ties, once and for all.
\paragraph{The hidden-vector game.}
We first solve a cleaner game. The value vector $w$ is a fixed but unknown
nonnegative vector. Before arrivals the rule draws a random mask
$B_0\subseteq E$, independently of $w$, and is told $w$ on $B_0$. It must
reject every label of $B_0$ (those samples are \emph{sacrificed}). On every
other label it learns $w_e$ only when that label arrives. The mask may
depend on the whole seed $R$. Let $A(w,R,\pi)$ be the accepted set under
order $\pi$.
\begin{proposition}\label{prop:hidden}
There is a measurable rule for the hidden-vector game that is feasible for
every realization and every order and, for every
$w\in[0,\infty)^E$, satisfies
\begin{equation}\label{eq:hidden-guarantee}
\Ex_R\!\left[\min_{\pi}\sum_{e\in A(w,R,\pi)}w_e\right]
\ \ge\ 2^{-293}\,\OPT_M(w).
\end{equation}
Its revealed mask is chosen before any weight is seen.
\end{proposition}
The minimum in \eqref{eq:hidden-guarantee} is \emph{inside} the expectation.
So the adversary may choose a different order for every seed. Everything
below is for a fixed $M,w$, which we suppress inside conditional
expectations. The next lemma is the only bridge to Theorem~\ref{thm:main}.
\begin{lemma}[One-sample simulation]\label{lem:simulation}
A measurable hidden-vector rule satisfying \eqref{eq:hidden-guarantee} gives
a measurable one-sample rule with the same competitive ratio against the
adversary of Theorem~\ref{thm:main}.
\end{lemma}
\begin{proof}
Draw the rule's seed independently of $S,V$. For the analysis, glue the two
copies together:
\[
w^{\mathrm{glue}}_e=
\begin{cases}S_e,&e\in B_0(R),\\ V_e,&e\notin B_0(R).\end{cases}
\]
Given the seed, the choice of which copy supplies each label is fixed, and
the mutual independence with matching laws gives
$\mathcal L(w^{\mathrm{glue}}\mid R)=\bigotimes_e D_e$, the law of $V$.
Hence $w^{\mathrm{glue}}$ is independent of the seed.
Run the hidden-vector rule with $S_e$ on its revealed mask and $V_e$
elsewhere, ignoring unused samples and rejecting revealed labels without
looking at their online values. Induction on arrivals shows that, for
every fixed $S,V,R$ and every order, this execution accepts exactly
$A(w^{\mathrm{glue}},R,\pi)$, and each accepted weight is its true online
value. So for any adversarial order, even one using all unused samples and
values, the reward is at least
$\min_{\pi'}\sum_{e\in A(w^{\mathrm{glue}},R,\pi')}w^{\mathrm{glue}}_e$.
Integrate \eqref{eq:hidden-guarantee} using independence of the glued vector
and seed. Nonnegative integration needs no moment hypothesis beyond the
reported one, and feasibility caps the reward by $\OPT_M(V)$, whose
expectation is finite.
\end{proof}
\subsection{Elementary matroid facts}\label{sec:matroid-facts}
We use only rank and closure, so nothing below needs representability. The
independent sets contain $\varnothing$, are closed under subsets, and satisfy
exchange. Exchange implies that all maximal independent subsets of a set
have the same size and that independent sets extend to bases of larger sets.
Rank is \emph{submodular}:
\begin{equation}\label{eq:rank-submodular}
\rk(A)+\rk(B)\ \ge\ \rk(A\cup B)+\rk(A\cap B).
\end{equation}
Indeed, take a basis of $A\cap B$, extend it to a basis of $A$, then to a
basis of $A\cup B$ using elements of $B\setminus A$. The initial basis
together with those last elements is independent inside $B$, which gives the
inequality. Two consequences we will use constantly:
\begin{itemize}
\item $\rk(Z\mid P)$ can only decrease as $P$ grows;
\item closure is increasing and idempotent, and adjoining already-spanned
elements changes neither rank nor closure.
\end{itemize}
Finally, scanning any set $Z$ and greedily keeping the elements that raise
rank over a fixed base $P$ selects an independent set over $P$ of size
$\rk(Z\mid P)$ that spans all of $Z$ over $P$.
\section{Constructing the hidden-vector rule}\label{sec:algorithm}
We build the rule of Proposition~\ref{prop:hidden} for a fixed hidden vector
$w$. It rounds values to geometric levels and flips a fair coin between two
sub-rules. The \emph{maximum} branch handles the case where one label
dominates the optimum. The \emph{main} branch filters arrivals against
revealed samples and sorts them into layers of nested flats built from those
samples; greedy independent sets from different layers then combine feasibly.
\subsection{Constants, rounding, and the maximum branch}
Fix the constants
\begin{equation}\label{eq:constants}
B=2^{32},\qquad \kappa=2^{100},\qquad t=2^{-140},\qquad
\eta=2^{-12},\qquad \gamma=\eta/16=2^{-16}.
\end{equation}
Here $B$ separates weight levels, $\kappa$ is the rank charge in the density
expansions, $t$ is the common sparsity of the guard and eligibility masks,
and the exit cutoff $\eta$ yields the sample-to-rank coefficient $\gamma$.
The sizes leave room for every loss combined in Section~\ref{sec:accounting}.
For $w_e>0$ round down,
$u_e=B^{\lfloor\log_B w_e\rfloor}$, and put $u_e=0$ when $w_e=0$. Write
$u(Z)=\sum_{e\in Z}u_e$ and $W=\OPT_M(u)$. Coordinates are rounded when
their weight is revealed or arrives; the full vector $u$ is for analysis
only. Rounding gives
\begin{equation}\label{eq:rounding}
\OPT_M(w)/B\ \le\ W\ \le\ \OPT_M(w).
\end{equation}
Higher rounded weight means higher priority, ties broken by the fixed label
order. Running priority greedy over all positive labels keeps an
independent set $I^*$ of $u$-weight $W$: its intersection with every initial
segment of weight levels has full rank there, so adding up the gains of
successive levels proves optimality.
Let $m_*$ be the largest rounded weight of a positive nonloop, or $0$ if
there is none. The \emph{maximum rule} reveals a fair independent mask
(rate $1/2$) and accepts the first unmasked positive nonloop of higher
priority than every revealed positive nonloop, then accepts nothing more.
Its guarantee is simple. If there are at least two positive nonloops, then
with probability $1/4$ the top-priority one is unmasked and the second is
masked; on that event only the top one can clear the threshold, so it is
accepted in every order. With one positive nonloop, success has probability
$1/2$. Hence in all cases
\begin{equation}\label{eq:maximum}
\Ex\!\left[\min_\pi u(A_{\mathrm{max}}(R,\pi))\right]\ \ge\ m_*/4.
\end{equation}
Final rule: with probability $1/2$ play the maximum rule and with
probability $1/2$ play the main rule built below. All coins, including
unused branch coins, are drawn initially and independently of $w$.
\subsection{Candidates and weight groups}
The main rule draws mutually independent masks $H,D,C,T$, independently
across labels, with membership probabilities
\begin{center}
\begin{tabular}{@{}ccl@{}}
\toprule
Mask & Probability & Role \\
\midrule
$H$ & $1/2$ & filters candidates by higher-priority span \\
$D$ & $1/4$ & lists weight groups and supplies density data \\
$C$ & $t$ & supplies guards for the flat paths \\
$T$ & $t$ & thins online eligibility independently of the paths \\
\bottomrule
\end{tabular}
\end{center}
Reveal and sacrifice the weights on $H\cup D\cup C$. By
Lemma~\ref{lem:simulation} these revealed weights are sample coordinates.
Being in $T$ alone reveals nothing and forces no rejection. For each $e$
let $H_{>e}$ be the labels of $H$ of higher priority than $e$, and define a
candidate set together with a comparison independent set
\begin{equation}\label{eq:candidates}
U=\{e\notin H:u_e>0,\ e\notin\cl(H_{>e})\},\qquad Y=I^*\setminus H.
\end{equation}
Only $U$ matters for analysis; the candidate test is computable as soon as
the weight of $e$ is known.
\begin{lemma}[Candidate mass]\label{lem:filter}
$Y$ is independent, $Y\subseteq U$, and
\begin{equation}\label{eq:candidate-mass}
\Ex_H u(Y)=W/2,\qquad \Ex_H u(U)\le W .
\end{equation}
\end{lemma}
\begin{proof}
For $e\in I^*$ no higher-priority labels span $e$, so neither do the
higher-priority labels of $H$; thus $Y\subseteq U$, and the fair mask gives
the first identity. Condition on all higher-priority memberships of $H$.
Then $\{e\notin\cl(H_{>e})\}$ is fixed, and its contribution to $u(U)$ has
the same expectation as the event that $e\in H$ and $e$ is chosen by
priority greedy on $H$. Summing over positive labels, the expected greedy
value on $H$ is at most $W$.
\end{proof}
Conditional on $H$, the \emph{true weight groups} are
\[
U_i=\{e\in U:u_e=B^i\},\quad n_i=|U_i|,\quad Y_i=Y\cap U_i
\qquad(i\in\mathbb Z),
\]
empty ones omitted. A group is \emph{listed} when $D\cap U_i\ne\varnothing$.
List the listed groups $G_1,\dots,G_m$ from low to high weight and write
$D_h=D\cap G_h$, $C_h=C\cap G_h$, $T_h=T\cap G_h$. The whole $D_h,C_h$ is
known before arrivals: every label of $D\cup C$ is revealed, and its
candidate test uses only $H$ and its own weight. The algorithm never needs
the full $G_h$ nor the true sizes $n_i$. All candidates are nonloops.
\subsection{Density expansions}
For a listed group $h$ and a flat $P$, let $Q_h(P)$ be the largest flat
maximizing
\begin{equation}\label{eq:density-objective}
f_h(Z)=|D_h\cap Z|-\kappa\rk(Z)\qquad\text{over flats }Z\supseteq P .
\end{equation}
For a nonflat argument take its closure first. The objective rewards the
number of $D_h$ samples spanned and charges $\kappa$ per unit of rank, so
extending the flat and picking up more samples costs rank only at that rate.
This is a contracted, sample-restricted form of the cardinality-minus-rank
maximization behind principal partitions (Santiago, Sergeev and Zenklusen
\cite{SSZ25}); we prove the properties we need directly.
\begin{lemma}[Density expansion]\label{lem:density}
The largest maximizer in \eqref{eq:density-objective} exists, the map $Q_h$
is increasing, $P\subseteq Q_h(P)$, and if $Q=Q_h(P)$ then for every set $Z$
\begin{equation}\label{eq:density-residual}
|D_h\cap(\cl(Q+Z)\setminus Q)|\ \le\ \kappa\,\rk(Z\mid Q).
\end{equation}
\end{lemma}
\begin{proof}
The function $f_h$ is supermodular on the lattice of flats: the counting
term is supermodular under intersection and closed union, and the rank term
is supermodular by \eqref{eq:rank-submodular}. There are finitely many
flats, and the closed union of two maximizers containing $P$ is again a
maximizer, so a largest maximizer exists.
For $P\subseteq P'$, put $Q=Q_h(P)$, $Q'=Q_h(P')$. The flats $Q\cap Q'$
and $\cl(Q\cup Q')$ are feasible at $P$ and at $P'$ respectively. Optimality
gives one inequality, supermodularity the reverse:
\[
f_h(Q\cap Q')+f_h(\cl(Q\cup Q'))
\ \le\ f_h(Q)+f_h(Q')\ \le\ f_h(Q\cap Q')+f_h(\cl(Q\cup Q')).
\]
Equality forces $\cl(Q\cup Q')$ to be a maximizer at $P'$, and the largest
maximizer there contains $Q$. Finally, the flat $\cl(Q+Z)$ is feasible in
\eqref{eq:density-objective}; the rank gap between it and $Q$ is $\rk(Z\mid
Q)$, which yields \eqref{eq:density-residual}.
\end{proof}
\subsection{Nominal and guarded paths}
An integer $k$ is an \emph{auxiliary time}, unrelated to arrival time. Set
$F_0(k)=L$ for $k<0$ and $F_0(k)=E$ for $k\ge0$. For a listed group put
$a_h=-3h$ and define an enabled expansion
\[
Q_{h,k}(P)=\begin{cases}Q_h(P),&k\ge a_h,\\ P,&k<a_h,\end{cases}
\qquad(P\text{ a flat}).
\]
In increasing group order form the \emph{nominal} and \emph{guarded} paths
\begin{equation}\label{eq:paths}
X_h(k)=Q_{h,k}(F_{h-1}(k)),\qquad
F_h(k)=\cl\!\bigl(X_h(k)+(C_h\cap X_h(k+1))\bigr).
\end{equation}
So a guard ($C$-sample) is added one auxiliary step before it would enter the
nominal path. Each density map uses only $D_h$ and the known matroid; each
guard set uses only the revealed $C_h$. Hence every $X_h(k)$ and $F_h(k)$ is
a computable subset of $E$ before arrivals, even though some of its labels'
weights stay unknown.
\begin{lemma}[Path properties]\label{lem:paths}
The paths increase in $k$ and satisfy
\begin{equation}\label{eq:path-inclusions}
F_{h-1}(k)\subseteq X_h(k)\subseteq F_h(k)\subseteq X_h(k+1).
\end{equation}
They equal $E$ for $k\ge0$. Moreover $X_h(k)=L$ for $k<a_h$ and
$F_h(k)=L$ for $k<a_h-1$. For a nonloop $e$ the nominal birth
$b_h(e)=\min\{k:e\in X_h(k)\}$ is either $a_h$, with $e\in Q_h(L)$, or lies
in $[a_h+2,0]$.
\end{lemma}
\begin{proof}
Induct on $h$. The map $Q_{h,k}$ is increasing in its argument and in $k$,
because enabling it swaps the identity for an extensive increasing map.
Thus $X_h$ and then $F_h$ increase. The first two inclusions in
\eqref{eq:path-inclusions} are extensiveness. The last holds because both
sets adjoined in the definition of $F_h(k)$ lie in the flat $X_h(k+1)$.
The same recursion gives $E$ once $k\ge0$.
For $h>1$ we have $a_{h-1}=a_h+3$, and induction makes $F_{h-1}(k)=L$ for
$k<a_h+2$; for $h=1$ it holds directly from $F_0$. Before $a_h$ the new map
is the identity, giving the lower bounds on $X_h$ and $F_h$. At $a_h$ and
$a_h+1$ the nominal flat is the same $Q_h(L)$, so no nonloop is born at
$a_h+1$. Since $X_h(a_h)=Q_h(L)$, a nonloop born at $a_h$ lies in $Q_h(L)$,
and every other birth is at least $a_h+2$.
\end{proof}
\subsection{The online decisions}
Draw an independent fair parity $\varepsilon\in\{0,1\}$ and set
$\widehat F(k)=F_m(k)$. If $m=0$ use $\widehat F=F_0$ and reject everything.
Otherwise the \emph{layer endpoints} are the integers
$b\equiv\varepsilon\pmod2$, and layer $(b-2,b]$ has \emph{base}
$\widehat F(b-2)$. The rule keeps, in each layer, a set
$A_b\subseteq\widehat F(b)$ independent over $\widehat F(b-2)$. Since
consecutive layers share an endpoint, everything kept in an earlier layer
lies in the base of every later layer. At the arrival of $e$:
\begin{enumerate}
\item Reject if $e\in H\cup D\cup C$, if its candidate test fails, or if its
rounded weight is not listed.
\item For its listed group $h$ compute $b=b_h(e)$. Reject unless
\begin{equation}\label{eq:eligibility}
e\in T,\quad b\ge a_h+2,\quad b\equiv\varepsilon\ (\mathrm{mod}\ 2),
\quad e\notin\widehat F(b-2).
\end{equation}
\item Let $A_b$ hold the labels already accepted into this layer. Accept $e$
exactly when $\rk(\{e\}\mid\widehat F(b-2)+A_b)=1$, and then add it
to $A_b$.
\end{enumerate}
These steps use only the revealed data, the arriving label and its weight,
the seed, and earlier decisions; no full true group or future arrival is
needed. By Lemma~\ref{lem:paths} the schedule leaves no birth at $a_h+1$,
so excluding the baseline birth $a_h$ keeps exactly those births with
$b-2\ge a_h$, i.e.\ the density map is already enabled at the preceding
layer endpoint.
\begin{lemma}[Feasibility and measurability]\label{lem:feasibility}
The main rule keeps an independent accepted set at every arrival prefix, for
every order, and is a measurable rule using only the allowed information.
\end{lemma}
\begin{proof}
An eligible label at endpoint $b$ lies in $X_h(b)\subseteq\widehat F(b)$, and
its layer's accepted set is independent over $\widehat F(b-2)$. In
increasing auxiliary endpoint order, all earlier accepted layers lie in that
base flat, so adding the current layer keeps the union independent. This
gives independence of the union for any interleaving of arrivals, hence of
every prefix.
All masks are drawn initially and the matroid is known. Each density
maximization ranges over finitely many flats, and by Lemma~\ref{lem:paths}
it suffices to scan a finite interval of auxiliary times for the at most
$|E|$ listed groups. Positive rounding has countably many measurable level
sets, and each realized vector occupies finitely many levels. The rest are
finite rank tests and set comparisons with fixed tie rules, hence measurable.
Zeros never enter a logarithm, and loops fail the candidate test.
\end{proof}
\subsection{A generator budget for the whole path}
We need one bound on how much each density expansion can move the path.
Charging the rank increase separately at each time would bill the same
samples repeatedly; instead choose one generator set for all times. The
same lemma bounds the independent sampled mass lost to the baseline birth.
\begin{lemma}[Generator budget]\label{lem:generators}
For each listed group $h$ there is a set $J_h\subseteq D_h$ and increasing
subsets $J_h(k)\subseteq J_h$ with
\begin{equation}\label{eq:generator-budget}
X_h(k)=\cl\!\bigl(F_{h-1}(k)+J_h(k)\bigr),\qquad
|J_h|\le |D_h|/\kappa .
\end{equation}
In particular $\rk(Q_h(L))\le |D_h|/\kappa$.
\end{lemma}
\begin{proof}
Before $a_h$ no generators are needed. Process enabled times
$k=a_h,a_h+1,\dots,0$ in order. Given the earlier generators set
$P_k=\cl(F_{h-1}(k)+X_h(k-1))$. By monotonicity $P_k\subseteq X_h(k)$, and
$P_k$ is feasible in the maximization defining $X_h(k)$, so
\begin{align*}
\kappa\bigl(\rk(X_h(k))-\rk(P_k)\bigr)
&\le |D_h\cap X_h(k)|-|D_h\cap P_k|\\
&\le |D_h\cap X_h(k)|-|D_h\cap X_h(k-1)|.
\end{align*}
The flat $R_k=\cl(F_{h-1}(k)+(D_h\cap X_h(k)))$ lies in $X_h(k)$ with the
same $D_h$ count; a proper subflat would have smaller rank and improve the
objective, contradiction. Thus $R_k=X_h(k)$, and the extension over $P_k$
has a basis chosen from $D_h\cap X_h(k)$.
Adjoin such a basis to the generators, in the fixed label order. Because
$F_{h-1}$ increases, the earlier generators together with $F_{h-1}(k)$
already generate $P_k$, which proves the first identity inductively. The new
generators are distinct and their counts obey the displayed inequality.
Summing telescopes the $D_h$ counts to $|J_h|\le |D_h|/\kappa$. Extend the
generators constantly for $k>0$. At $k=a_h$ the lower flat is $L$, giving
the last assertion.
\end{proof}
\section{Reverse exposure and safe samples}\label{sec:safety}
The guards serve two purposes: they build the paths, and they protect a
sampled label against lower-weight competition inside its layer. We relate
these by exposing the guard mask \emph{backwards} in auxiliary time. A label
leaves its nominal flat at some step with a decent conditional probability,
and a comparison using the test mask turns the square of that probability
into safety.
Fix $H,D$ and a listed group $h$ throughout; so the groups, their indices,
the density maps, and $Y$ are fixed. Define the lower-weight competition set
\begin{equation}\label{eq:competition-set}
K_{h,b}=\bigcup_{j<h}\bigl(T_j\cap(X_j(b)\setminus X_j(b-1))\bigr).
\end{equation}
It contains every possible eligible lower-weight competitor at endpoint $b$,
and is contained in $F_{h-1}(b)$; including sacrificed labels only enlarges
it. Let $\sigma_h$ count the labels $d\in D_h\cap Y$ whose birth $b$ on
$X_h$ satisfies
\begin{equation}\label{eq:safe-definition}
a_h+2\le b\le0,\qquad b\equiv\varepsilon\ (\mathrm{mod}\ 2),\qquad
d\notin Q_h\bigl(F_{h-1}(b-2)+K_{h,b}\bigr).
\end{equation}
These are analysis quantities the rule never computes. The goal is
Lemma~\ref{lem:safe}: a constant fraction of $D_h\cap Y$ contributes to
$\sigma_h$ in expectation, up to a $|D_h|/\kappa$ loss.
\subsection{The reverse computation and its filtration}
The guard mask was drawn with the initial seed and may be fully known to the
adversary. Reverse exposure analyzes its product law; it adds no online
randomness and hides nothing from the adversary. For $k<0$, a later state
$S=(S_j:j\le h)$ and a guard-bit vector $c$, define a one-step map
\begin{equation}\label{eq:reverse-map}
\begin{aligned}
A_0&=F_0(k),\qquad N_j=Q_{j,k}(A_{j-1}),\\
A_j&=\cl\!\bigl(N_j+\{e\in G_j\cap S_j:c_e=1\}\bigr)\quad(1\le j\le h).
\end{aligned}
\end{equation}
Its output is $(N_j:j\le h)$. The map is increasing in $k$, in each
coordinate of $S$, and in the bits $c$. Starting from $X_j(0)=E$, compute
$X(k)$ at $k=-1,-2,\dots,a_h-1$ by $X(k)=\mathcal G_k(C,X(k+1))$; this is
exactly the defining recursion. For an actual state $S=X(k+1)$ the new
$N_j$ lies in $S_j$ for every choice of $c$: inductively
$A_{j-1}\subseteq S_{j-1}\subseteq F_{j-1}(k+1)$, so
$N_j\subseteq Q_{j,k+1}(F_{j-1}(k+1))=S_j$, and the guard additions also stay
inside $S_j$.
After computing $N_j$, inspect only the bits on $G_j\cap(S_j\setminus N_j)$;
additions inside $N_j$ do not change its closure. Order the labels in each
batch. The batch's domain is fixed before its first query, because $N_j$
uses only previous groups' bits. The groups are disjoint and the domains
shrink each reverse step, so no coordinate is queried twice.
Let $\mathcal H_b$ be the sigma-field of the complete transcript just before
the step from $X(b)$ to $X(b-1)$, including queried labels, their answers,
and the states reached. Thus $\mathcal H_b\subseteq\mathcal H_{b-1}$ as
reverse time advances. Conditional on $\mathcal H_b$, the unqueried bits on
$V_b=\bigcup_{j\le h}(G_j\cap X_j(b))$ are jointly independent Bernoulli of
rate $t$: the unqueried coordinates are exactly these, and each query was
chosen from its prior transcript. So the conditional transition law is
\eqref{eq:reverse-map} with fresh product bits, and the transcript reveals no
test bits, parity, or not-yet-computed small-time flat.
For a fixed nonloop $d$, on $\{d\in X_h(b)\}$ define the predictable exit
probability
\begin{equation}\label{eq:exit-probability}
p_{b-1}=\Prob\bigl(d\notin X_h(b-1)\mid\mathcal H_b\bigr),
\end{equation}
and $p_{b-1}=0$ when $d\notin X_h(b)$. Before exit these probabilities are
nondecreasing along the reverse computation: evaluate each conditional
transition probability with one independent product mask $\xi$ on the whole
union of groups; smaller time and smaller input state give a smaller output
under the same $\xi$, and taking probabilities proves it.
\subsection{Certificates and exit mass}
To bound exits at steps with small $p_{b-1}$ we look at bands of comparable
exit probabilities and show each survival in a band certifies a fixed
increasing event using only that step's fresh positive bits. An increasing
Boolean event is a family $\mathcal A\subseteq2^V$ closed under supersets; a
positive \emph{certificate} for $\mathcal A$ is a set $I\in\mathcal A$
(setting the coordinates of $I$ to one already forces the event).
\begin{lemma}[Disjoint-query certificates]\label{lem:transactions}
Let $V_0$ be finite with independent Bernoulli bits, and let
$\mathcal A\subseteq2^{V_0}$ be increasing with failure probability
$\delta>0$. An adaptive procedure queries each coordinate at most once and
groups queries into transactions; the next query, the boundaries, and any
stopping rule depend only on the transcript and perhaps an independent
auxiliary seed. Suppose the number of transactions is deterministically
bounded. A transaction may be declared successful only if the positive bits
queried within it alone form a certificate for $\mathcal A$. Then
\begin{equation}\label{eq:certificate-budget}
\Ex[\text{number of successful transactions}]\ \le\ \log(1/\delta),
\end{equation}
with $\log$ the natural logarithm.
\end{lemma}
\begin{proof}
Condition on the auxiliary seed. Conditional on any query transcript, all
unqueried bits keep their joint product law; this follows by induction over
the predictably chosen queries.
For a remaining set $V\subseteq V_0$, let $p(V)$ be the failure probability of
$\mathcal A$ when bits on $V$ keep their laws and all others are zero. For
the set $I$ of positive bits already queried in the current transaction, let
$p_I(V)$ be the same with bits on $I$ forced to one. Then
$\delta\le p(V)\le1$, $0\le p_I(V)\le p(V)$, and
$p(V\setminus\{e\})\ge p(V)$. The ratio $Z=p_I(V)/p(V)$ starts each
transaction at one.
A query of $e\in V$ with success probability $q_e$ updates to $V'=V\setminus
\{e\}$ via the one-coordinate identity
$p_I(V)=(1-q_e)p_I(V')+q_e p_{I\cup\{e\}}(V')$, valid conditional on the
current transcript. The denominator $p(V')$ is the same for either answer,
so
\begin{align}
\Ex[Z-Z'\mid\text{transcript}]
&=Z\Bigl(1-\frac{p(V)}{p(V')}\Bigr)
=Z\bigl(1-e^{-(\log p(V')-\log p(V))}\bigr)\notag\\
&\le\log p(V')-\log p(V),
\label{eq:log-resource}
\end{align}
using $0\le Z\le1$ and $1-e^{-x}\le x$.
At a successful transaction's end, the certificate forces $p_I(V)=0$, so
$Z=0$; at any other end $0\le Z\le1$. Thus a success indicator is bounded
by its realized net decrement $1-Z_{\rm end}$. Summing \eqref{eq:log-resource}
over the queries and taking expectations bounds each success probability by
the expected increase of $\log p(V)$. Reset $I$ to empty but keep the
depleted $V$; the logarithmic increments telescope across all transactions
to at most $0-\log p(V_0)=\log(1/\delta)$. Adaptive stopping is covered by
padding with zero increments, since there are finitely many queries and a
bounded number of transactions.
\end{proof}
\begin{lemma}[Exit mass]\label{lem:exit}
Every nonloop $d$ exits its $h$-th nominal path by the end of the reverse
computation, and
\begin{equation}\label{eq:low-exit-hazard}
\Prob(\text{$d$ exits at a step with }p_{b-1}<\eta\mid H,D)<\tfrac12.
\end{equation}
Consequently,
\begin{equation}\label{eq:squared-exit-mass}
\sum_{b=a_h}^{0}\Ex\bigl[\ind{d\in X_h(b)}\,p_{b-1}^{2}\mid H,D\bigr]
\ \ge\ \frac{\eta}{2}.
\end{equation}
\end{lemma}
\begin{proof}
Fix $p_0>0$ and consider steps, before exit, whose exit probability lies in
$[p_0,2p_0)$. By monotonicity they form one block, possibly empty. Its
first step is determined by the pre-step transcript. Condition on a possible
transcript there, with time $k_0$ and input state $S^0$, and on the fresh
bits $V_0=\bigcup_{j\le h}(G_j\cap S^0_j)$ fix the increasing event
$\mathcal A=\{c:d\in(\mathcal G_{k_0}(c,S^0))_h\}$. Its failure probability
satisfies $\delta\ge p_0$.
Treat the queries within each later step of the block as one transaction. If
a step does not exit, its own fresh positive bits alone certify $\mathcal A$:
hold the step's actual input $S$ fixed and let $I$ be only its queried
positives. Evaluating $\mathcal G_k(c^I,S)$ with every other guard bit zero
gives the same output as the actual step, since new $N_j$ are unchanged,
positive additions outside $N_j$ were queried and lie in $I$, and additions
inside $N_j$ are already spanned. Earlier queried coordinates lie outside
the current domains, and $k\le k_0$, $S\subseteq S^0$, so
$\mathcal G_k(c^I,S)\subseteq\mathcal G_{k_0}(c^I,S^0)$. Non-exit thus gives
$I\in\mathcal A$. Lemma~\ref{lem:transactions} bounds the conditional
expected number of non-exit steps in the block by $\log(1/\delta)\le
\log(1/p_0)$; there is at most one exit step. Hence the expected number of
steps in the range is at most $\log(1/p_0)+1$, and summing their exit
probabilities bounds the chance of exit in the range by
$2p_0(\log(1/p_0)+1)$. For $p_0=2^{-(\ell+1)}$, summing over $\ell\ge12$,
\[
\sum_{\ell=12}^{\infty}2^{-\ell}\bigl((\ell+1)\log2+1\bigr)
=2^{-11}(14\log2+1)<\tfrac12.
\]
An exit at probability zero has probability zero, and $X_h(a_h-1)=L$ forces
every nonloop to exit; this proves \eqref{eq:low-exit-hazard}.
The exit mass at steps with $p_{b-1}\ge\eta$ is at least $1/2$. There
$p_{b-1}^2\ge\eta p_{b-1}$, and $\ind{d\in X_h(b)}p_{b-1}$ has expectation
equal to the probability of exit at step $b$. Summing gives
\eqref{eq:squared-exit-mass}.
\end{proof}
\subsection{A hybrid transition}
Lemma~\ref{lem:exit} supplies mass for squared exit probabilities. To use
it we compare the ordinary guard transition with a second transition of the
same conditional law that also uses the departing labels' test bits; joint
exit of the two will certify safety against $K_{h,b}$.
Fix $a_h+2\le b\le0$ and a pre-step transcript $\mathcal H_b$. Run the
ordinary step from $S=X(b)$ to $S'=X(b-1)$ with transcript
$\mathcal H_{b-1}$. Both transitions start from the frozen input $S$; the
ordinary output $S'$ decides where each hybrid bit comes from:
\begin{equation}\label{eq:hybrid-bits}
\begin{array}{c|c|c}
\text{coordinates }e & \text{ordinary status} & \widetilde c_e\\ \hline
G_j\cap S'_j & \text{unqueried} & \ind{e\in C}\\
G_j\cap(S_j\setminus S'_j) & \text{queried} & \ind{e\in T}
\end{array}
\end{equation}
Let $\widetilde N=\mathcal G_{b-1}(\widetilde c,S)$, with intermediate flats
$\widetilde A_j$.
Conditional on the \emph{complete} ordinary transcript, the partition is
fixed. The retained $C$-bits on $G_j\cap S'_j$ were never queried, so keep
their independent rate-$t$ laws; no $T$-bit was queried, and the whole test
mask is independent of the guard mask. So the hybrid vector has the fresh
product law conditional on $\mathcal H_{b-1}$, and its output law is the
ordinary transition law determined by $\mathcal H_b$. In particular on
$\{d\in X_h(b)\}$ we have
$\Prob(d\notin\widetilde N_h\mid\mathcal H_{b-1})=p_{b-1}$, and the tower
property gives
\begin{align}
&\Prob(d\in X_h(b),\,d\notin X_h(b-1),\,d\notin\widetilde N_h\mid\mathcal H_b)
\notag\\
&\quad=\Ex\bigl[\ind{d\in X_h(b)}\ind{d\notin X_h(b-1)}p_{b-1}\mid\mathcal H_b\bigr]
=\ind{d\in X_h(b)}p_{b-1}^{2}.
\label{eq:double-exit}
\end{align}
This holds for one endpoint at a time; the same $T$ is reused across
endpoints, and no joint independence across endpoints is claimed.
There is also a deterministic containment:
\begin{equation}\label{eq:hybrid-containment}
Q_h\bigl(F_{h-1}(b-2)+K_{h,b}\bigr)\subseteq\widetilde N_h.
\end{equation}
Induct over $j<h$. If $\widetilde A_{j-1}\supseteq F_{j-1}(b-2)$ then
\[
\widetilde N_j=Q_{j,b-1}(\widetilde A_{j-1})
\supseteq Q_{j,b-2}(F_{j-1}(b-2))=X_j(b-2).
\]
The retained guards include exactly $C_j\cap X_j(b-1)$, which form
$F_j(b-2)$, so $\widetilde A_j\supseteq F_j(b-2)$. The hybrid additions
also include every $T$-positive in $G_j\cap(X_j(b)\setminus X_j(b-1))$, and
extensivity carries the earlier test additions along. Starting from
$F_0(b-1)\supseteq F_0(b-2)$ this proves
$\widetilde A_{h-1}\supseteq\cl(F_{h-1}(b-2)+K_{h,b})$. The focal map
$Q_{h,b-1}=Q_h$ is enabled, and monotonicity gives \eqref{eq:hybrid-containment}
for every completed bit assignment.
An ordinary exit at this step means $d$ has birth $b$; a simultaneous hybrid
exit, by containment, certifies the safe exclusion. Thus
\eqref{eq:double-exit} implies, for $a_h+2\le b\le0$,
\begin{equation}\label{eq:birth-safety-probability}
\begin{split}
&\Prob\bigl(b_h(d)=b,\ d\notin Q_h(F_{h-1}(b-2)+K_{h,b})\mid H,D\bigr)\\
&\hspace{24mm}\ge \Ex\bigl[\ind{d\in X_h(b)}p_{b-1}^{2}\mid H,D\bigr].
\end{split}
\end{equation}
These bounds add by linearity, and for one label the birth events at distinct
endpoints are disjoint.
\begin{lemma}[Safe sampled labels]\label{lem:safe}
For every listed group $h$,
\begin{equation}\label{eq:safe-samples}
\Ex[\sigma_h\mid H,D]\ \ge\ \frac{\eta}{4}\,|D_h\cap Y|-\frac{|D_h|}{\kappa}.
\end{equation}
\end{lemma}
\begin{proof}
Apply Lemma~\ref{lem:exit} to each $d\in D_h\cap Y$. By
Lemma~\ref{lem:paths} the only birth excluded from $a_h+2\le b\le0$ is the
baseline $a_h$ (a birth at $a_h+1$ is impossible), and $p^2\le p$, so the
discarded contribution is at most
\[
\sum_{d\in D_h\cap Y}\Prob(b_h(d)=a_h\mid H,D)
=|D_h\cap Y\cap Q_h(L)|\le\rk(Q_h(L))\le\frac{|D_h|}{\kappa},
\]
the last step by Lemma~\ref{lem:generators}. Summing
\eqref{eq:birth-safety-probability} over labels and valid births gives a
pre-parity expected safe count at least
$\tfrac{\eta}{2}|D_h\cap Y|-|D_h|/\kappa$. The independent fair parity keeps
each such label with probability $1/2$, giving the stronger lower bound
$\eta|D_h\cap Y|/4-|D_h|/(2\kappa)$, which implies \eqref{eq:safe-samples}.
\end{proof}
\section{From safe samples to unobserved rank}\label{sec:transfer}
We keep the fixed matroid and hidden vector, suppressed in conditional
expectations. The next step turns the safe-sample estimate into rank
available on labels outside the revealed mask $O=D\cup C$. Since the paths
depend on that mask, the argument needs a uniform bound on the sets the paths
can leave unspanned. For a listed group $h$ let
\[
\mathcal B_h=\{b\in\mathbb Z:a_h+2\le b\le0,\ b\equiv\varepsilon\ (\mathrm{mod}\ 2)\},
\qquad
P_{h,b}=G_h\cap\bigl(X_h(b)\setminus X_h(b-1)\bigr)\ \ (b\in\mathcal B_h),
\]
and $P_{h,b}=\varnothing$ for other endpoints of the chosen parity. Define
the nominal rank statistic
\begin{equation}\label{eq:nominal-rank}
z_h=\sum_{b\in\mathcal B_h}
\rk\bigl(P_{h,b}\setminus O\mid X_h(b-2)\cup K_{h,b}\bigr).
\end{equation}
It measures rank before the focal thinning by $T_h$ and before replacing
$X_h$ by the final path $\widehat F$.
\begin{lemma}[Sample-to-rank transfer]\label{lem:transfer}
Fix $H$. For a true group $U_i$ put $z_i=z_h$ and $\sigma_i=\sigma_h$ when
the group is listed with index $h$, and both zero otherwise. If
$n_i\ge\kappa$ then
\begin{equation}\label{eq:rank-transfer}
\Ex[z_i\mid H]\ \ge\ \frac{\gamma\,|Y_i|-2^{-23}n_i}{\kappa},
\qquad \gamma=\frac{\eta}{16}=2^{-16}.
\end{equation}
\end{lemma}
First relate $z_h$ to $\sigma_h$. Choose enough unsacrificed labels to
witness the rank in each summand of \eqref{eq:nominal-rank}; a safe sample
spanned by these witnesses over its summand base is charged to their rank by
the density bound, and every other safe sample lands in a residual set inside
the revealed mask. For each summand choose a basis extension
$Z_b\subseteq P_{h,b}\setminus O$ over $X_h(b-2)\cup K_{h,b}$, so
\begin{equation}\label{eq:rank-witnesses}
\sum_b|Z_b|=z_h,\qquad
P_{h,b}\setminus O\subseteq\cl\bigl(X_h(b-2)\cup K_{h,b}\cup Z_b\bigr).
\end{equation}
The $Z_b$ are disjoint because the $P_{h,b}$ are; fix them by the label
order. Set
\begin{equation}\label{eq:residual-set}
\mathcal R_h=\bigcup_{b\in\mathcal B_h}
\bigl(P_{h,b}\setminus\cl(X_h(b-2)\cup K_{h,b}\cup Z_b)\bigr),
\end{equation}
which lies in $O$. There is a deterministic comparison with the safe count:
\begin{equation}\label{eq:safe-residual}
\sigma_h\le\kappa\,z_h+|\mathcal R_h|.
\end{equation}
Indeed, fix $b$ and put $Q'_b=Q_h(F_{h-1}(b-2)\cup K_{h,b})$. Since
$b-2\ge a_h$, monotonicity gives $X_h(b-2)=Q_h(F_{h-1}(b-2))\subseteq Q'_b$
and $K_{h,b}\subseteq Q'_b$. A safe sample at $b$ outside $\mathcal R_h$
lies in $D_h\cap(\cl(Q'_b\cup Z_b)\setminus Q'_b)$, and
\eqref{eq:density-residual} bounds these by $\kappa\rk(Z_b\mid Q'_b)\le
\kappa|Z_b|$; summing proves \eqref{eq:safe-residual}.
\subsection{Counting marked pivots}
The set $\mathcal R_h$ depends on the focal mask, so we must control it
without knowing those bits. We build, before the bits are revealed, a small
family that contains every possible residual with small $z_h$. The key
combinatorial bound does not depend on how many times a path can change.
\begin{lemma}[Marked pivots]\label{lem:pivot-patterns}
Let $M$ be any finite matroid and $V$ a set of $n$ nonloops. Fix $s\ge0$,
an ordered sequence of labeled old occurrences, each with a mark in $\{0,1\}$,
whose labels span $E$, and at most $s$ labeled movable occurrences;
repetitions are allowed. Insert the movable occurrences into the old
sequence in any order and positions, each with either mark. For $f\in V$ its
\emph{pivot} is the first occurrence after whose insertion $f$ is spanned,
and one records that occurrence's mark. The number of resulting $n$-mark
vectors is at most
\begin{equation}\label{eq:pivot-pattern-bound}
4^s\sum_{\ell=0}^{s}\binom n\ell,
\end{equation}
with $\binom n\ell=0$ for $\ell>n$.
\end{lemma}
\begin{proof}
Bound the bases kept by greedy processing of an interleaving. Remove every
old occurrence whose label is spanned by its old predecessors; the span
after every old prefix is unchanged and no pivot mark changes. The survivors
form an ordered basis $b_1,\dots,b_r$ of $M$. Write $B_j=\{b_1,\dots,b_j\}$
and let $A$ denote all movable occurrences, ranks taken through their labels.
For each old position set
\[
\Delta_j=\rk(A\mid B_{j-1})-\rk(A\mid B_j)
=1-\rk(\{b_j\}\mid B_{j-1}\cup A)\in\{0,1\},
\]
fixed before any insertion, with $\sum_j\Delta_j=\rk(A)\le s$. If
$\Delta_j=0$ then $b_j$ raises rank even after all of $A$ is adjoined to
$B_{j-1}$, hence raises rank in every interleaving. So greedy can omit old
occurrences only at the at most $s$ positions with $\Delta_j=1$. That gives
at most $2^s$ choices of omitted old occurrences and $2^s$ of retained
movable ones, so at most $4^s$ possible kept bases.
Fix one kept basis $J$. For each $f\in V$ there is a unique minimal
$S_f\subseteq J$ spanning $f$: if $S,T\subseteq J$ both span $f$ then
submodularity on $S\cup\{f\}$ and $T\cup\{f\}$ gives
$|S|+|T|\ge|S\cup T|+\rk((S\cap T)\cup\{f\})$, so $S\cap T$ also spans $f$.
The support $S_f$ is nonempty because $f$ is a nonloop. Since at every
prefix the kept greedy occurrences span the same flat as the full prefix,
the pivot of $f$ is the last occurrence of $S_f$ in the interleaving.
Count the possible marks of those last members. Give the kept old
occurrences fixed absolute scores $2^{s+1},2^{2(s+1)},\dots$, positive for
mark $1$ and negative for mark $0$, keeping at least $s$ unused powers of two
before the first, between successive old scores, and (reserve) after the
last. Every order of the kept movable occurrences can be represented by
distinct unused powers in the right gaps, signed by their marks; then every
absolute score exceeds the sum of all earlier ones. Let the signed
movable scores be real variables, at most $s$ of them. For each $f$, the sum
of scores over $S_f$ is affine in these variables, with constant term the
sum of the fixed old scores in $S_f$. At the representation just built this
sum is nonzero and its sign is the mark of the last member of $S_f$. Thus
every pivot-mark vector for $J$ is a strict sign pattern of $n$ affine
functions in dimension at most $s$.
The remaining estimate is the affine-arrangement region bound
(Schl\"afli \cite{Schlafli1901}): $n$ affine functions in dimension $d$ have
at most $\sum_{\ell=0}^{d}\binom n\ell$ strict sign patterns. A prescribed
strict pattern is open and convex, and adding a proper affine hyperplane
splits at most as many regions as the induced arrangement on it, giving
$N(n,d)\le N(n-1,d)+N(n-1,d-1)$ with $N(0,d)=1$ and $N(n,0)\le1$. Nonzero
constants have fixed sign, an identically zero function yields no strict
pattern, and coincident or degenerate hyperplanes cannot increase the count.
Induction gives the binomial sum. Applying it to each of the at most $4^s$
kept bases, with all movable orders, positions and marks already counted,
proves \eqref{eq:pivot-pattern-bound}.
\end{proof}
\subsection{Encoding residuals as a small family}
We apply the counting bound twice. The first marked sequence tests whether a
label has a valid nominal birth of the chosen parity; among labels passing it,
the second tests whether, within its layer, the label stays outside the span
of the preceding flat, the competing test labels, and the rank witnesses.
Their intersection is exactly the residual. Counting both tests before the
focal bits are exposed is what lets a later union bound work despite the
residual depending on those bits.
\begin{lemma}[A uniform family of residuals]\label{lem:pattern-family}
Fix $H$ and a true group $U_i$ of size $n=n_i\ge\kappa$. Condition also on
the parity and on the $D,C,T$ bits outside $U_i$, but not on their bits inside
$U_i$ nor on whether $U_i$ is listed. There is a deterministic family
$\mathfrak R_i\subseteq2^{U_i}$ with
\begin{equation}\label{eq:pattern-family-size}
|\mathfrak R_i|\le\exp\!\left(\frac{1000\log\kappa}{\kappa}\,n\right)
\end{equation}
such that, whenever the group is listed and $z_h\le n/\kappa$, every residual
\eqref{eq:residual-set} from witnesses \eqref{eq:rank-witnesses} lies in
$\mathfrak R_i$.
\end{lemma}
\begin{proof}
If $U_i$ is listed its index is one plus the number of listed lower-weight
groups; call it $h$ whether or not the group is listed. The lower-group
paths $F(k):=F_{h-1}(k)$ and all $K_{h,b}$ are fixed by the conditioning, and
no $D,C,T$ bit inside $U_i$ touches them. Write $a=a_h$ and
$q=\lfloor n/\kappa\rfloor$.
On a listed outcome, Lemma~\ref{lem:generators} gives $J_h\subseteq U_i$,
$|J_h|\le q$, and insertion times $\tau(g)\in[a,0]$ with
\begin{equation}\label{eq:encoded-path}
X_h(k)=\cl\!\bigl(F(k)\cup\{g\in J_h:\tau(g)\le k\}\bigr).
\end{equation}
When $z_h\le n/\kappa$ the witness union $Z=\bigcup_b Z_b$ has at most $q$
labels. We allow all choices of these two subsets of $U_i$ and encode the
residual with two marked sequences; a label in both is one occurrence per
role.
\emph{First sequence (birth test).} Advance $k$ from $a-2$ to $1$. At time
$k$ take as old occurrences a fixed label-ordered listing of $F(k)$ and mark
the whole block by $1$ exactly when $k\in\mathcal B_h$. These old slots,
including order and marks, are fixed and span $E$ since $F(0)=E$. For the
actual path insert each $g\in J_h$ at its time $\tau(g)$, after that block,
with the block's mark. After time $k$ the generated flat is $X_h(k)$, so the
labels of $U_i$ receiving mark $1$ form exactly
$\bigcup_{b\in\mathcal B_h}P_{h,b}$.
\emph{Second sequence (layer test).} Take the unique
$b_0\in\{a-2,a-1\}$ with $b_0\equiv\varepsilon$, then the successive
endpoints $b_0+2,\dots,b_1\in\{0,1\}$, starting from $L=X_h(b_0)$. For each
layer $(b-2,b]$: (i) insert a fixed listing of $K_{h,b}$ as old occurrences
with mark $0$, then the movable witnesses $Z_b$ with mark $0$
($Z_b=\varnothing$ if $b\notin\mathcal B_h$); (ii) insert a fixed listing of
$F(b)$ with mark $1$, then the movable density generators with
$b-2<\tau(g)\le b$ with mark $1$. The old slots are fixed and span $E$ at
the final endpoint. The phases realize
\[
X_h(b-2)\xrightarrow[\text{mark }0]{\text{(i)}}
\cl\bigl(X_h(b-2)\cup K_{h,b}\cup Z_b\bigr)
\xrightarrow[\text{mark }1]{\text{(ii)}}X_h(b),
\]
because $K_{h,b}\subseteq F(b)$ and $Z_b\subseteq X_h(b)$, and the generators
inserted at $b-1$ are postponed to phase (ii); induction from $b_0$ gives the
endpoints exactly.
Take a label passing the first test with valid birth $b$. It is outside
$X_h(b-1)$ and hence $X_h(b-2)$, so its second-sequence pivot is in this
layer, and its second mark is $1$ exactly when it is not spanned at the end of
phase (i), i.e.\ exactly its membership in $\mathcal R_h$. Thus the residual
is the intersection of the two mark-$1$ sets. Phase (ii) can also span labels
born at $b-1$, which is why the first test is needed.
Now define $\mathfrak R_i$ without the focal bits: for every pair of subsets
$J,Z\subseteq U_i$ of size at most $q$, include every intersection of two
marked-pivot sets from the fixed sequences above, allowing all placements,
orders and marks. This may include spurious intersections, only enlarging
the family; the construction shows every actual residual is inside.
Let $S_d(n)=\sum_{\ell=0}^d\binom n\ell$. There are at most $S_q(n)^2$ subset
pairs and at most $2q$ movable occurrences in a sequence, so
\eqref{eq:pivot-pattern-bound} gives
\begin{equation}\label{eq:raw-pattern-count}
|\mathfrak R_i|\le S_q(n)^2\bigl(4^{2q}S_{2q}(n)\bigr)^2.
\end{equation}
For $0<\alpha\le1/2$,
\[
\alpha^{\alpha n}S_{\lfloor\alpha n\rfloor}(n)
\le\sum_{\ell=0}^{\lfloor\alpha n\rfloor}\binom n\ell\alpha^\ell
\le(1+\alpha)^n\le e^{\alpha n}.
\]
Using $q\le n/\kappa$ and $2q\le\lfloor2n/\kappa\rfloor$ with
$\alpha=1/\kappa$ and $2/\kappa$ bounds \eqref{eq:raw-pattern-count} by
\[
\log|\mathfrak R_i|
\le\frac n\kappa\bigl(6\log\kappa+6+4\log2\bigr)
\le\frac{1000\log\kappa}{\kappa}\,n,
\]
which is \eqref{eq:pattern-family-size}. All tested labels are nonloops, and
no representability of the matroid is used.
\end{proof}
\subsection{Completing the sample-to-rank estimate}
The residual family is fixed before the focal mask is exposed, so we can bound
the chance that any large member lies wholly inside $O$, even though the
actual residual is chosen using that mask.
\begin{proof}[Proof of Lemma~\ref{lem:transfer}]
Put $n=n_i$. On the unlisted branch $D\cap U_i$ is empty; extend both sides
of Lemma~\ref{lem:safe} by zero there and average over $D$. Each label lies
in $D$ with probability $1/4$, so
\begin{equation}\label{eq:averaged-safe-count}
\Ex[\sigma_i\mid H]\ \ge\ \frac\eta{16}|Y_i|-\frac{n}{4\kappa}
\ \ge\ \gamma|Y_i|-\frac n\kappa.
\end{equation}
Use the conditioning of Lemma~\ref{lem:pattern-family}. Inside $U_i$ the
events $\{e\in O\}$ are independent with
$p_O=1-(1-1/4)(1-t)=\tfrac14+\tfrac34t\le\tfrac12$, so for each fixed
$R_0\in\mathfrak R_i$, $\Prob(R_0\subseteq O)\le2^{-|R_0|}$. Let
$\delta=2^{-26}$ and let $\mathcal E_i$ be the event that some
$R_0\in\mathfrak R_i$ has $R_0\subseteq O$ and $|R_0|>\delta n$. A union
bound gives
\begin{align}
\Prob(\mathcal E_i\mid H,\varepsilon,\text{masks outside }U_i)
&\le\exp\!\left(\frac{1000\log\kappa}{\kappa}n-\delta n\log2\right)
\notag\\
&=2^{-(2^{-26}-100000\cdot2^{-100})n}
\le2^{-2^{-27}n}\le2^{-2^{73}}<2^{-26},
\label{eq:residual-tail}
\end{align}
where $\kappa=2^{100}$ and $n\ge\kappa$, the bound holding already at the
smallest analyzed size.
Define an error variable $e_i$: on a listed outcome with $z_i\le n/\kappa$
choose the witnesses and set $e_i=|\mathcal R_h|$; otherwise set $e_i=0$. In
its nonzero branch $\mathcal R_h\in\mathfrak R_i$ and
$\mathcal R_h\subseteq O$, so $e_i\le\delta n+n\ind{\mathcal E_i}$ and
$\Ex[e_i\mid H]\le2\delta n=2^{-25}n$, using \eqref{eq:residual-tail} and then
averaging that conditioning away. In every outcome
$\sigma_i\le\kappa z_i+e_i$: for listed $z_i\le n/\kappa$ this is
\eqref{eq:safe-residual}; for listed $z_i>n/\kappa$ it is
$\sigma_i\le n<\kappa z_i$; for unlisted both sides vanish. Taking
expectations with \eqref{eq:averaged-safe-count},
\[
\kappa\,\Ex[z_i\mid H]
\ge\gamma|Y_i|-(\kappa^{-1}+2^{-25})n
\ge\gamma|Y_i|-2^{-23}n,
\]
which is \eqref{eq:rank-transfer}.
\end{proof}
\section{Rank and payoff for every arrival order}\label{sec:accounting}
We pass from the nominal rank guarantee of Lemma~\ref{lem:transfer} to the
actual greedy reward. An order-independent rank statistic on the final layers
bounds the reward for \emph{every} order with all coins fixed. We then compare
final and nominal layers using one generator budget over the whole auxiliary
timeline. Only after these deterministic comparisons do we average over the
independent test thinning and the other masks.
\subsection{A simultaneous rank lower bound}
Fix all weights and coins. For a listed group $h$ put
$S_{h,b}=P_{h,b}\setminus O$ and define the order-independent statistic
\begin{equation}\label{eq:actual-rank-statistic}
\lambda_h=\sum_b\rk\bigl(T_h\cap S_{h,b}\mid\widehat F(b-2)+K_{h,b}\bigr).
\end{equation}
Sums over $b$ use the chosen parity, and terms outside the finite nontrivial
range are zero. Each summand is the rank left among tested, unobserved labels
of group $h$, after contracting the preceding final flat and all lower-weight
test competitors. Let $N_{\ge h}(\pi)$ be the number of accepted labels whose
rounded weight is at least that of $G_h$.
\begin{lemma}[Order-uniform rank bound]\label{lem:all-orders}
For each realization of all coins and every permutation $\pi$,
\begin{equation}\label{eq:all-orders}
N_{\ge h}(\pi)\ \ge\ \lambda_h.
\end{equation}
\end{lemma}
\begin{proof}
At endpoint $b$ let $F=\widehat F(b-2)$ and $E_b$ the entire eligible set of
that layer. Whatever the order or the interleaving with other layers, the
final greedy set $B_b$ is a basis of $E_b$ over $F$. Split
$B_b=L_b\sqcup H_b$ into selected labels of strictly lower weight than $G_h$
and the rest. Independence and spanning give
\[
|H_b|=\rk(H_b\mid F+L_b)=\rk(E_b\mid F+L_b).
\]
Every element of $T_h\cap S_{h,b}$ outside $F$ is eligible; those in $F$
contribute no rank. Also $L_b\subseteq K_{h,b}$, since each lower-weight
accepted label is test-positive and has nominal birth in a lower group. Thus
\[
|H_b|\ge\rk(T_h\cap S_{h,b}\mid F+L_b)
\ge\rk(T_h\cap S_{h,b}\mid F+K_{h,b}).
\]
Summing over layers proves \eqref{eq:all-orders}; including unselected or
sacrificed labels in $K_{h,b}$ only weakens the bound.
\end{proof}
\subsection{One budget for later path expansions}
\begin{lemma}[Telescoping rank cost]\label{lem:rank-cost}
For each listed group $h$ the nominal statistic $z_h$ satisfies
\begin{equation}\label{eq:rank-cost}
\sum_b\rk(S_{h,b}\mid\widehat F(b-2)+K_{h,b})\ \ge\ z_h-c_h,
\qquad
c_h=|C_h|+\sum_{j>h}\bigl(|C_j|+|D_j|/\kappa\bigr).
\end{equation}
\end{lemma}
\begin{proof}
Take the generators of Lemma~\ref{lem:generators} and put
\[
J=C_h\cup\bigcup_{j>h}(C_j\cup J_j).
\]
This single set has $|J|\le c_h$ and, for every integer $k$,
\begin{equation}\label{eq:common-generator-set}
X_h(k)\subseteq\widehat F(k)\subseteq\cl(X_h(k)+J).
\end{equation}
Indeed the first group's guards lie in $C_h$; each later group's density path
uses part of $J_j$, and its guards lie in $C_j$. Induction over groups gives
the second inclusion for all times at once.
At endpoint $b$ abbreviate $A=X_h(b-2)+K_{h,b}$ and $S'=S_{h,b}$. The
conditioning set in \eqref{eq:rank-cost} lies between $A$ and $\cl(A+J)$, so
the rank loss is at most
\begin{align}
\rk(S'\mid A)-\rk(S'\mid A+J)
&=\rk(J\mid A)-\rk(J\mid A+S')\notag\\
&\le\rk(J\mid X_h(b-2))-\rk(J\mid X_h(b)),
\label{eq:rank-telescope-step}
\end{align}
because $X_h(b-2)\subseteq A\subseteq A+S'\subseteq X_h(b)$ (the last step
uses $K_{h,b}\subseteq F_{h-1}(b)$ and $P_{h,b}\subseteq X_h(b)$) and
conditional rank decreases as the conditioning set grows. Summing the right
side of \eqref{eq:rank-telescope-step} over the chosen parity telescopes to at
most $\rk(J)\le|J|$. Missing endpoints may be added since all differences are
nonnegative. This proves \eqref{eq:rank-cost}; neither independence of $J$
nor a per-layer budget is required.
\end{proof}
\subsection{Independent thinning and group estimates}
Both lemmas hold simultaneously for every realization and order. We now
average the focal group's test bits, which took no part in building its paths
or its lower-weight competition sets.
\begin{lemma}[Independent test thinning]\label{lem:thinning}
For a listed group $h$ let $\mathcal F_{-h}$ be generated by $H,D,C$, the
parity $\varepsilon$, and the test-mask memberships outside $G_h$. Then
\begin{equation}\label{eq:test-thinning}
\Ex[\lambda_h\mid\mathcal F_{-h}]
\ge t\sum_b\rk(S_{h,b}\mid\widehat F(b-2)+K_{h,b})
\ge t(z_h-c_h).
\end{equation}
\end{lemma}
\begin{proof}
The group $G_h$ is determined by $H,D$ and the fixed weights. All paths use
$H,D,C$ and not $T$. The birth sets $P_{h,b}$ use only the parity,
$O=D\cup C$ omits $T$, and $K_{h,b}$ uses only lower groups' test bits. So
these sets, $z_h$, and $c_h$ are $\mathcal F_{-h}$-measurable, while the bits
of $T_h$ stay independent Bernoulli of rate $t$.
Conditional on $\mathcal F_{-h}$, fix an independent witness for each
unthinned rank in \eqref{eq:test-thinning}. Its intersection with $T_h$ is
still independent over the same base and has expected size $t$ times its size.
Linearity gives the first inequality, and Lemma~\ref{lem:rank-cost} the second.
No order is conditioned upon.
\end{proof}
Return to true weight indices. For a listed true group $U_i=G_h$ put
$\lambda_i=\lambda_h$, $c_i=c_h$; if it is unlisted set both to zero, as with
$z_i$. Conditional on $H$, dominate the cost pointwise by counts on all true
groups,
\[
c_i\le |C\cap U_i|+\sum_{\ell>i}\Bigl(|C\cap U_\ell|+\frac{|D\cap U_\ell|}{\kappa}\Bigr),
\]
and only then take expectations. Mask probabilities are unchanged under this
conditioning, so
\begin{equation}\label{eq:expected-cost}
\Ex[c_i\mid H]\le t n_i+(t+1/\kappa)\sum_{\ell>i}n_\ell .
\end{equation}
(The exact density-mask contribution is $1/(4\kappa)$; the larger coefficient
is convenient.) Lemmas~\ref{lem:transfer} and~\ref{lem:thinning} then give,
for every true group of size $n_i\ge\kappa$,
\begin{equation}\label{eq:group-payoff}
\Ex[\lambda_i\mid H]\ge\frac{t}{\kappa}\Bigl(
\gamma|Y_i|-(2^{-23}+t\kappa)n_i-(1+t\kappa)\sum_{\ell>i}n_\ell\Bigr).
\end{equation}
Although different $\lambda_i$ may depend on one another's test bits, each
separate thinning is valid, and the expectations may be summed without
asserting independence.
\subsection{The weighted sum and the final constant}
Let $A_{\mathrm{main}}(R,\pi)$ be the main rule's accepted set and let
$\mathcal A(H)=\{i:n_i\ge\kappa\}$ be the analyzed true groups. For a true
weight index $i$ let $N_i(\pi)$ count accepts of weight at least $B^i$.
Lemma~\ref{lem:all-orders}, with $\lambda_i=0$ on unlisted groups, gives
$\lambda_i\le N_i(\pi)$ simultaneously for every $\pi$. Each accepted weight
$B^\ell$ contributes at most $\sum_{i\le\ell}B^i=B^\ell B/(B-1)<2B^\ell$ to
the cumulative weighted counts. Hence the pointwise inequality is
\begin{equation}\label{eq:minimum-before-expectation}
\min_\pi u(A_{\mathrm{main}}(R,\pi))
\ \ge\ \frac12\sum_{i\in\mathcal A(H)}B^i\lambda_i .
\end{equation}
The order has been minimized before any expectation is taken.
Multiply \eqref{eq:group-payoff} by $B^i$ and sum over analyzed groups. The
higher-weight cost is bounded using
\[
\sum_{i\in\mathcal A(H)}B^i\sum_{\ell>i}n_\ell
\le\sum_\ell n_\ell\sum_{i<\ell}B^i
=\frac1{B-1}\sum_\ell B^\ell n_\ell .
\]
With \eqref{eq:constants},
\begin{equation}\label{eq:error-constant}
2^{-23}+t\kappa+\frac{1+t\kappa}{B-1}<2^{-21},
\end{equation}
since $t\kappa=2^{-40}$ and the fractional term is below $2^{-30}$.
Combining with \eqref{eq:minimum-before-expectation} yields
\begin{equation}\label{eq:conditional-main-payoff}
\Ex\!\left[\min_\pi u(A_{\mathrm{main}}(R,\pi))\given H\right]
\ge\frac{t}{2\kappa}\Bigl(
\gamma\sum_{i\in\mathcal A(H)}B^i|Y_i|-2^{-21}u(U)\Bigr).
\end{equation}
Suppose $W>0$, so $m_*>0$. Ignoring the smaller true groups loses at most
\begin{equation}\label{eq:small-groups}
\sum_{i\notin\mathcal A(H)}B^i|Y_i|\le\kappa\sum_{B^i\le m_*}B^i<2\kappa m_* .
\end{equation}
If $m_*\le W/(8\kappa)$, Lemma~\ref{lem:filter} and \eqref{eq:small-groups}
give $\Ex_H\sum_{i\in\mathcal A(H)}B^i|Y_i|\ge W/4$ and $\Ex_H u(U)\le W$.
Since $\gamma=2^{-16}$, $\gamma/4-2^{-21}=7\cdot2^{-21}\ge\gamma/8$, so
\begin{equation}\label{eq:main-branch-guarantee}
\Ex\bigl[\min_\pi u(A_{\mathrm{main}}(R,\pi))\bigr]
\ \ge\ \frac{t\gamma}{16\kappa}\,W .
\end{equation}
If instead $m_*>W/(8\kappa)$, the maximum branch gives more than
$W/(32\kappa)$ by \eqref{eq:maximum}.
\begin{proof}[Proof of Proposition~\ref{prop:hidden} and Theorem~\ref{thm:main}]
Choose the two branches with equal probability. In the first case the main
branch contributes at least $t\gamma W/(32\kappa)$ after mixing. In the
second case the maximum branch contributes more than $W/(64\kappa)$, which
exceeds the same target since $t\gamma=2^{-156}\ll1/2$. The minimum over
orders is taken separately for every complete seed, including the branch, so
the fair mixture is valid against branch-dependent orders. True accepted
weights dominate their rounded values, and by \eqref{eq:rounding} the
resulting fixed-vector reward fraction is
\[
\frac{t\gamma}{32\kappa B}
=2^{-140-16-5-100-32}=2^{-293}.
\]
When $W=0$ the benchmark is zero and the claim is immediate. Feasibility and
measurability follow from Lemma~\ref{lem:feasibility} and the analogous
properties of the maximum branch. This proves Proposition~\ref{prop:hidden}.
The revealed mask is chosen from the initial seed independently of the
weights, so Lemma~\ref{lem:simulation} proves Theorem~\ref{thm:main}, with
slack in its announced constant.
The construction covers empty ground sets, loops, rank zero, ties, and zero
values as specified. Each realized weight vector is finite even under
unbounded support. Only the expected optimum needs to be finite; loop
values, which can never be accepted, need no moment condition.
\end{proof}
\section{An order-oblivious secretary consequence}\label{sec:secretary}
The fixed-vector guarantee also gives a secretary rule with a random
observation prefix and an adversarial suffix, in the prefix/suffix form of
Azar, Kleinberg and Weinberg \cite{AKW14} but with full visibility of the
rule's entire seed. The mechanism is the sacrificed observation mask of
Proposition~\ref{prop:hidden}. Inside either branch, a binomial prefix
length chosen independently of the permutation reproduces that branch's
product-mask law. After observing that set the rule uses predrawn random
coordinates to reconstruct the remaining source coins from their conditional
law. The expected minimum over all orders then absorbs any rearrangement of
the suffix.
\begin{corollary}[Order-oblivious selection with full-seed visibility]
\label{cor:secretary}
For each known finite labeled matroid $M=(E,\mathcal I)$ there is one
measurable randomized online rule $\mathcal S_M$ with the following
property. Fix any finite nonnegative vector $w\in[0,\infty)^E$ before all
rule and arrival randomness. Without knowing $w$ the rule draws its complete
initial seed $Q$, independent of a uniformly random permutation $\sigma$ of
$E$, and fixes a possibly random prefix length $K$ before any arrival. It
observes the first $K$ label--weight pairs of $\sigma$ in order and rejects
them. After this prefix, an adversary may know $M$, the entire $w$, the
ordered prefix, and the complete seed $Q$ (including $K$, the branch choice,
and unused coins), and may choose any measurable permutation $\tau$ of the
remaining labels as a function of this information. The rule is not told the
future suffix order and decides irrevocably at each suffix arrival while
keeping an independent set. For every such adversary, with $A_{\mathcal S}$
the accepted set,
\begin{equation}\label{eq:secretary-guarantee}
\Ex\!\left[\sum_{e\in A_{\mathcal S}}w_e\right]\ \ge\ 2^{-293}\OPT_M(w).
\end{equation}
The expectation is over the rule seed and random prefix and over any
adversary randomization; the adversary cannot alter the random-prefix law or
choose the weights after observing the seed or prefix.
\end{corollary}
\begin{proof}
Let $R$ be the complete source seed of Proposition~\ref{prop:hidden},
including the fair branch choice $J$. The maximum branch sacrifices an
independent mask of rate $p_{\mathrm{max}}=1/2$; the main branch sacrifices
$B_0=H\cup D\cup C$, of rate
\[
p_{\mathrm{main}}=1-(1-\tfrac12)(1-\tfrac14)(1-t)=\tfrac58+3\cdot2^{-143},
\qquad t=2^{-140}.
\]
The test mask $T$ is not sacrificed. Both rates lie strictly between zero and
one and are independent of $w$.
Let $n=|E|$. Draw $J$, then $K\mid J\sim\operatorname{Bin}(n,p_J)$, as part
of $Q$ before arrivals and independently of $\sigma$; write
$P=\{\sigma_1,\dots,\sigma_K\}$. For each fixed $p\subseteq E$,
\begin{equation}\label{eq:secretary-prefix-mask}
\Prob(P=p\mid J)=\frac{\Prob(K=|p|\mid J)}{\binom n{|p|}}
=p_J^{|p|}(1-p_J)^{n-|p|},
\end{equation}
so $P\mid J$ has exactly the product law of the source sacrificed mask. This
averages over $K$; no product-law claim is made conditional on $K$.
After the prefix, reconstruct $R$ from its source conditional law given $J$
and $B_0=P$. In the maximum branch set its fair mask equal to $P$. In the
main branch set $(H_e,D_e,C_e)=(0,0,0)$ for $e\notin P$, and for each $e\in P$
independently use the original product law of the triple conditioned on being
nonzero, each of the seven probabilities being the original divided by
$p_{\mathrm{main}}$. Keep the source laws of $T$, the parity, unused branch
coins, and all other coins. Multiplying this kernel by
\eqref{eq:secretary-prefix-mask} recovers exactly the source joint law of the
branch and complete seed, with $B_0(R)=P$.
This reconstruction needs no concealed later randomness. The seed $Q$
predraws independent uniforms for the finite conditional kernels and the
remaining source coins; after the prefix the kernels are evaluated by fixed
interval partitions from the label set $P$ alone, not its weights. So the
derived $R$ is a function of $(Q,P)$, known to the adversary; any extra
information in $Q$ may reveal more than $R$, which the pointwise comparison
below permits.
Initialize the hidden rule with $R$ and $w|_P$ and virtually feed the prefix
in order, forcing every prefix label rejected and replaying any internal
state changes. Then feed each suffix label and weight as it arrives, with no
unseen suffix weight or future order. For the concatenated permutation
$\pi=(\sigma_1,\ldots,\sigma_K,\tau)$, induction on arrivals gives exactly
$A(w,R,\pi)$. Hence for every realization, including $\tau$ depending on all
of $Q$ and the ordered prefix,
\[
\sum_{e\in A_{\mathcal S}}w_e
=\sum_{e\in A(w,R,\pi)}w_e
\ge\min_{\pi'}\sum_{e\in A(w,R,\pi')}w_e .
\]
The marginal law of $R$ is the source law and $w$ was fixed before the
randomness, so averaging and applying Proposition~\ref{prop:hidden} proves
\eqref{eq:secretary-guarantee} with no extra loss. Feasibility is inherited.
For fixed finite $M$ the mask kernels have finite support and measurable
interval-partition realizations, so composition gives a measurable rule; the
minimum is over finitely many rewards, each capped by the finite
$\OPT_M(w)$. The cases $K=0$, $K=n$, empty ground sets, loops, rank zero,
ties and zero weights are covered by the same construction.
\end{proof}
For ordinary uniformly random arrivals, recent work gives much larger
constants. Abdi, Banihashem, Hajiaghayi and Mittal \cite{ABHM26} give a
polynomial-time $1/64$-competitive ordinal rule for known matroids;
Singla \cite{Singla26} and Huang \cite{Huang26} select each element of a fixed
optimum with probability at least $1/4$ and $1/e$. Those results keep the
arrivals random throughout, whereas Corollary~\ref{cor:secretary} survives an
arbitrary full-seed adversarial rearrangement of the unobserved suffix, with
no additional loss from the fixed-vector guarantee.
\begin{thebibliography}{99}
\bibitem{KS77} U.~Krengel and L.~Sucheston. Semiamarts and finite values.
\emph{Bulletin of the AMS}, 83(4):745--747, 1977.
\bibitem{KW12} R.~Kleinberg and S.~M.~Weinberg. Matroid prophet inequalities.
In \emph{STOC '12}, pages 123--136, 2012.
\bibitem{AKW14} P.~D.~Azar, R.~Kleinberg and S.~M.~Weinberg. Prophet
inequalities with limited information. In \emph{SODA '14}, pages
1358--1377, 2014.
\bibitem{FLTWWZ24} H.~Fu, P.~Lu, Z.~G.~Tang, H.~Wu, J.~Wu and Q.~Zhang.
Sample-based matroid prophet inequalities. In \emph{EC '24}, 2024.
\bibitem{FSZ26} M.~Feldman, O.~Svensson and R.~Zenklusen. Nearly tight sample
complexity for matroid online contention resolution. In \emph{SODA '26},
pages 4692--4711, 2026.
\bibitem{RWW20} A.~Rubinstein, J.~Z.~Wang and S.~M.~Weinberg. Optimal
single-choice prophet inequalities from samples. In \emph{ITCS 2020},
LIPIcs 151, 60:1--60:10, 2020.
\bibitem{CDF22} C.~Caramanis, P.~D\"utting, M.~Faw, F.~Fusco, P.~Lazos,
S.~Leonardi, O.~Papadigenopoulos, E.~Pountourakis and R.~Reiffenh\"auser.
Single-sample prophet inequalities via greedy-ordered selection. In
\emph{SODA '22}, pages 1298--1325, 2022.
\bibitem{FSZ16} M.~Feldman, O.~Svensson and R.~Zenklusen. Online contention
resolution schemes. In \emph{SODA '16}, pages 1014--1033, 2016.
\bibitem{FSZ15} M.~Feldman, O.~Svensson and R.~Zenklusen. A simple
$O(\log\log\mathrm{rank})$-competitive algorithm for the matroid secretary
problem. In \emph{SODA '15}, pages 1189--1201, 2015.
\bibitem{ABHM26} H.~Abdi, K.~Banihashem, M.~Hajiaghayi and D.~Mittal. On the
strong matroid secretary conjecture and beyond. arXiv:2609.19118v1, 2026.
\bibitem{BIK07} M.~Babaioff, N.~Immorlica and R.~Kleinberg. Matroids,
secretary problems, and online mechanisms. In \emph{SODA '07}, pages
434--443, 2007.
\bibitem{Lachish14} O.~Lachish. $O(\log\log\mathrm{rank})$ competitive ratio
for the matroid secretary problem. In \emph{FOCS '14}, pages 326--335, 2014.
\bibitem{Singla26} S.~Singla. The matroid secretary conjecture is true.
arXiv:2609.14555v2, 2026.
\bibitem{Huang26} Z.~Huang. Settling the matroid secretary problem.
arXiv:2609.30421v1, 2026.
\bibitem{SSZ25} R.~Santiago, I.~Sergeev and R.~Zenklusen.
Constant-competitiveness for random assignment matroid secretary without
knowing the matroid. \emph{Mathematical Programming}, 210:815--846, 2025.
\bibitem{Soto13} J.~A.~Soto. Matroid secretary problem in the random-assignment
model. \emph{SIAM Journal on Computing}, 42(1):178--211, 2013.
\bibitem{Edmonds65} J.~Edmonds. Minimum partition of a matroid into independent
subsets. \emph{J. Res. Nat. Bur. Standards B}, 69B:67--72, 1965.
\bibitem{Schlafli1901} L.~Schl\"afli. Ueber die Zahl der Teile, in welche die
$n$fache Totalit\"at durch eine beliebige Menge $(n-1)$facher linearer
Kontinua geteilt wird. In \emph{Theorie der vielfachen Kontinuit\"at},
chapter 16, pages 39--42, Basel, 1901.
\end{thebibliography}
\end{document}