When Adaptivity Counts: Hit-Count Inspection with Information-Only Queries

Abstract

This working paper studies finite Bayesian decision problems in which a learner must identify one member of a hidden subset. It distinguishes an unrestricted finite-alphabet message from a physically executable observation protocol that reveals only whether a named point belongs to the hidden set. The distinction yields a concrete optimisation problem for decision value under information constraints. For an arbitrary rational prior, the optimal value of a deterministic K-symbol encoder–decoder pair is weighted maximum K-point coverage. For the uniform fixed-cardinality source, the paper derives a closed binomial expression and shows that exact rational randomisation does not improve this value. It also characterises when deterministic records are decision-neutral through simple 1-designs, and extends the free-message analysis to multiple-answer reward objectives. For perfect point-membership inspections, the paper proves that batch and deterministic adaptive protocols have the same exact one-hit decision value: weighted maximum (I+1)-point coverage for an inspection budget I. This establishes a precise boundary between free communication capacity and realizable observation. The finite results, including explicit attaining witnesses, are machine-checked in Lean 4. The claims are limited to the stated finite, rational, perfect-inspection models; they do not assert general results for noisy or pooled testing, strategic signalling, or full social-deduction games.