Adaptive Stochastic Matching: An Expected Query Bound and the Cost of Mandatory Batching

We study adaptive edge discovery in a known finite bipartite graph whose edges are independently present with probability 1/2. Queries are charged at both endpoints, successful edges may be retained without commitment, and the objective is expected matching size relative to the expected full-information optimum.First, the established optimistic maximum-matching-round policy, run for R rounds, has expected relative loss at most 2 log(3)/(R log(3/2)). It therefore obtains a (1-epsilon) approximation with a hard per-vertex query cap ceil(6/epsilon) on every finite input. The proof tracks evolving vertex covers indexed by subsets of one minimum cover of the host graph.Second, on an explicit family with accuracy parameter epsilon_N, mandatory optimistic matching batches need Omega(1/(epsilon_N log^2(1/epsilon_N))) queries at some vertex, whereas interior-first screening achieves the same expected accuracy with O(log(1/epsilon_N)) queries per vertex. The screening policy uses optimistic maximum-matching proposals but cancels a proposal after a negative answer. Thus within-proposal stopping can change endpoint query cost exponentially on this family.The algorithm and construction precedents are attributed in the manuscript. The paper does not establish a universal logarithmic query guarantee or make empirical relationship-prediction claims. Complete proofs and a vector schematic are included. This is an AI-assisted preprint, not a peer-reviewed publication; OpenAI Codex assisted with mathematical derivation, drafting, and internal proof review. No empirical dataset or simulations are used.