Many deployed selection systems choose a small, diverse set of items as data streams past: exemplars for clustering, seed users for an influence campaign, a shortlist of movies to recommend. Two kinds of rules usually govern these choices. The first is structural. The chosen set must be "independent" in a matroid, a family of allowed sets that generalizes simple caps such as "at most $k$ items" or "at most $k_j$ items from category $j$". The second is fairness: each demographic group must receive between $l_c$ and $u_c$ slots. In Fairness in Streaming Submodular Maximization over a Matroid Constraint, the authors prove that no single-pass, small-memory algorithm can always return a set satisfying both rules. Their provable algorithm therefore reads the data twice, relaxes the fairness lower bounds by a factor of 2, and guarantees only $1/11.656$ of the optimum. Yet in the same paper, a simple single-pass heuristic satisfied every fairness constraint in every run on real data.
This note proposes to close that gap. The worst case is real, but real streams seem not to trigger it. We want to identify a measurable property of an instance under which one pass provably suffices, and to build a streaming algorithm that checks this property while it runs. The algorithm stays single-pass when the data allows it and asks for a second pass only when the data shows it is needed. The theory–practice angle is concrete: a deployment observation contradicts a theorem, and we turn that contradiction into a new theorem plus a checkable runtime certificate. The IAAI organizers describe this as the job of deployment in IAAI-13 Preface, where real constraints expose the limits of current models.
Core Claim
We conjecture that the impossibility result depends on two ingredients appearing together. One is adversarial arrival order. The other is groups whose elements are barely sufficient to reach their quota once other choices have been committed. We make the second ingredient precise with a slack parameter.
Let $\mathcal{M}$ be the matroid, $k$ its rank, and $V_c$ the elements of group $c$ with lower bound $l_c$. Call an instance $\delta$-slack if the following holds for every independent set $A$ of size at most $k - \sum_c l_c$ and every group $c$:
$$\mathrm{rank}_{\mathcal{M}/A}(V_c) \ge (1+\delta)\, l_c .$$
Here $\mathcal{M}/A$ is the matroid left after committing to $A$. In words, whatever the "free" part of the solution looks like, each group can still extend it by noticeably more than its quota.
The target theorem has three parts, and the conditions differ between them.
The first part covers random arrival order. Suppose the instance is $\delta$-slack and the stream arrives in random order. Then a single-pass algorithm that reserves capacity for under-filled groups returns a fair independent set except with probability at most $C\exp(-\Omega(\delta^2 l_{\min}))$, where $l_{\min}$ is the smallest quota. The exponential form comes from Chernoff-type concentration of how many rank-increasing group elements land in each segment of a randomly ordered stream.
The second part asks for a constant-factor objective guarantee. This guarantee has no factor-2 fairness relaxation and is meaningfully better than $1/11.656$.
The third part removes the random-order assumption and requires slack alone. The algorithm can test the slack condition, or a cheap proxy for it, online. On failure it falls back to the two-pass procedure of Fairness in Streaming Submodular Maximization over a Matroid Constraint. So it keeps that procedure's guarantees in the worst case and pays for the second pass only when the data demands it.
What would be new is an instance-level explanation of an observed empirical regularity, together with an algorithm whose cost adapts to how hard the instance actually is. Prior work offers either a worst-case two-pass method or an unexplained single-pass heuristic.
Research Program
The theory proceeds in two stages. We start with partition matroids, where each category has its own cap. Contraction is explicit there, so the slack condition reduces to per-group counting and can be computed exactly. We then move to general matroids such as graphic and transversal ones. In those, slack can only be bounded, using the rank of each group's buffered elements in the contraction by the current solution. A secondary theoretical question is whether a smoothed model, in which an adversarial order is perturbed by random swaps, recovers most of the random-order guarantee. Real logs are often sorted by time or by source, so a random-order theorem alone would oversell the result.
The algorithm keeps a small reservoir for each group, in the spirit of the first pass of FAIR-STREAMING, alongside a threshold-based main solution. Throughout the stream it tracks an estimate of each group's remaining "extendable rank" given what has been committed. If any group's estimate falls below its unfilled quota plus a margin set by $\delta$, the algorithm raises a flag. The flag either triggers a repair step from the reservoir or, if repair fails, triggers the second pass. The output carries a certificate: either the observed slack trajectory, which justifies the single-pass answer, or a record that the fallback was invoked.
The empirical program has two jobs. The first is to measure slack on the real instances where the heuristic succeeded, to confirm that the explanation actually applies there. The second is to build stress instances that make the heuristic fail, which tests whether slack predicts failure.
Baselines
The naive reference point is unconstrained single-pass streaming maximization over the matroid that ignores fairness. This is the "unfair" comparison used in Fairness in Streaming Submodular Maximization over a Matroid Constraint. It bounds the objective from above among streaming methods and shows how often fairness is violated if nobody enforces it.
The strongest worst-case competitor is that paper's two-pass FAIR-STREAMING. It is the only method in the file with a feasibility guarantee in this setting. The paper reports that it reaches objective values within 15–26% of the unfair baselines, with a theoretical ratio of $1/11.656$ under factor-2 relaxed lower bounds.
The strongest practical competitor is the same paper's single-pass GREEDY-FAIR-STREAMING, which "satisfied all fairness constraints in every experimental run". We found no reported per-dataset objective value for GREEDY-FAIR-STREAMING on Lacuna, so we will measure it ourselves.
For an offline quality ceiling we use IterativeGreedy from Fair Representation in Submodular Subset Selection: A Pareto Optimization Approach, which traces Pareto fronts it reports as nearly identical to the exact integer-programming optimum. On instances small enough, we will also solve an exact integer program.
All methods will run on the same streams, under the same per-group memory budget measured in stored elements, the same matroid and quotas, and the same number of oracle calls to the objective, over at least 20 stream orderings per condition.
We will run three ablations on our own method. The first removes the slack monitor, leaving reservoir plus threshold rule; this isolates whether the certificate is what buys reliability. The second removes the reservoir. The third fixes the margin instead of setting it from $\delta$.
Beating the baselines means three things. We must match GREEDY-FAIR-STREAMING's objective within noise. We must achieve zero fairness violations on every stress condition where GREEDY-FAIR-STREAMING violates some. And we must invoke the second pass on only a small fraction of the natural-order runs, while recovering at least FAIR-STREAMING's objective whenever the fallback fires.
Why not just…?
Why not just deploy GREEDY-FAIR-STREAMING, since it already never failed? This is the most serious threat. Its success comes from three datasets in their given orders, with no account of why it worked or when it would stop working. A system owner cannot tell in advance whether a new stream resembles those three. Our stress tests will settle the question. If the heuristic also never fails under time-sorted, group-sorted, and impossibility-style orderings, the algorithmic contribution shrinks to an explanation plus a cheap certificate, and we will report that plainly. If it does fail, slack should predict where.
Why not just always run two passes? The second pass doubles input/output and requires storing the candidate reservoir. Most importantly, FAIR-STREAMING's guarantee holds only with lower bounds halved. That is a real cost when quotas are policy requirements rather than soft goals. The adaptive scheme keeps the two-pass guarantee as a fallback. The experiment will measure how often the fallback is actually needed on natural streams.
Why not just reservoir-sample uniformly and solve offline with a fair greedy? This turns the stream into a random-order sample, which is the very regime our theorem exploits. It is therefore a genuine competitor, and we include it at equal memory. Its weakness is predictable: rare groups get too few sampled elements to fill their quotas unless memory is allocated per group. Once memory is allocated per group, the method approaches our reservoir design without the online certificate. The rare-group stress test will show whether this matters in practice.
Proposed Experiments
We reuse the three real instances on which GREEDY-FAIR-STREAMING was reported to succeed in Fairness in Streaming Submodular Maximization over a Matroid Constraint. These are Pokec influence coverage with age groups, Portuguese Bank Marketing exemplar clustering with age groups, and MovieLens 1M recommendation, each with the same matroids and quotas as that paper. We add MovieLens-25M as a scale test, following Fair Representation in Submodular Subset Selection: A Pareto Optimization Approach.
For each instance we vary three factors. The first is ordering: random, the native order, sorted by group with the rarest group last, and an order built from the impossibility construction. The second is group rarity: we subsample one group down until its slack approaches zero. The third is quota tightness, varying $\sum_c l_c / k$.
The metrics are the fraction of runs violating any fairness bound, objective value relative to offline IterativeGreedy, memory, passes used, and wall-clock time.
The decisive check is predictive. Across all conditions, we plot the failure rate of GREEDY-FAIR-STREAMING against the measured slack $\delta$ for each instance. The thesis holds if failures concentrate where $\delta$ is near zero under non-random orders, if failure probability falls roughly exponentially in $\delta^2 l_{\min}$ under random order, and if the real datasets sit at clearly positive slack. The thesis is falsified if the heuristic fails at high slack, or never fails even at zero slack. In the second case the true explanation lies elsewhere, perhaps in objective structure or matroid geometry, and the proposal would pivot to finding it.