I have conducted two surveys on French political preferences. As half of each sample (of ~1000 persons) gave a satisfactory margin error, I have randomly displayed (or not) several questions. Now, I have an incomplete dataset of the preferences of the sample over many political propositions (I can provide it if needed). For the sake of simplicity, let us assume that for each proposition of reform, either the respondent agrees for a change (True), or not (False), either the question was not asked to him-her (NA).
I am looking for a political program (i.e. a set of propositions) which gathers a majority of adhesion: I call this a majoritarian program. For a program to be majoritarian, we need that a majority of the respondents agree jointly with all the propositions of the set. As the dataset is incomplete, we need to check that any subset of propositions in the program gathers a majority (i.e. gathers more True than False). Indeed, it could be that only 5 respondents have voted to all the propositions in the program, by chance all favorably; then, we could still not deduce that this program is majoritarian because one of its proposition could have failed to obtain a majority itself. Finally, I am looking for the maximal majoritarian program, i.e. the largest one (in terms of number of propositions).
Does anyone have an idea on how to solve exactly this computational problem? Any insight on the question is welcome, including broader reflection on optimizing over the subsets of a big set.
So far, three methods have come to my mind to solve this problem:
Brute force I have optimized an exact algorithm (which I can provide). With my (rather small) dataset (a hundred propositions), it works if I restrict the number of propositions I analyze to 47, but it is way too computationally demanding if I try to analyze all propositions. Indeed, the number of potential programs of size k grows exponentially: it is $2^k$.
Completion of data I haven't try this because I don't know the theory of imputing missing data. If such an imputation proves always reliable, then the problem may be solved. Indeed, a friend have shown me a way to reduce my problem to linear optimization as long as the dataset is complete.
Machine learning By defining appropriate an weight on each answer, that depends on the examined program, we can train a neural network to find the best ordering of propositions so as to form our program with the adequate number of highest-ranked propositions. (The gain function values individual adhesion to the program as well as its size.) However, this method is just an heuristic for the problem, and its solution is simply a proxy for the real answer. Indeed, the necessary check of the potentially maximal program may take too long a time (as we need to examine each subset of propositions in the program). Nonetheless, I will implement this method soon.