Combinatorial Group Testing with Selfish Agents

We study the Combinatorial Group Testing (CGT) problem in a novel game-theoretic framework, with a solution concept of Adversarial Equilibrium (AE). In this new framework, we have n selfish agents corresponding to the elements of the universe [n] \{0,1,\ldots,n-1\} and a hidden set K \subseteq [n] of active agents of size K k \ll n . In each round of the game, each active agent decides if it is present in a query Q \subseteq [n], and all agents receive feedback on Q \cap K . The goal of each active agent is to assure that its id could be learned from the feedback as early as possible. We present a comprehensive set of results in this new game, where we design and analyze adaptive algorithmic strategies of agents which are AE's.