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 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)). In the case of unknown k, we design adaptive AE strategies with maximum revealing time of order n^k−1, and we prove a lower bound of Ω(n) on the maximum revealing time of any such algorithmic strategies. This shows a strong separations between the two models of known and unknown k, as well as between the classic CGT, i.e., without selfish agents, and our game theoretic CGT model.