MS defense: Graph-Theoretic Approach to Collusion Detection in Multi-Agent Systems

MS Thesis Defense

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

Peter Hamilton

9:00am Thursday, 28 April 28 2011, ITE 325B

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 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.

Thesis Committee:

• Dr. Marie desJardins (chair)
• Dr. Tim Finin
• Dr. Tim Oates