A Graph-Theoretic Approach to Collusion Detection in Multi-Agent Systems

The study of trust and cooperation is a major component of multi-agent systems research. Such work often focuses on how best to estimate the reliability of a specific agent, or how to create strategies and protocols that engender the most cooperation from the most agents. However, when cooperation is not a desired aspect of a multi-agent system, these actions define collusive behavior, which can have a significant impact on the dynamics of the system. This thesis defines a generic, graph-theoretic approach to collusion detection known as Collusion Detection using Interaction Graphs (CODING). This approach detects group-based collusion, targeting two basic collusion mechanisms that rely on large numbers of colluding agents for success. CODING analyzes and classifies agent interactions from the system and constructs a series of interaction graphs from this data. These graphs are processed for structures that correspond to collusion mechanisms; the agents composing these structures are reported as colluders. CODING is applied to a game theory domain, in which it must detect agents adhering to group strategies in round-robin tournaments composed of single-player strategies