Bought Majorities: Capability Discovery Voids Byzantine Robustness in Agent Networks

Agentic-web designs discover specialists by advertised capability, retrieve a handful per request, and combine their answers. The obvious protection against malicious participants is Byzantine-robust aggregation, whose guarantees hold while fewer than half the aggregated inputs are corrupt. We show that discovery voids those guarantees, because the router chooses what gets aggregated. A coalition that inflates its capability card, which nothing verifies, occupies $\min(n,\, m-h)$ of the $m$ retrieved slots, where $h$ counts the honest agents it still fails to outrank; clearing them all gives $\min(n,m)$ and a capture threshold of $n > m/2$ agents, an absolute count fixed by retrieval width rather than a share of the population. At $m = 7$ that threshold is $n = 4$ agents from $K = 50$ to $400$, while the share needed falls from $0.080$ to $0.010$, so a defence stated as a tolerable fraction becomes vacuous as the network grows. Past the threshold robust aggregation does not merely fail, it inverts: coordinate-wise median and Krum become \emph{worse} than the naive weighted mean they replace, because they discard the minority and the minority is now the honest agents. We measure this on a population of language-model agents given private fact sheets, and on a second population of classifiers cheap enough to rebuild across an order of magnitude in size. Two levers work: retrieval wide relative to the tolerated coalition, and capability claims anchored on evidence the claimant does not control.