Efficient pooling against strategic adversary with applications in anonymous and reliable networking

In many anonymous peer-based networking schemes, it is difficult to identify adversarial participants who drop or corrupt packets they are supposed to forward. This paper considers a pooling problem which models the strategic interaction between an adversary and a sender who chooses relay nodes from a pool of participants, a subset of which is controlled by the adversary. The sender adaptively chooses sets of relay nodes over a number of rounds, while the adversary chooses whether or not to attack in rounds where adversarial nodes are chosen. We introduce a class of strategies, called random pooling strategies, over which it is tractable to optimize and whose performance is within a factor of 1.4 of the optimal strategy when the number of adversaries is given.