unfinished ideas

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.

The Rules of the 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:

1. Townies labeled spies by townies are eliminated, as are the townies that labeled them.
2. Spies labeled spies by townies are eliminated.
3. Spies that labeled a townie a spy are eliminated.
4. Spies that have not identified any of the remaining spies are eliminated; this step is repeated until the set of spies no longer changes.

At each step, already eliminated players don’t count; a spy can’t be eliminated by mislabeling an eliminated townie. If there are still spies, they win. If there were townies left but not spies, the townies win. If everyone was eliminated, it’s a tie.

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?