The paper is concerned with an identification problem of a set of K out of N numbers. Two parties are involved in the identification process, the inquirer and the respondent. The set to be identified is referred to as the chosen subset and it is known only to the respondent. The identification process involves the inquirer who wishes to identify the chosen subset by asking a series of questions. At each question the inquirer selects a subset of K elements out of N, the inquired subset, and receives from the respondent partial information about the number of elements which belongs to both the inquired subset and the chosen subset. The questions continue until the chosen subset is identified. A possible application of the problem is related to learning games. Two types of algorithms, which are independent of each other and aimed at identifying the chosen subset, are presented in this paper. Type I algorithms (uncertainty reduction) select only subsets that have not yet been rejected as being the chosen subset. A linear integer programming model is employed to identify the set of subsets that have not yet been rejected—the uncertainty set. For Type I algorithms two different decision rules are considered to select a subset. Each decision rule selects the elements of the next inquired subset by employing a different probabilistic argument: 1) randomly select the next subset from among the subsets not yet ruled out, or 2) select as the next subset the one whose elements occur most frequently among the subsets not yet ruled out. Type II algorithms (static and dynamic processing) select a subset according to a different principle which allows the inquirer to select a subset that may not belong to the uncertainty set. This is accomplished by marginally interchanging the elements of any two successive subsets. Analytical solutions are provided for algorithms of Type II. Furthermore, a comparison between the two types of algorithms under different measures of performance, such as the expected number of questions (subsets) required to identify the chosen subset, is conducted through a simulation analysis.
