PAIR Auditing Pairs for AI Agent Collusion

Collusion can leave evidence across two agents while each individual record appears innocuous. A monitor that reports only per-agent coverage can therefore overstate its ability to collect actionable evidence. We study how audit correlation changes detection under an exact record budget and identical marginal coverage for every agent. PAIR applies a standard max-min linear program to the joint inclusion probabilities of a specified interaction graph. For eight agents and two audits per round, four feasible disjoint pairs obtain 25% joint coverage, compared with 3.57% under uniform fixed-size sampling. The same policy reduces coverage when either record alone suffices. We derive the exact reversal: under equal marginals and a mixture of joint-only and single-record evidence, pairing helps precisely when the joint-only fraction exceeds one half. In 40 shared- controller bandit runs per condition, the higher coverage deters attacks in a deliberately selected incentive regime. However, allowing migration to unmodeled pairs or revealing the realized audit draw defeats the specialized policy. A uniform hedge restores a measurable coverage floor but does not guarantee deterrence. These are synthetic allocation results, not evidence of emergent LLM collusion or a validated semantic detector. The contribution is a reproducible evidence-aware benchmark and explicit limits on when correlated auditing is beneficial.