Thursday, May 31, 2012

liar-truther accusation graphs

One of the puzzles concerning the island of liars and truthers (#2 in the first post about these problems) involved a bunch of islanders accusing each other of lying, leaving you to sort out who was telling the truth and who wasn't.

I decided to present the solution in a truth table (in this post), but it turns out that for this kind of puzzle the answer is presented better (and found more easily) if you use a graph. For example, the graph at the top of the page (K_24,12) could represent 24 truthers, each accusing a group of 12 liars of lying - or it might be 12 truthers and 24 liars - it's hard to tell :).

Let's say you have an "accusation" puzzle, where a bunch of islanders are directly accusing each other of lying. Let each islander be represented by a vertex, and let each accusation be represented by an edge.

Note that it amounts to the the same thing if A accuses B, B accuses A, or if they both accuse each other, so it doesn't matter who accuses who - our graph doesn't need to have directed edges. The important thing to note is that if there is an accusation between A and B, then one of them must be a liar and the other must be a truther.

We want to find out who among the islanders are liars are truthers, and maybe represent this by colouring the vertices for liars one colour, and the vertices for truthers another colour. If A and B are connected by an edge this means that one of them is accusing the other of being a liar, they can't both be liars or both be truthers - so the vertices cannot be the same colour. You may see where this is going:  finding a solution to the puzzle is equivalent to finding a two-colouring of the graph.

What if in our puzzle we have some islanders "praising" other islanders - like if D says "A is telling the truth."? We might be tempted to add in a new kind of edge to represent this in our graph, but this isn't necessary. If D says that A is telling the truth, this means that both D and A must be the same - they must either both be liars or both be truthers. From the point of view of our graph, we can represent this by collapsing D and A and represent them both by the same vertex. Note that you can't have D and A accusing each other and praising each other at the same time - you get a liar paradox if you do.

Here is an example:

You meet a group of islanders and want to know whether they are liars or truthers. Alice says "Bob is a liar", Bob says "Carol is a liar" and Carol says "Bob is lying." At that moment, Dave walks up and says "Alice is telling the truth." Who are the liars and who are the truthers?

We can start by modeling the problem as a graph - with edges for "accusations" and to start with the "praise" as a dashed edge (1). Then we collapse the nodes that have a dashed edge between them (2) and finally find a 2-colouring of the graph (3).

This shows that either (a) Alice, Dave, and Carol are truthers and Bob is a liar or (b) Alice, Dave, and Carol are liars and Bob is a truther.

I think that seeing this as a coloring problem makes it more obvious what the solutions will generally look like. For example, if the puzzle hasn't "pinned" any of the islanders by saying explicitly that they are a liar or a truther, or hasn't fixed the number of liars or truthers (e.g. by saying "there are two liars" or something similar) any solution that you find will also give a "complementary" solution by reversing the colours - turning every liar into a truther and vice-versa. Also, in any puzzle where there is an accusation, the group of islanders cannot be all liars or all truthers.

In a problem like that doesn't have any islanders standing alone (i.e. not praising or accusing anyone and not being praised or accused by anyone else), if there is a solution, the graph will be bipartite. The picture at the top of this post is of a complete bipartite graph, which is what you get if all truthers are accusing all liars (or vice-versa). Here are some pictures of complete bipartite graphs, and here are some more.

A lot of liar-truther problems are not like these "accusation" scenarios. See here for more variations on the liar-truther theme.