Can you find out who knows the secret without revealing it?
Part of my current research involves considering how agents can benefit from cooperation even when some agents are malicious. Thinking about that problem led me to design the following game.
There are a fixed, known number of players in the game, p. Each player is either a spy or a spy-hunter. The players do not know who is what, though they do know s, the total number of spies in the game. The t = p – s other players are called townies. Each spy knows the same password, taken from a set of n possible passwords; all of the players know what that set is.
Each round of play each player sends a secret message to one other player. This message consists of just a single password, and only the sender and recipient know who received it. The recipient they replies with a single password. There is no other communication possible.
After some number of rounds of play, each player submits a list of which other players are spies and which are townies. We then proceed to eliminate players:
Who has the advantage if there are zero rounds of play? How should spies decide if they send the real password or a fake? How does anyone decide if they reply with the same password they received or not? Does having more spies than townies help or hurt the spies?