Poster
Combinatorial Group Testing with Selfish Agents
Georgios Chionas · Dariusz Kowalski · Piotr Krysta
Great Hall & Hall B1+B2 (level 1) #1701
Abstract:
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 selfish agents corresponding to the elements of the universe and a hidden set of active agents of size . In each round of the game, each active agent decides if it is present in a query , and all agents receive feedback on . 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. In particular, if is known to the agents, then we design adaptive AE strategies with provably near optimal learning time of . In the case of unknown , we design an adaptive AE strategies with learning time of order , and we prove a lower bound of on the learning time of any such algorithmic strategies. This shows a strong separations between the two models of known and unknown , as well as between the classic CGT, i.e., without selfish agents, and our game theoretic CGT model.
Chat is not available.