## 4 Deriving Branching Rules
### Sequential Identification  
Branching rules will be identified in a sequential manner. To get started, we first identify all the admissible CQs. A CQ is admissible if it has cost and benefit satisfying \(C\leq C_{0}\) and \(B\geq B_{0}\), where \(B_{0}\) is a specified minimum benefit. The motivation for imposing the benefit constraint is to screen out CQs that do not have an adequate sample size to judge if the majority answer can be trusted as representative of future surveys. As can be seen from Figure 1, for example, some of the CQs have very small values for \(s_{0}+s_{1}\), and this becomes increasingly more common the deeper you look into the tree.  
Admissible CQs that have zero cost (_i.e._, all the answers to the CQ go one way) form the initial list of CQs to be eliminated. After that, we choose CQs that have small non-zero cost-benefit ratios, \(R\). For each CQ that is selected, the \(N\) matrix is modified to reflect the presumed majority answer. Modifying \(N\) involves consolidating the minority answers to the majority in multiple places, as will now be illustrated.  
Figure 1: Illustrative example of \(N\) depicted as a tree.  
Referring to Figure 1, the CQ with the smallest cost-benefit ratio is question #3, given that the answer to the first two questions was '0.' For this case, \((s_{0}\,,\,s_{1})=(317\,,\,\,4)\), \(C=4\), \(B=321\) and \(R=4/321\). The modified version of \(N\) is shown in Figure 2. First, it can be seen that the four '1' answers to the CQ have been merged with the 317 '0' answers. A consequence of this change is that it becomes unnecessary to ask the CQ, since all 321 answers have become '0.' Thus, for a cost of 4 changed answers, a benefit of 321 reduced questions needs to be asked. Second, it can also be seen that subsequent corresponding merges were implemented to maintain consistency throughout the tree. These additional merges are necessary because for the four respondents who answered '1' to the CQ we want to preserve their answers to all subsequent questions. The first iteration is complete and the remaining budget is \(A-4\).  
In the second step of the sequential process, the modified \(N\) is processed in what is essentially the same way the original \(N\) was processed in the first step, the only difference being that we compare cost to a reduced budget to account for what part of it was spent in the first step. Referring to Figure 2, the CQ with the smallest cost-benefit ratio is question #3, given that the answers to the first two questions are '1' and '0.' For this case, \((s_{0}\,,\,s_{1})=(256\,,\,\,8)\), \(C=8\), \(B=264\) and \(R=8/264\). The modified version of \(N\) is shown in Figure 3. It can be seen that the 8 '1' answers to the CQ have been merged with the 256 '0' answers. A consequence of this change is that it becomes unnecessary to ask the CQ, since all 264 answers have become '0.' Thus, for a cost of 8 changed answers, the benefit is a reduction of 264 questions that need to be asked. The second iteration is complete, and the remaining budget is \(A-12\).  
The sequential process would continue until either the budget, \(A\), for the number of changed answers amongst the historical surveys was entirely spent, or until all the remaining CQs had individual costs that exceeded the remaining budget. Upon completion of the sequential process, the branching rules can be discerned from \(N\) by identifying the CQs that have pure answers. The mining section of the algorithm in the appendix sketches the steps involved with the sequential process. The basic idea is to iteratively identify the CQ that would deliver the biggest 'bang for the buck' in terms of eliminating that question from the survey. CQs are eliminated on that basis until the remaining budget for the number of changed answers reaches zero, or can no longer be reduced.  
Figure 2: Modified \(N\) for after first iteration of illustrative example.