Original problem statement
Consider a game played with 12 people. 9 are randomly assigned to Team Good and 3 to Team Evil. Players on Team Evil know their teammates, but players on Team Good don't. Two of the players on Team Good are secretly assigned devices with red and green buttons on them. Gameplay proceeds as follows:
- All of the players talk publicly with each other.
- The two players with buttons each secretly choose one to press.
- The three players on Team Evil reveal themselves, and collectively guess one player who they believe has a device with buttons.
Team Good wins if Team Evil's guess was incorrect and the buttons pressed were different colors. Team Evil wins if their guess was correct or the buttons pressed were the same color.
What strategy should Team Good use to maximize their winning chances?
Besides the point but I'd like to point out that the qualifiers "good" and "evil" are arbitrary. In that scenario, "Team Good" could be a group of terrorists trying to detonate a nuclear device in a kindergarten and "Team Evil" could be a group of undercover parents trying to prevent that from happening. So calling the first team "Good" just tells on which side you are. These are just two teams with opposing goals.
The probability of success for Team Good is
6/11 * 7/9 = 14/33 ~= 42%.
Since the bad guys already know each other, they have two objectives:
1. Find one button holder among the known good guys by detecting any attempt to communicate which button they would press.
2. Prevent coordination between button holders by interfering or mislead them into getting the wrong information.
The button holders would have the following objectives:
1. Provide information for the other button holder regarding what button they will press,
2. Figure out what the other button holder will press.
3. Minimize information revealing they are a button holder.
Now, if the button holders behave differently than the other good guys, that can help the other button holder to decide which button to press. But the bad guys can mimic the behaviour of a button holder. The buton holders don't know who is who, so they can be misled and get the wrong information. The bad guys on the other side won't be mislead and will get reliable information to uncover the button holders. Leaking information about who has the buttons is a small advantage for Team Good but a larger advantage for Team Evil. Therefore Team Good must act in a way that doesn't reveal who has the buttons.
The simplest strategy would be for the button holders to just press a random button and otherwise act like any other good guy. This gives a success rate of 1/2 for pressing different buttons and 7/9 for not being picked by the bad guys who have no clue. This is a success rate of 1/2*7/9 = 7/18 = 38.88% overall.
But a better strategy is to split the players randomly in two groups of 6, one being instructed to press the red button, the other to press the green button. This way, the probability of the two button holders being in different groups, and therefore pressing different colors, is 6/11, slightly better than 1/2. And the bad guys are not the wiser. The success rate for Team Good becomes 6/11 * 7/9 = 14/33 = 42.42%.
It is important that it is not a bad guy who forms the red and gree groups, because if he puts all good guys in the same team, the probability to press a different color drops to 1/2. So it must be done in a way everybody is confident that the assignment has been done impartially.
I don't know if that is optimal, but it is the best I can come up with. And 42% always looks like a good answer.
Objections and correction.
A valid objection by JS1 is that Team Evil can do better than just pick one of the 9 Team Good members. Team Evil only needs to find a button holder when the button holders succeed in pressing different buttons. That means that Team Evil can assume there is one button holder in each color group when it matters. With that knowledge it is better to pick one good guy from the smaller color group. They can uncover a button holder with probability 1/3 or 1/4 depending on the distribution (3+6 or 4+5).
The overall probability to uncover a button holder is tricky. You have to figure the probability of each distribution to happen, given that they succeeded in pressing different buttons, then apply the rate above.
I am not sure how to compute that properly. I ran a computer simulation and found the same success rate of 40.15% as JS1 and Retudin. That should be the correct answer.
Retudin wonders whether Team Evil can bias the choice of colors towards 3/0 for Team Evil. I think that if colors are chosen randomly by picking marbles from a hat Team Evil cannot introduce a bias. Whoever objects that method only reveals himself to be evil. The remaining players can then split between red and green producing on average a more equal split.