Liars and truth-tellers

Originally posted by JS357
It just nags at me that there is so little use to be made of the information gained during the questioning, under the WCS, other than "possibly, they are using the WCS." But unless I come up with something, I'm OK with Anthem's approach being the best proven.

Yeah, I know what you mean... The problem is that in the WCS you always get the same answer ('He is not a truth-teller'😉 from anyone you ask (which will always be liars) about any of the people you ask about (which will always be liars).

We could always pose a second question and ask what is the best strategy for both parties if there is a game between asker and liars to minimize/maximize the expected number of questions... We've seen it's not 100% truth or 0% truth. Let's call P = (P_L,P_T) the strategy that gives a probability of lying when the question is about a liar (P_L) or a truth-teller (P_T), and supposed for now they commit to those strategies. Can we find an optimal strategy for the asker that minimizes the EXPECTED number of questions asked?

Originally posted by Palynka
Yeah, I know what you mean... The problem is that in the WCS you always get the same answer ('He is not a truth-teller'😉 from anyone you ask (which will always be liars) about any of the people you ask about (which will always be liars).

We could always pose a second question and ask what is the best strategy for both parties if there is a game between as nd an optimal strategy for the asker that minimizes the EXPECTED number of questions asked?

A probabilistic approach...

If you have lost interest in this, I understand. This is about my last posting on this topic, because delving much further will require tedious math work. But after thinking about it I want to include this idea, because it will mean I can't worry it further. 🙂

I am thinking about a strategy which is immune to the values of P_L and P_T, I think.

Number the people 1 to 100, and pair them off 1 and 2, 3 and 4, etc, on paper. You don't have to tell them they are paired or about the pairing scheme. Ask the odd numbered people about the even numbered; 1 about 2, 3 about 4, etc. Don't ask 2 about 1, 4 about 3, etc. just yet.

If, in any pair, the person you ask calls the other a liar, cross out BOTH of that pair, don't pair them with anyone again, and don't ask either of them from now on. They are both done for the day. They don't have to be told this -- you just won't ask either of them again.

For any pair crossed off, you have avoided asking the next question, which is, what the even-numbered person has to say about the odd-numbered person. Do this with the survivors, and repeat the crossing-off of any pair where the odd-numbered person is called a liar.

This seems counterintuitive because you are crossing off truthers, but you have two extra of them. Two truthers have to be paired up with each other, and so will survive the round. So will any additional paired-up truthers -- and so will any paired up liars, but only if they both lie about each other and call each other truthers.

Now, before starting the next round, redo the pairing systematically.* Renumber reductively (eliminating gaps) and pair 1 with 4, 2 with 5, and so on. Basically you rotate the pairing wheel two spaces from the previous, after renumbering. This process will certainly, at least eventually, separate some previously paired liars and put them with truthers. (I don't know if this can be quantitatied or estimated easily). Those liars are doomed (along with their paired truthers). You still have two extra truthers that will be paired with one another -- they might be different truthers this time -- so at least one pair of truthers will survive, again.

You are using the truthers to 'out' the liars, and you have truthers to spare. Getting rid of truthers you no longer need, also reduces the number of questions you need to ask in future rounds.

Because you are always eliminating pairs, you always have an even number to pair up. In principal on average, in each round this will cut the number of people left, about in half. Of course it could in principle take longer, if it were possible that all the truthers get paired to each other and all the liars get paired to each other, and the liars lie about each other. But the pairing system -- practically, if not easily provably, -- prevents that.

There is always a surplus of at least two truthers. When it gets down to, say, 4 and 2, or 6 and 2, the 2 liars will soon enough be paired with truthers and will be gone, and then the truthers will confirm each other as such by pairing each with each of the others in a final round or so.

Other than simulation, I would not know how how to compare this to other strategies that test various settings of P_L and P_T including 100 and 0%. But it has elements that actively trim the number of future questions needed, even during a round.

OK that's it. Like I said, I'm not about to do the math. It satisfies my desire that the information gained be more useful.

* The renumbering might preferably be random, followed by a fresh 1 and 2, 3 and 4 pairing etc. A refinement to the pairing system could be that if any two people are re-paired, skip questioning them in the round, then re-randomize.

Originally posted by JS357
A probabilistic approach...

If you have lost interest in this, I understand. This is about my last posting on this topic, because delving much further will require tedious math work. But after thinking about it I want to include this idea, because it will mean I can't worry it further. 🙂

I am thinking about a strategy which is immune to the values of P_ any two people are re-paired, skip questioning them in the round, then re-randomize.

Cool strategy!

Assume the liars always say the other guy tells the truth (best they can do)

your worst case pairs (each is paired with the one below) is
LLLLLLLLLLLLLLLLLLLLLLLLLTTTTTTTTTTTTTTTTTTTTTTTTT
LLLLLLLLLLLLLLLLLLLLLLLLTTTTTTTTTTTTTTTTTTTTTTTTTT

(the LT in the middle is eliminated, 50 questions
moving the top row forward one step (and carrying the last guy back round to the start) we get the pairings:
TLLLLLLLLLLLLLLLLLLLLLLLLTTTTTTTTTTTTTTTTTTTTTTTT
LLLLLLLLLLLLLLLLLLLLLLLLTTTTTTTTTTTTTTTTTTTTTTTTT

so this time you eliminate 2 pairings with 49 more questions
now we have

TLLLLLLLLLLLLLLLLLLLLLLLTTTTTTTTTTTTTTTTTTTTTTT
LLLLLLLLLLLLLLLLLLLLLLLTTTTTTTTTTTTTTTTTTTTTTTT
So I think the number left decreases by 2 first and thereafter by 4:
100, 98, 94, 90 ... 2

And the number of questions on each round decreases by 1 first and 2 thereafter:
50, 49, 47, 45 ... 3

(we can miss the last question out because we know by then that there are two truth tellers left)

So I think your worst case num questions is (3 + 49)*12 + 50 = 674

Considering the plan to ask everyone "does A tell the truth" until you have 50 agreeing answers.

It looks like this takes 50 questions to eliminate 1 person (a liar)
then 49 questions to eliminate another one, then 48 questions etc, with 2 questions to eliminate the final liar. So I reckon it takes

(2+50)*49/2 = 1274 questions, this strategy takes almost twice the questions and is therefore much worse!

Originally posted by JS357
A probabilistic approach...

If you have lost interest in this, I understand. This is about my last posting on this topic, because delving much further will require tedious math work. But after thinking about it I want to include this idea, because it will mean I can't worry it further. 🙂

I am thinking about a strategy which is immune to the values of P_ any two people are re-paired, skip questioning them in the round, then re-randomize.

Very nice! More evidence that skepticism is good. 🙂

Originally posted by iamatiger
Considering the plan to ask everyone "does A tell the truth" until you have 50 agreeing answers.

It looks like this takes 50 questions to eliminate 1 person (a liar)
then 49 questions to eliminate another one, then 48 questions etc, with 2 questions to eliminate the final liar. So I reckon it takes

(2+50)*49/2 = 1274 questions, this strategy takes almost twice the questions and is therefore much worse!

Thanks to you and Palynka for the comments. Of course the skeptic in me awaits a disproof or better system being announced.

674 is a useful figure as it allows WCS comparisons. But it is a figure that could be achieved by a pairing system that can be made impossible. It would be equivalent to letting the people in the room pair themselves and telling them the elimination rule that will be used.

As suggested, a systematic or semi-systematic pairing method, will, I think, prevent the liars uniformly pairing up with liars and the truthers uniformly pairing up with truthers on subsequent rounds. For example, the first round uses random pairing. In the second round, now pairing N people, you can pair #1 and #N, #2 and #(N-1), etc. Then randomly pair in the next round, or use a different systematic pairing method. This would cause the elimination process to proceed more rapidly than in the WCS.

Because we don't know what the lineup of true identities of the persons we pair each time, it seems a little daunting to prove the above paragraph is true. But it feels true. 🙂

Originally posted by JS357
A probabilistic approach...

If you have lost interest in this, I understand. This is about my last posting on this topic, because delving much further will require tedious math work. But after thinking about it I want to include this idea, because it will mean I can't worry it further. 🙂

I am thinking about a strategy which is immune to the values of P_ ...[text shortened]... any two people are re-paired, skip questioning them in the round, then re-randomize.

Nice strategy.

Originally posted by JS357
Thanks to you and Palynka for the comments. Of course the skeptic in me awaits a disproof or better system being announced.

674 is a useful figure as it allows WCS comparisons. But it is a figure that could be achieved by a pairing system that can be made impossible. It would be equivalent to letting the people in the room pair themselves and telling them t ch time, it seems a little daunting to prove the above paragraph is true. But it feels true. 🙂

This could be right:

I said you started off (after out random paring) with
AAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBB

(I have replaces L and T with A and B because they are the same width in pixels, at least on my screen)

After the non matching pair in the middle is removed, this gives:
AAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBB

And I was rotating the top guys only one place to the right, which didn't move the As and Bs apart much...

It looks like I could have done much better by rotating them 25 to the right, to give:
BBBBBBBBBBBBBBBBBBBBBBBBBAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBB

which would have solved the problem immediately.

It could be, that when you are left with an odd number of pairs after a match and trim you can rotate by N/2 (rounded up) to the right, and you will solve the problem.

Can anyone find a "worst" configuration of truth tellers and liars that would lose only one pair at the start and could not then be completely solved with a rotation by 25 to the right?

Possibly if you have an even number of pairs after a trim you have to rotate by N/2 + 1 where N is the number of pairs.

The idea is that, once we have a set of matched liars and truth tellers (all the mixed pairs have been removed then:

Using 1A for the first person in pair 1, and 1B for the other person in Pair 1:

Because the pairs match, 1A = 1B, 2A = 2B .. nA = nB
Assuming there are N pairs (odd)

Take N/2 and round Up, then add that to the number of the first person in each pair
(take away N if this takes the number over N)

for example, say there are 49 pairs, we add 25 to all the As

So person 1A now matches against person 26 B, if this is a "worst case" they are the same type (which means they won't be thrown out in the next questioning round). So 26A = 26B = 1A = 1B.
But we added 25 to 26A too, which takes us to 51, so we subtract 49 meaning that 26A now matches against 2B and for a "worst case" they must be the same too.

So 26A = 26B = 1A = 1B = 2A = 2B

we can continue this logic, to prove that in the "worst case" everyone equals everyone else!
This is clearly false. Therefore there is no "worst" case possible after a shift of N/2.

Therefore (I think) at least half of the liars will not match with other liars, and we will be able to throw them out on this round.

I quite fancy simulating this scheme as my next step.

I'm not sure I understand... Why does moving 1 or 25 make a difference? The ordering we have is just expositional, isn't it? Nothing differentiates the pair to my right from the pair 25 places to my right. Or maybe I'm missing something?

Apologies if I'm being thick here.

Originally posted by Palynka
I'm not sure I understand... Why does moving 1 or 25 make a difference? The ordering we have is just expositional, isn't it? Nothing differentiates the pair to my right from the pair 25 places to my right. Or maybe I'm missing something?

Apologies if I'm being thick here.

I think there is not a specific number of spaces to rotate the pairings, that ends the game at round 2 for all arrangements of A’s and B’s.

I'm going with 11 A’s and 9 B’s out of laziness.

Look at the following:

ABABABABAB
ABABABABAA

Becomes:
ABABABABA
ABABABABA

Now arranged in a circle, we can see that there are two A's next to one another, at positions 1 and 9:

A rotation of one space will create 8 AB pairs, ending the game, as follows. So will a rotation of 3, 5, 7, or any odd number.
ABABABABA
AABABABAB

But a rotation of 2 spaces will only create 2 AB pairs, so will a rotation of 4, 6, 8, or any even number.
ABABABABA
BAABABABA

You get the opposite sort of result from the following:

AABBAABBAA
AABBAABBAB

becomes
AABBAABBA
AABBAABBA

Now arranged in a circle, we can see that there are three A's next to one another, at positions 1, 2 and 9.

In this case, a rotation of 1 space will only create 4 AB pairs, so will a rotation of 3, 5, 7, or any odd number:
AABBAABBA
AAABBAABB

But a rotation of 2 spaces will create 8 AB pairs, ending the game. So will a rotation of 4, 6, 8, or any even number:
AABBAABBA
BAAABBAAB

So I think there is not a specific number of spaces to rotate the pairings, that ends the game at round 2 for all arrangements of A’s and B’s.

Alternating odd and even rotations from round to round might be best.

Originally posted by JS357
I think there is not a specific number of spaces to rotate the pairings, that ends the game at round 2 for all arrangements of A’s and B’s.

I'm going with 11 A’s and 9 B’s out of laziness.

Look at the following:

ABABABABAB
ABABABABAA

Becomes:
ABABABABA
ABABABABA

Now arranged in a circle, we can see that there are two A's next to one another, ents of A’s and B’s.

Alternating odd and even rotations from round to round might be best.

Sorry, I still don't see how it matters, we're still talking WCS here, right? Take a final configuration, if one chooses carefully the place where to put the (eliminated) LT pair, I think one can reverse engineer for any step size and get an original configuration where all the remaining pairs are all LL or TT. So there's always the possibility that your rotation will end up with only 1 eliminated pair...

Originally posted by Palynka
Sorry, I still don't see how it matters, we're still talking WCS here, right? Take a final configuration, if one chooses carefully the place where to put the (eliminated) LT pair, I think one can reverse engineer for any step size and get an original configuration where all the remaining pairs are all LL or TT. So there's always the possibility that your rotation will end up with only 1 eliminated pair...

I'm not sure what the dispute concerns. Is "final configuration" the arrangement of Ls and Ts after a round has been completed and all but the pairs of people reporting "TT" about one another have crossed off the list? If you add back only one LT pair to it, of course that one pair would have been the only one eliminated in that round.

Originally posted by JS357
I'm not sure what the dispute concerns. Is "final configuration" the arrangement of Ls and Ts after a round has been completed and all but the pairs of people reporting "TT" about one another have crossed off the list? If you add back only one LT pair to it, of course that one pair would have been the only one eliminated in that round.

Yes, but that I can find one means that it exists so it could be the WCS...

AABBAABBA
AABBAABBA

That is 9 pairs
9/2 rounded up - 5

move the top row 5 places right
AABBAAABB
AABBAABBA

yes, 4 got rid of, now this looks bad, but actually it is quite good!

to show this, lets try with 21 pairs:
AABBAABBAABBAABBAABBA
AABBAABBAABBAABBAABBA

21/2 rounded up = 11, so move 11 places to the right:
BBAABBAABBAAABBAABBAA
AABBAABBAABBAABBAABBA

here we got rid of 16 pairs. Why is this good? Consider 21 arranged like this:

ABABABABABAABABABABAB
ABABABABABABABABABABA

here we still get rid of 10 pairs, this is because the shift of 10 is not particularly sensitive to the ordering, which is what is good about it.

I think a rotation of ceiling(N/2 + 1/2) to the right is optimum because it gets rid of at least half (rounded down), whatever the order. Therefore it will have the lowest "worst case".