Combinatorial Group Testing with Selfish Agents

We study the Combinatorial Group Testing (CGT) problems 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.