The Matroid Secretary Problem is a central question in online optimization, modeling sequential decision-making under combinatorial constraints. Despite significant progress, the Matroid Secretary Conjecture — which asks whether every matroid admits a constant-competitive algorithm — remains open. In the paper Free-Order Secretary for Two-Sided Independence Systems, we introduce a bipartite graph framework that unifies and extends several known formulations, including the bipartite matching, matroid intersection, and random-order matroid secretary problems. In this model, elements form a bipartite graph between agents and items, and the objective is to select a matching that satisfies feasibility constraints on both sides, given by two independence systems.
We study the free-order setting, where the algorithm may adaptively choose the next element to reveal. For $k$-matroid intersection, we leverage a core lemma by (Feldman, Svensson and Zenklusen, 2022) to design an $\Omega(1/k^2)$-competitive algorithm, extending known results for single matroids. Building on this, we identify the structural property underlying our approach and introduce $k$-growth systems — a new class of independence systems that generalize $k$-matchoids and may be of independent combinatorial interest. We establish a generalized core lemma for $k$-growth systems, showing that a suitably defined set of critical elements retains a $\Omega(1/k^2)$ fraction of the optimal weight. Using this lemma, we extend our $\Omega(1/k^2)$-competitive algorithm to $k$-growth systems for the edge-arrival model.
We then study the agent-arrival model, which presents unique challenges to our framework. We extend the core lemma to this model and then apply it to obtain an $\Omega(\beta/k^2)$-competitive algorithm for $k$-growth systems, where $\beta$ denotes the competitiveness of a special type of order-oblivious algorithm for the item-side constraint. Finally, we relax the matching assumption and extend our results to the case of multiple item selection, where agents have individual independence systems coupled by a global item-side constraint. We obtain constant-competitive algorithms for fundamental cases such as partition matroids and $k$-matching constraints.
We also study the structural role of $k$-growth systems within the hierarchy of $k$-systems. We analyze their closure under key operations, such as parallel extension, restriction and contraction, and derive a new characterization of $k$-extendible systems in terms of contractions of $k$-systems.