Semantic Discovery Is Not Enough: Complementarity Gaps and Capability Spam in Open Agent Networks

Open agent networks need more than a good match to a single agent card. Many jobs require a small team whose skills cover a multi part requirement, and the agents advertising those skills may not be honest. We study this setting as a network problem rather than a single agent demo. First we show, with short existence arguments, that cosine style ranking can miss complementary specialists even when advertisements are truthful, and that overclaiming can break any selector that trusts ads as ground truth. Then we introduce AgenticWeb Micro, a controllable open registry benchmark with honest ads, capability spam, and churn. We compare random selection, cosine retrieval, greedy skill cover, Claude Sonnet 5 reading natural language marketplace cards, and a cover method that adds sandbox probes plus reputation. On honest ads, cover based selection reaches perfect team success while similarity and Claude sit slightly lower. Under spam, advertisement trusting cover collapses to zero, Claude tracks the similarity drop, and the probe aware method recovers near perfect success. Offline ablations show the same pattern across spam rates and registry sizes, and that either probes or outcome reputation can restore cover if given a few epochs. The practical point is narrow and, we think, timely for the Agentic Web: semantic discovery helps, but team routing on open networks also needs coverage objectives and outcome grounded trust.