Maximal majoritarian program under incomplete voting

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:

1. 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$.

2. 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.

3. 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.

• Can you please clarify your definition of a "majoritarian program" a bit? First, can a program be against a proposition, or can it only be for the proposition or neutral about it? And second, by "we need to check that any subset of propositions in the program gathers a majority", do you mean that any subset of the propositions included in the program must have more respondents that agree with all the propositions in the subset than there are respondents who disagree with any proposition in the subset? – Ilmari Karonen Jan 7 '17 at 17:05
• Cross-posted: cs.stackexchange.com/q/68383/755, datascience.stackexchange.com/q/16126/8560. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. – D.W. Jan 7 '17 at 19:31
• Sorry for the cross-post, I did not know if my question better fits data science or computer science. – bixiou Jan 9 '17 at 10:50
• Concerning the majoritarian program: a program contains only supported propositions. The convention I have chosen is to convert non-answers (I don't know) in NA (which originally encodes missing answers). As for indifference/neutrality, I convert it to False. Hence, the status quo is the default program, and a majoritarian program contains only reforms which gather a (joint) majority for changes in policies. – bixiou Jan 9 '17 at 11:09
• The answer to your second question is Yes and no. If the data were complete, it would be Yes. As the data is incomplete, I want to look for any subset at the group of people who have answered all these questions. Then, if there is a majority in this group who have answered Yes to all the proposition in the subset, the check is validated. – bixiou Jan 9 '17 at 11:11

We can formalize this problem as follows. Let the propositions be numbered $1,2,\dots,n$. We have a function $f$ that, given a subset $S \subseteq \{1,2,\dots,n\}$ of propositions, returns true or false according to whether every proposition in $S$ has majority support among the survey respondents who saw every proposition in $S$. Define $S \subseteq \{1,2,\dots,n\}$ to be a majoritarian program if $f(T)$ is true for all $T \subseteq S$. Now we want an algorithm that, given ability to invoke $f$, finds the largest majoritarian program $S \subseteq \{1,2,\dots,n\}$.

We will of course interpret $S$ as follows: for each $i \in S$, we take whichever side of proposition $i$ has majority support (when considered in isolation; among all survey respondents who saw $i$), and take the conjunction of all of those. Given $S$ you can easily compute $f(S)$ from the survey responses.

Here is one natural but not necessarily optimal algorithm for this. Basically, you grow subsets from the "bottom up". In particular, the algorithm looks like this:

Try(S):
1. If S is not a majoritarian program, return
2. If S is larger than the largest so far, remember S as the largest so far.
3. For each i in 1+max(S) .. n:
4.     Try(S ∪ {i})


You start by invoking Try({}), and when it returns, the best subset so far is the largest majoritarian program possible. This effectively takes small subsets and tries to grow them to become bigger, but if they don't get majority support, the search is pruned and it stops trying to grow that set.

The running time could be exponential. If you get lucky, you could hope that it runs more efficiently than that, though I don't know if you'll be lucky.

As a heuristic, you could sort the propositions by order of polarization, from most unanimous to most controversial. That might speed up the search, or allow you to cut off the search after a certain time limit and take the best you've seen so far (with no guarantee that it is optimal, but the hope that it might be close).

• Thank you D.W. for your answer. This is actually what I have done (and called "Brute force"). The computation takes indeed too long a time when I include all the propositions. Here, I have a rather small dataset, but from a theoretical perspective, I would like to find another algorithm which could be scaled up to larger ones. – bixiou Jan 9 '17 at 11:16
• Just two remarks: your proposed algorithm lacks the check part. We have to check that any subset of S + {i} is a majoritarian one, because of incompleteness of the dataset. What I did is: I store the "minoritarian subsets" (those who failed in the step 1. of your algorithm), and I check if there is a subset of S + {i} inside them, after the algorithm is completed, i.e. when I have found a candidate for my majoritarian program. The second remark is that I did not think of sorting my propositions first, and I tank you for the advice. – bixiou Jan 9 '17 at 11:20
• @AdrienFabre, OK! Hopefully someone else will be able to think of a better algorithm. – D.W. Jan 9 '17 at 16:36