We investigate a new type of information-theoretic identification problem, suggested to us by Alan Taylor. In this problem we are given a set of items, more than half of which share a common ``good" value. The other items have various other values which are called ``bad". The only method we have for gaining information about the items' values is to ask whether two items share the same value. We can assume there is an oracle which always answers each such query truthfully. Our goal is to identify at least one good item, i.e., an item which is guaranteed to have a good value, using a minimum possible number of queries. We will establish upper and lower bounds for the number of queries needed
for both adaptive as well as oblivious strategies.
The practical context in which this problem arose was in connection with trying to identify a good sensor from a set of sensors in which some are non-operational or corrupted, for example, where it was desired to minimize the amount of intercommunication used in doing so.
We just learned that the basic version of the problem addressed in this technical report had been studied before in the literature, and known as the problem of "computing majority". Saks and Werman (Combinatorica 11 (1991), 383-387) first determined the exact complexity when there are only two values, showing f_1(n)= n - w_2(n). Another proof was given by Alonso, Reingold and Schott (Information Processing Letters 47(1993), 253-255). Thus, Theorem 1 in this technical report is superseded by the above result, and the open question (1) raised in Section 5 already has been answered. A new article containing several variants on this problem by Martin Aigner will soon appear in Discrete Applied Mathematics.
We thank Professor Ugo Vaccaro of the University of di Salerno for communicating to us all the above information.
Our previous comments need some qualification: the "majority problem" in the literature asks for either the output of a majority element or a declaration that "no majority exists". When n is even, this is slightly different from the model discussed in our technical report, in which it is assumed that there is a majority. Thus, the open problem mentioned in (i) of Section 5 of our technical report was immediately implied by the result of Saks and Werman's 1991 Combinatorica paper only for the case of odd n. In the case of even n, our open problem (i) was solved in the paper (mentioned in our previous comments) by Martin Aigner's paper in Discrete Applied Mathematics. Again, we thank Professor Ugo Vaccaro for pointing out these finer distinctions in the models and their implications.
