You ve been asked to help some organizational theorists analyze data on group decision-mak...

You ve been asked to help some organizational theorists analyze data on group decision-making. In particular, they ve been looking at a dataset that consists of decisions made by a particular governmental policy committee, and they re trying to decide whether it s possible to identify a small set of influential members of the committee.

Here s how the committee works. It has a set M = {m1,...,mn} of n members, and over the past year it s voted on t different issues. On each issue, each member can vote either "Yes," "No," or "Abstain"; the overall effect is that the committee presents an affirmative decision on the issue if the number of "Yes" votes is strictly greater than the number of "No" votes (the "Abstain" votes don't count for either side), and it delivers a negative decision otherwise.

Now we have a big table consisting of the vote cast by each committee member on each issue, and we d like to consider the following definition. We say that a subset of the members M' c M is decisive if, had we looked just at the votes cast by the members in M', the committee's decision on every issue would have been the same. (In other words, the overall outcome of the voting among the members in M' is the same on every issue as the overall outcome of the voting by the entire committee.) Such a subset can be viewed as a kind of "inner circle" that reflects the behavior of the committee as a whole.

Here s the question: Given the votes cast by each member on each issue, and given a parameter k, we want to know whether there is a decisive subset consisting of at most k members. We ll call this an instance of the Decisive Subset Problem.

Example. Suppose we have four committee members and three issues. We re looking for a decisive set of size at most k = 2, and the voting went as follows.

Then the answer to this instance is "Yes," since members m1 and m3 constitute a decisive subset.

Prove that Decisive Subset is NP-complete.