Liars and truth-tellers

Originally posted by Grampy Bobby
Let's visit that first sentence again. If the liars all told the truth the result would be an accurate 51/49 mix with all 49 liars identified. Wording should be "There could be 100 truthful answers if the 49 liars all lied about themselves... with no truthteller identified".


.

I think a hint would be Reveal Hidden Content.

Originally posted by LemonJello
I think your analysis makes sense. In my first pass above I was thinking of the same plan as what you outline, but I realize now I jacked up the analysis.

I do not yet see how implementing any X=Y cases will help here. We have to assume worst case scenarios; and in the scenario that X = Y and X responds "Yes", I do not see how that could give you any useful information.

I was thinking about something like the fact that we already know what the answer to a X=Y question will be because everyone will answer "yes" to an X=Y question. Anyway, after thinking about it a bit more, I don't think that that idea makes much sense, and even if it does, it only applies if you are asking everyone about a truth-teller, which doesn't seem to occur in the worst case scenario.

Thinking so far:

Choose a person A)

Ask each other person in turn : Is A a liar?

Continue until you have 51 concurrent answers, now you know what A is.

If A is a truth teller you have finished, so lets assume A is a liar

That means there are 48 other liars you haven't located yet.

Out of the people you asked "Is A a liar?", discard those who disagreed with the majority.

Lets assume that, to foil you the liars all told the truth this round, so you can discard nobody. However that means you asked only 51 people, so you have eliminated the first guy with only 51 questions. The 48 other liars could all be in your 51 concurrent answers, but you know at least 3 truth tellers must be in the 51 too.

Say 1 liar lied to you, that means you needed 52 questions to get a majority, but you can discard him, so once again you have 51 contenders, and you know only 47 liars can be in your 51, so 4 truth tellers must be there.

Similarly if two liars lie to you, you needed 53 questions but only 46 liars can be in your 51 and at least 5 truth tellers.

So an important first step in the the question is to establish the optimum liar strategy that will delay you the most.

Possibly the liars optimum strategy is for all of them to tell the truth? Does anyone agree with that?

Originally posted by iamatiger
Thinking so far:

Choose a person A)

Ask each other person in turn : Is A a liar?

Continue until you have 51 concurrent answers, now you know what A is.

If A is a truth teller you have finished, so lets assume A is a liar

That means there are 48 other liars you haven't located yet.

Out of the people you asked "Is A a liar?", discard those ...[text shortened]... the liars optimum strategy is for all of them to tell the truth? Does anyone agree with that?

Ask each other person in turn : Is A a liar?

This is not a question you are permitted to ask.

Continue until you have 51 concurrent answers, now you know what A is.

You should only need 50 agreeing answers, since there can be at most 49 lies.

Possibly the liars optimum strategy is for all of them to tell the truth? Does anyone agree with that?

