Detection Gaps on Path Graphs With Multi-Accusation Budgets

Abstract

Distributed networks rely on cooperation between autonomous agents to achieve global outcomes, but adversarial agents can disrupt these outcomes by exploiting shared responsibility for selfish gain while hiding their malicious actions among the actions of others. This creates a detection gap, where adversarial agents are known to exist in the network yet remain indistinguishable from honest agents. Prior work by Dani et al. [7] established a worst-case framework for cooperation verification via symmetric random walks on general graphs, but was restricted to a single accusation. We generalize this framework to the multi-accusation setting on path graphs, where a strategy may accuse up to k agents simultaneously and succeeds if any accused agent is adversarial. We construct an accusation set Sk(p) with appropriately chosen p and prove that either cover time is achieved or an adversary is successfully accused in O(n^2(log n+ log δ−1) + nb^2(log n/k + 1/k log δ−1)) rounds with probability at least 1−δ. Under strict error conditions, this yields a factor-of-k speedup over the state-of-the-art single-accusation result. We further derive an optimal budget size given cost-aware applications.