VERA: Verifiable Feasibility Representations with Counterfactual Credit for Constrained Multi-Agent Control

Constrained multi-agent control requires more than predicting rewarding actions: an action can cease to be executable as contact windows, shared capacity, and deadlines change. We introduce VERA, a centralized-training, decentralized-execution framework that separates feasibility estimation from credit assignment. Each actor predicts a five-dimensional verifiable feasibility representation (VFR). After an action is proposed, exact action-conditioned margins available only during training supervise that representation, while a counterfactual group-relative advantage (CGRA) ranks candidate representation–action pairs. Execution uses one actor pass and no privileged state. In a dynamic space–air–ground integrated network (SAGIN), VERA obtains $55.33\pm 3.60$ success with $0.45\pm 0.81$ coverage violation, within $1.33$ points of a privileged-mask reference. With rewards matched over ten paired seeds, VERA improves success over the strongest baseline by $8.74$ points ($p=0.023$) and reduces violation by $52.19$ points ($p=5.7\times 10^{-8}$). A ten-seed $4\times 2$ factorial attributes a $14.16$–$16.48$ point gain to CGRA across handcrafted, learned, random, and latent representations; evaluation on seven unseen topologies preserves a $24.33$–$30.02$ point advantage over multi-agent proximal policy optimization. From 10 to 40 users, success remains $50.1$–$53.8$, and VFR adds only $0.026$ ms to a central processing unit (CPU) actor step. Cross-domain tests further identify the governing condition: counterfactual credit succeeds when candidate scores respect shared constraints and fails under incompatible reward geometries. These results establish action-conditioned feasibility as an auditable training interface and counterfactual credit as a geometry-dependent optimization mechanism.