Combinatorial Group Testing with Selfish Agents

We study the Combinatorial Group Testing (CGT) problem in a novel gametheoretic framework, with a solution concept of Adversarial Equilibrium (AE). In this new framework, we have n selfish autonomous agents, corresponding to the elements of the universe [n] = {0, 1,..., n 1}, and a hidden set K [n] of active agents of size |K| = k n. In each round of the game, each active agent decides if it is present in a query Q [n], and all agents receive some limited feedback on Q K. The goal of each active agent is to ensure that its id could be revealed from the feedback as early as possible. We present a comprehensive set of results for this new game, where we design and analyze adaptive algorithmic strategies of agents which are AE's. In particular, if k is known to the agents, then we show adaptive AE strategies with provably near-optimal maximum revealing time of O(k log(n/k)).