# Optimized Weighted Nearest Neighbours Matching Algorithm for Control Group Selection
## 3 Weighted Nearest Neighbours Control Group Selection with Simulated Annealing (WNNSA)
### Conflicting Candidates
Additionally, denote \(X_{C}^{k}\), the _aggregated reduced set of candidates_ for the \(k\)-sized environment as:  
\[X_{C^{*}}^{k}=\{\mathbf{X}_{j}|\mathbf{X}_{j}\in NN_{k}(\mathbf{X}_{i},X_{C}),\forall\mathbf{X}_{i}\in X_{T}\}. \tag{7}\]  
Furthermore, denote \(Dem(\mathbf{X}_{j})\) those individuals from the treated group for which \(\mathbf{X}_{j}\in X_{C^{*}}^{k}\) is in their \(k\)-size reduced environment. \(Dem(\mathbf{X}_{j})\) is called the _demand set_ of \(\mathbf{X}_{j}\), and it is calculated as:  
\[Dem(\mathbf{X}_{j})=\{\mathbf{X}_{i}|\mathbf{X}_{j}\in NN_{k}(\mathbf{X}_{i},X _{C})\}, \tag{8}\]  
where \(\mathbf{X}_{i}\in X_{T}\). Let \(di(\mathbf{X}_{j})\) be the _demand index_ for \(\mathbf{X}_{j}\in X_{C^{*}}^{k}\) quantifying those \(\mathbf{X}_{i}\in X_{T}\) subjects which select \(\mathbf{X}_{j}\) as one of the \(k\)-nearest neighbours into the \(k\)-reduced environment. The demand index is calculated as:  
\[di(\mathbf{X}_{j})=\frac{|Dem(\mathbf{X}_{j})|}{k}, \tag{9}\]  
Figure 1: Demonstration of conflicting pairs in a reduced environment \(\mathbf{X_{1}}\), \(\mathbf{X_{2}}\) and \(\mathbf{X_{3}}\) are three individuals from the treated group and \(\mathbf{X_{4}}\), \(\mathbf{X_{5}}\), and \(\mathbf{X_{6}}\) are three individuals from the candidate group. In the case of a \(k=2\) reduced environment, 1:1 matching cannot be performed; while in the case of a \(k=3\) reduced environment, conflicts can be resolved. where \(|Dem(\mathbf{X}_{j})|\) yields the size of the demand set of \(\mathbf{X}_{j}\). Denote \(asi(\mathbf{X}_{j})\) the _alternative selection index_ for \(\mathbf{X}_{j}\), which quantifies the alternative selection options of \(\mathbf{X}_{j}\) for all \(\mathbf{X}_{i}\in Dem(\mathbf{X}_{j})\). Alternative selection means that the elements of the demand set of \(\mathbf{X}_{j}\) are paired to another candidate individual instead of \(\mathbf{X}_{j}\). The alternative selection index for \(\mathbf{X}_{j}\) can be calculated as:  
\[asi(\mathbf{X}_{j})=\frac{\sum_{\mathbf{X}_{i}\in Dem(\mathbf{X}_{j})}min(di(NN _{k}(\mathbf{X}_{i},X_{C})))}{|Dem(\mathbf{X}_{j})|}. \tag{10}\]  
Using these metrics, we can easily define the minimum size of the environment required for our pairing algorithm to succeed. If exists such an \(\mathbf{X}_{j}\in X_{C}^{k}\), that \(di(\mathbf{X}_{j})>1\) and \(asi(\mathbf{X}_{j})>1\), there is an unsolvable conflict. In this case, the size of the environment (the value of \(k\)) have to be increased. The method to determine the minimum value of \(k\) is summarized in Algorithm 2. ```
Input:\(X_{T}\): the set of the treated group; \(X_{C}\): the set of candidate individuals Output:\(k_{min}\): the minimal size for the reduced environment. 1 Calculate the distance matrix \(\mathbf{D}\) by Equation (3). Set \(k=1\). Determine \(X_{C}^{k}\), by Equation (7). For all \(\mathbf{X}_{j}\in X_{C}^{k}\): Calculate \(di(\mathbf{X}_{j})\) by Equation (9). If \(di(\mathbf{X}_{j})>1\) Calculate \(asi(\mathbf{X}_{j})\) by Equation (10). If \(asi(\mathbf{X}_{j})>1\)\(k=k+1\) Go Step 3 Return \(k\). ```  
**Algorithm 2**Determination of the minimal size for the reduced environment for the WNNSA algorithm. After determining the size of the minimal reduced environment, the WNNSA algorithm can be executed. In order to perform a successful control group selection, the value of \(k\) must be initialized to at least the value determined by Algorithm 2. The higher the value of \(k\) is, the greater the degree of freedom the WNNSA algorithm has. However, it should also be taken into account that a too high value of \(k\) reduces the chances of the simulated annealing optimization to find the optimal pairing of the elements. Therefore, it is recommended to set the value of the \(k\) parameter first to the minimum required (\(k_{min}\)), or a little higher.