[EM] Mutual majority set methods

[James Green-Armytage]

Below is the matlab program that I wrote to find the mutual majority  
set. It's very fast, as long as the number of candidates isn't too  
large.

What you need to input:
C (the number of candidates)
V (the number of voters)
util (a V by C matrix of voter utilities over candidates)

What it does:
It examines each subset of the whole set of candidates (including the  
whole set itself), and determines whether the subset is a mutual  
majority set, i.e. whether a majority of voters prefer every candidate  
in the set to every candidate outside the set. If this is true of more  
than one set, it chooses the smallest of these.

The output:
The value 'MMMS' gives the index in the 'profile' matrix of the  
minimal mutual majority set. You can also see what the other mutual  
majority sets are, by looking at the 'profilescore' vector.



--------------------------

% Set up profiles
P = 2^C;   code1 = zeros(P,C);   profile = zeros(P,C);
for p = 1:P
     for x = 1:C
         code1(p,x) = ceil(p/2^(x-1));
         if ceil(code1(p,x)/2) == code1(p,x)/2
             profile(p,x) = 1;
         else
             profile(p,x) = 0;
         end
     end
end

% Find mutual majority sets
profilescore = inf(P,1);
for p = 2:P
     majoritymember = ones(V,1);
     for v = 1:V
         for x = 1:C
             for y = 1:C
                 if profile(p,x) == 1        % x is in the proposed set
                     if profile(p,y) == 0    % y is not in the proposed set
                         if util(v,y) > util(v,x)
                             majoritymember(v) = 0;
                         end
                     end
                 end
             end
         end
     end
     if sum(majoritymember) > V/2
         profilescore(p) = sum( profile(p,:) );
     end
end
[num,MMMS] = min(profilescore);