I do agree with this. I think the optimal liar strategy is for the liar to tell the truth whenever the question is directed about someone else (X not equal to Y); and for the liar to lie if the question is directed about himself (X = Y). (Of course, your strategy here, like Anthem's, does not involve any cases where X = Y.)

Originally posted by LemonJello
[b]Ask each other person in turn : Is A a liar?

This is not a question you are permitted to ask.
[/b]

For the purpose this problem, asking if someone is a liar is the essentially same as asking if they are a truth-teller. Except for the 51/50 issue, it seems to me that iamatiger is giving the same solution, just explaining the optimum strategy bit in a little more detail.

Originally posted by Anthem
For the purpose this problem, asking if someone is a liar is the essentially same as asking if they are a truth-teller. Except for the 51/50 issue, it seems to me that iamatiger is giving the same solution, just explaining the optimum strategy bit in a little more detail.

Yes, of course.

Originally posted by LemonJello
[b]Ask each other person in turn : Is A a liar?

This is not a question you are permitted to ask.

Continue until you have 51 concurrent answers, now you know what A is.

You should only need 50 agreeing answers, since there can be at most 49 lies.

Possibly the liars optimum strategy is for all of them to tell the truth? Does anyone ...[text shortened]... = Y). (Of course, your strategy here, like Anthem's, does not involve any cases where X = Y.)

I think the optimal liar strategy is for the liar to tell the truth whenever the question is directed about someone else (X not equal to Y); and for the liar to lie if the question is directed about himself (X = Y). (Of course, your strategy here, like Anthem's, does not involve any cases where X = Y.)

Given the optimum liar strategy, the player should stop asking about subject A as soon as A is called a liar, and switch to asking about some subject B. In theory this might not have any value, but it will almost certainly get to a subject (say, D, or G, or M) that is a truth teller and who will be confirmed as such by fifty questions plus the few that it took to get to that subject, faster than wasting 50 questions on subject A and working the number of questions down that way. It will yield the absolute surety called for, as soon as those 50 concurrent answers are "Yes, he is a truth teller."

Of course this means there is no definite answer to the question of how many questions it will take, except that it is at least 50.

But then, the liars know the player will do this, and so they adjust their strategy accordingly!

And the player knows the liars will do this!!

And around it goes.

Originally posted by JS357

I think the optimal liar strategy is for the liar to tell the truth whenever the question is directed about someone else (X not equal to Y); and for the liar to lie if the question is directed about himself (X = Y). (Of course, your strategy here, like Anthem's, does not involve any cases where X = Y.)

Given the optimum liar strategy, the pla ...[text shortened]... strategy accordingly!

And the player knows the liars will do this!!

And around it goes.

Given the optimum liar strategy, the player should stop asking about subject A as soon as A is called a liar, and switch to asking about some subject B.

I see what you are saying. But in this problem, the player cannot assume that the liars will follow any particular strategy.

Sorry if my comments were not grounded in the proper context. I was not trying to imply that there is some "optimal" liar strategy that our hypothetical player for this problem needs to assume when he strategizes in attempt to find a truth-teller. I only meant it was an "optimal" liar strategy there in just the sense that I think it would, if adopted by the liars, delay the player the longest given that the player adopts the particular strategy that iamatiger laid out. Really, probably a better way to talk about it would be not as talk about a liar strategy, per se; but, rather, we would want to ask what is the worst case scenario that could happen to play out for the player in iamatiger's (or, symmetrically, anthem's) strategy. What is the worst way the cookie could crumble within such a strategy, so to speak? This would be the relevant question, and it does not have to assume any actual strategizing or collaboration on the part of the liars.

Originally posted by LemonJello
[b]Given the optimum liar strategy, the player should stop asking about subject A as soon as A is called a liar, and switch to asking about some subject B.

I see what you are saying. But in this problem, the player cannot assume that the liars will follow any particular strategy.

Sorry if my comments were not grounded in the proper context. I ...[text shortened]... does not have to assume any actual strategizing or collaboration on the part of the liars.[/b]

Yes, I think we should treat the liars as if they all know your strategy and collude to delay you the most (as they could randomly achieve that by chance and we are looking for the worst case).

Originally posted by LemonJello


Continue until you have 51 concurrent answers, now you know what A is.

You should only need 50 agreeing answers, since there can be at most 49 lies.

Oops, you are quite right! Thanks

Originally posted by iamatiger
Yes, I think we should treat the liars as if they all know your strategy and collude to delay you the most (as they could randomly achieve that by chance and we are looking for the worst case).

Yes, I think some element of randomly telling a lie about Y when Y is a truther, would delay the game the longest. I suppose we could discuss the optimal random pattern, but 😴 it's a job for some game theory graduate student.

I don't think game theory is very helpful here. The question is about what is the strategy that minimizes the maximal number of questions, so it's like LemonJello said, assuming the worst case scenario (WCS). That means that the strategy plays virtually no part. Imagine that they say the truth in 0.1^10000000000000 of cases. Can you use this information for a WCS? Not really, in the WCS you could still be extremely unlucky, so whether they say the truth half of the time or extremely rare makes no difference for the question asked.

So as far as I see it, Anthem's answer seems correct.

Originally posted by Palynka
I don't think game theory is very helpful here. The question is about what is the strategy that minimizes the maximal number of questions, so it's like LemonJello said, assuming the worst case scenario (WCS). That means that the strategy plays virtually no part. Imagine that they say the truth in 0.1^10000000000000 of cases. Can you use this information for ...[text shortened]... difference for the question asked.

So as far as I see it, Anthem's answer seems correct.

It may make a difference if you keep records and use the answer to decide whether to switch whom you ask about.

We have assumed that each of the liars wants to delay the player's success and the worst case for the player is when they all tell the truth about each other. This makes the situation one in which game theory IS being applied, such that the solution is designed to address this delay strategy IF it is used.

I suggested that when this delay strategy IS being adhered to, then a modification -- switching from subject A to subject B and so on, if and when the current subject is called a liar -- has the potential to reduce the number of questions needed and has no potential of increasing it. I believe this can be easily demonstrated.

But the "Anthem plus switching" strategy may not be optimal against other delaying strategies, say, one in which a liar uses a random process that has him lie on average, 1% of the time.

In this case, using the switching rule, the player may pass by subjects who are truthers and run through all 100 of the people in the room without identifying one as a truther.

This gets into a complicated scenario where the player keeps records of what each person has said about each subject, so he can pick up where he left off, eventually getting to 50 people saying a given person is a truther, at which point the player is done. It's a messy scenario. Can it be proven that there is no liar strategy that makes the Anthem plus switching rule worse than the plain Anthem strategy? I don't know, and it is likely I never will. One thing for sure; the number of questions needed in the A+S questioning strategy is indeterminate.

The poser is posed as if there is a determinate solution. So I like Anthem's solution, too. 🙂

Originally posted by JS357
It may make a difference if you keep records and use the answer to decide whether to switch whom you ask about.

We have assumed that each of the liars wants to delay the player's success and the worst case for the player is when they all tell the truth about each other. This makes the situation one in which game theory IS being applied, such that the solut poser is posed as if there is a determinate solution. So I like Anthem's solution, too. 🙂

If the question was what's the best strategy IN EXPECTATION, then it would matter. But that's not the question, the question asks for the minimum of the maximum number of questions of all possible strategies of the person asking (minimum in the WCS)

But for a WCS, no assumption is required of the strategy of the liars. No use of the probability of lying is needed, nor does it change the analysis. Whether they lie 1% or 50% or 99% of the time, a worst case scenario cares not for the exact percentage*. It will always be the question that gives him less information (in this case, asking about a liar) and the answer that provides least information (in this case 'No'😉. So for a WCS, it doesn't get complicated at all.

*Only if it's 100% or 0% and the person knows this with absolutely certainty and there's no possibility of deviation. Then it makes a difference (reducing the number of questions to (50+48: finds a liar then uses him to find a truth-teller) in the 100% case or 49 in the 0% case.

Originally posted by Palynka
If the question was what's the best strategy IN EXPECTATION, then it would matter. But that's not the question, the question asks for the minimum of the maximum number of questions of all possible strategies of the person asking (minimum in the WCS)

But for a WCS, no assumption is required of the strategy of the liars. No use of the probability of lying i ...[text shortened]... finds a liar then uses him to find a truth-teller) in the 100% case or 49 in the 0% case.

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.