Quickest algorithm to find at most (n/2)-1 liars in n people

Question

Here is my scenario:

This problem is couched in terms of liars and truth tellers, but it has real applications in identifying which componants of a complex system are good (functioning correctly) and which are faulty. Assume we have a community of n people and we know an integer number t < n/2, which has the property that most t of the n people are liars. This does not say that there actually are t liars, but only that there are at most t liars.

I assume that the truth-tellers are always truthful and correct and a liar may tells the wrong answer or right answer.

We will identify the liars in the community by successively picking pairs of people, (X, Y ) say, and asking X: Is Y a liar?. The response is either “yes” or “no";

What is the optimum algorithm(minimum number of steps) to find all the liars?

Answer 1

You state that a liar may tell the truth or may lie. This seems to me to make the problem a difficult one. I offer a solution in the special case where a liar always lies.

Let G be the group of interest. Choose an arbitrary member of the group, X say. Observe that the procedure of asking X "is Y a liar?" yields an answer of "no" if X and Y are both truth-tellers or if both are liars, and an answer of "yes" otherwise. Thus by asking X "is Y a liar?" for each Y in G (excluding X), you can find out which members Y are on the same "team" as X. From the fact that there have to be more truth-tellers than liars, this allows you to identify which "team" X is on, after which it is simple to identify the liars.

Answer 2

Random algorithm with optimal expected running time of O(n) and excellent constants:

1. Select at person at random
2. Ask the rest of the people whether he's a liar, until one option (either "yes" or "no") has weight > n/2 (i.e. until more than n/2 people gave the same answer).
   Majority decides (this is the key observation!).
3. If he is not a liar, then iterate over the remaining people and ask only him whether or not each person is a liar (since we determined that he tells the truth).
4. If he is a liar, take him out of the group and go back to 1.

The key observation is that if we ask everyone about a single individual the majority opinion will have to be correct (since there is a majority of truth tellers). A slight technicality is if we pick a non-liar first and ask everyone else, assuming all liars lie, we will reach a 50-50, so how do we decide which side is telling the truth? That isn't a problem, since we can only reach a 50-50 if we picked a non-liar in the first place, so our person in question is indeed a truth-teller.

The expected number of people we will have to choose randomly is O(1) (this is the meatiest part of this question, and since it may be homework, I'll skip the proof, but hint for an easy proof: geometric distribution), which means we will find our truth-teller and reliable source in O(1)*O(n) time, and from there it's another O(n) till the finish. In total, O(n).

Answer 3

A good paper on this topic is Leslie Lamport's "The Byzantine Generals Problem", available at http://research.microsoft.com/en-us/um/people/lamport/pubs/byz.pdf

Not a direct solution, but good background reading for those interested.