Propositional Logic and Social Deduction Games

Abstract: In this post, we introduce how propositional logic can be used in social deduction games. In the first part of this post, a brief overview of propositional logic is given, along with some more advanced ideas that are useful. In the second part an overview of The Resistance is given, followed by how propositional logic can be used to assist deduction in the game.

Propositional logic, sometimes referred to as propositional calculus, is a branch of logic that deals with statements or propositions, and the relationships between them. Using these prepositions and relationships we can build arguments, which can then tell us about more about the situation that we are in.

To start lets define a proposition. Loosely define, a proposition is a statement that can be evaluated to some truth value, that being either true or false. For example, the following statement is a proposition: “Bill Gates is the president of the United States.” It is a proposition, because the statement is either true or false, and in this instance it’s false. One of the tricky things for people who are unfamiliar with logic, is that statements don’t have to be true. This can be seen in our example above, as, at least at time of writing, Bill Gates is not the president of the US.

Let’s also look at an example of something that is not a proposition: “Is it hot outside?” Because there is no way to determine if that phrase was true of false, it is not a proposition.

Generally, when working in logic, we tend to reduce full statements to symbols. For example if we had the following preposition: “Paris is the capital of France” we assign this proposition the following symbol – P. Then, when working with this proposition, instead of writing the full proposition, we would simply write it as P.

The second thing we need to discuss when dealing with propositional logic are a couple of operators that we can use when working with propositions.

The first, is the negation operator. In logic, it is written as: \neg. Essentially, this operator flips the truth value of a given proposition or formula. For example, the truth value of the following formula (P), where P is our proposition from earlier, is true. This is because, Paris is the capitol of France. However, if we use the negation operator we get the following formula: \neg(P). Because the negation operator flips the truth value of our formula, this new formula evaluates to false.
The second operator we need to discuss is the conjunction operator, often written as: \land. Intuitively, we can think of this operator as the “and” operator, in that it joins to propositions together. In order for conjunction of two statements to be true, both of them must be true. For example, let L represent the following proposition: “Lyon is the capitol of France.” If we conjoin our two established propositions, we get the following formula (P \land L). To evaluate the truth value of this expression, we must first evaluate both expressions joined by the conjunction. As mentioned earlier, we know P evaluates to true. Unfortunately, the second part of this expression L evaluates to false, as obviously Lyon is not the capitol of France (it’s Paris). Because one of the sides on the conjunction does not evaluate to true, the entire conjunction evaluates to false. However, if we change the expression to the following (P \land \neg L), the expression evaluates to true.
The following operator we need for this post (there are other operators) is the disjunction operator, often written as: \lor. It is similar to the conjunction operator, in that is used to join to expressions together, however, unlike the conjunction operator, only one of the two expressions need to evaluate to true, for the full statement to evaluate to true. In English we can think of this as the “or” operator. For example, if we have the expression (P \lor L), this expression will evaluate to true. This is because P evaluates to true, and by definition of disjunction, only one of the two expression needs to be true for the disjunction to be true.
Finally, we will use all of the describe rules in a single example. To do so, lets introduce a third proposition. Let G represent the following statement: “France and Germany share a boarder.” The truth value of this statement is true. Then, using these three propositions, and our defined operates we can generate the following expression: (\neg P \lor (\neg L \land G)). Lets evaluate this expression, and do so in its nested order. Starting with \neg L \land G, we can see that this evaluates to true, as the negation of L is true, and G is also true. Since that expression is true, we can then say the entire expression is true, as we have a conjunction between a true expression and the negation of P (this is false). Therefore the entire expression is true.

Now that we have fully discussed all of the propositional logic needed, we can move on to our discussion of its uses in social deductions games. As mentioned above, we will be using propositional logic to analyze The Resistance. Before beginning this analysis, let us first discuss The Resistance.

The Resistance is a social dedication game for 5-10 players, released in 2009, and designed by Don Eskridge. In it players, take on the roles of resistance operatives seeking to destroy the oppressive empire. However, not all is as it seems, as some players will be imperial spies, working to stop the resistance. The game is played in three to five rounds, in which players are chosen to go on “missions.” If any of the imperial spies are on the mission, they can secretly choose to fail the mission. However, if no spies are on the mission, or the spies decide not to fail the mission, then the mission succeed. The first team to have three missions go there way wins. (For full rules of play, click here).

The main reason we are using The Resistance as our main example, is that the games mechanics are very easy to turn into prepositions, and analyze in preposition logic. Lets give an example. In this example we will assume 5 players, with the following names: Alice, Bob, Cody, Duke, Evelyn, with Bob and Duke being the spies. In the first round Alice, elects Duke and herself to go on the mission, and the mission succeeds. Because spies can chose to fail the mission, we are unable to gain any information from that round. However, in the second round Bob elects himself, Alice and Evelyn on the mission, and the mission fails. Because this mission failed, and resistance members can not fail the mission, we know their is at least on spy on the mission. There we can write the following preposition:

A \lor B \lor E

In this instance each proposition represents the following statement, with whoever’s first letter in their name is shared by preposition symbol: {Name} is a spy. In the third round, Cody elects himself and Alice to go on the mission, and the mission succeeds. In the fourth mission, Duke elects himself, Alice, and Evelyn to go on the mission. Unfortunately, this mission fails, allowing us to write the new proposition.

(A \lor B \lor E) \land (A \lor D \lor E)

It is important to note that there is also another section this proposition, that for sake of readability is not included here. That is the proposition that states that two unique players are both spies. Because writing this out would require writing all 10 unique two player pairs, we will instead imply it in our analysis.

In the final round, Evelyn attempts to choose a party, but due to being part of both failed missions, her party is turned down. For the final mission, Alice chooses herself, as she knows she can be trusted. She also decides that she trusts Evelyn, in part because her party was turned down. This leaves her with one final choice for the team, and she is unsure who to pick. However, we can use prepositional logic to figure out which is the correct choice. As Alice, we know that we are not a spy, and therefore can add that clause to our expression. Because we are picking Evelyn for the mission, we should assume that she is not the spy, adding a fourth clause to our expression, and giving us the following expression:

(A \lor B \lor E) \land (A \lor D \lor E) \land (\neg A) \land (\neg E)

To figure out who the final resistance member is, we can simplify this expression. Because we have both a neg Alice and neg Evelyn, clause that are both conjected with all other clauses, we can assume that both of those propositions must be false. Doing so, allows us to cancel out any other instances of them, in which they are required to be true. Doing so simplifies our expression to the following:

(B) \land (D)

Now that we have simplified, we can see who the two spies must be – Bob and Duke! As such Alice now knows that Cody, is the final real resistance member, and can win the game!

Final Thoughts and Conclusion: In this post, I have shown how propositional logic can be used in social deduction games. However, there are some important things to discuss about this. Although the example given here is rather simple, this same paradigm can be applied to games with more players, and assuming the rules of logic are followed, can be used for proper deduction. A future post may be written looking at more involved examples, as well as introducing two new operations.

It is important to note that you cant always use propositional logic to figure out who is a spy and who is not. For most cases, the ability to do so with be based on one or two assumptions, that are made through social deduction, not logic. The main reason for this, is that game designer want to ensure that players are interacting with each other, not solving logic puzzles.

This is however an interesting side problem to look at, mainly are there any instances in which the full game can be “solved” without making any assumptions. This will likely be looked at in a future post.

Published by Freddy_Reiber

Undergrad student at UCI. Running a blog on how to use Computer Science to win in modern board games.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: