Coordination Has a Price: Social Evidence and Manufactured Tails in Many-Armed Bandits

When arms outnumber the horizon, most arms are cold, and a learner can find the good ones in two ways. It can explore broadly, which is why greedy selection works so well in this regime (Bayati et al., 2020), or it can borrow evidence from other participants: endorsements, ratings, co-transactions. An adversary who controls where some of the arms land can exploit both. We first show that breadth has a fixed price. If the learner's side information carries no information about who is adversarial, its expected fraud is at least $\rho \epsilon \mathbb{E}[D]$, where $D$ is the number of distinct arms it tries after adversaries defect, $\epsilon$ the adversarial fraction and $\rho$ their failure rate. Coordination changes this, because coordinated adversaries leave structure. A flag-and-propagate rule that runs one CUSUM statistic per connected group of heavily interacting arms pays at most $(h+\ln (\rho /\beta ))/\mathrm{kl}(\rho ,\beta )$ pulls per ring, independent of $D$, and blocks honest arms with probability at most $e^{-h}$ per starting point. In a standard many-armed environment with 300 arms and 30 seeds, it cuts fraud by 2.4 to 15.5 times for rings of 30 or more and does nothing against solo adversaries, and both bounds hold in every cell. In an environment where arms endorse each other, endorsements cut regret from 149 to 89, a visible ring more than doubles a naive endorsement learner's fraud, and capping positive and negative endorsement counts separately at median plus three MADs brings every self-promoting ring we tried to within 1.8 times the fraud of the same adversaries acting alone, with the regret gain intact. Adding a dense-subgraph detector pushes rings that hide their links below the solo level. Coordinated bad-mouthing of honest arms is contained to the solo baseline via public consensus-residual rater filtering (CRRF), while real fraud benchmarks delineate the domain boundary where uncoordinated review spam merges into mixed giant components governed by graph-blind lower bounds.