Not All Coupling Matters: Value-Induced Belief Edges for Budgeted Coordination in Cooperative MARL

Sparse coordination lets cooperative multi-agent reinforcement learning (MARL) scale by giving each agent a limited budget of teammate interactions. Under a fixed budget, the question is which teammates deserve that capacity. Existing edge-selection criteria mainly measure how strongly a teammate affects payoff and do not account for whether reducing uncertainty about that teammate would change the receiver's decision. The result is certainty-blind coordination: capacity goes to strongly coupled but predictable teammates, while uncertain, decision-pivotal ones are overlooked. We introduce Value-Induced Belief Edges (VIBE), which scores an edge by the expected value of resolving uncertainty about a teammate: given its belief over teammate actions, the receiver values evidence that would change its preferred action and improve its expected return. This decision value decomposes into the probability that the receiver switches actions and the gain from switching, and payoff variance can rank teammates in the opposite order. A centralised teacher approximates the decision value over a bounded set of joint-action probes, and a decentralised student learns the resulting rankings from receiver-local information. Selected edges direct relational processing of teammate features the receiver already observes, with no additional communication at execution. Extensive experiments on five benchmark families show that VIBE outperforms strong value-based, partner selection and coordination-graphs baselines. Our code is anonymously available at https://anonymous.4open.science/r/VIBE-D717