[EM] mutual majority set

[Warren Smith]

>James Green-Armytage:
>Below is the matlab program that I wrote to find the mutual majority
>set...you need to input:
>  (the number of candidates)
>  (the number of voters)
>  (a V by C matrix of voter utilities over candidates)
>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 COMMON 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.

--Interesting computer science math and logic problem.
Hopefully what I now say is not contaminated with errors:

MM-SUBSET-CLOSURE THEOREM:
MM-sets are closed under subset, that is, they can
be ordered so S1<S2<S3<...<Sn   where < means subset and there are n MM-sets.

PROOF:
 LEMMA if A and B are MM-sets it is not possible for both
(A contains somebody X not in B) and
(B contains somebody Y not in A) to happen since then
a majority would prefer to X over Y but a majority would prefer Y over X.
 HENCE B must be a subset of A (or vice versa).
QED.

COROLLARY:
There are at most C-1 different non-boring
MM-sets if C candidates ("boring"=empty or full), and it is possible
in linear(C)
space to write them all down (in a suitable notation).  So it is kind
of silly for
JGA's program only to output the smallest, you might as well output all of them.

DEFINITION:
An ordinary (not mutual) majority set shall mean a candidate-subset
such that every member of the set is preferred pairwise versus every
candidate outside the set, by a majority (but the majorities as voter
subsets can vary).

OM-THEOREM:
There are at most C-1 non-boring ordinary-majority sets, they are
closed under subset,
and all can be written down in linear(C) space [same proof as before
also works].

MM==>OM THEOREM:
A mutual-majority set automatically is an ordinary-majority set, but
the reverse can fail.

LINEAR TIME ALGORITHM:
All ordinary-majority sets can be found by an algorithm which inputs
the (C-1)*C/2 pairwise
election results (i.e. who wins in each pair) and runs in time linear
in the size of the input.
The algorithm is the depth-first search algorithm for "topological
sorting" , see
  http://en.wikipedia.org/wiki/Topological_sorting
and it will produce an ordering of the candidates such that any
ordinary-majority set
has to consist of a prefix of that ordering.

POLYTIME QUESTION: given VxC matrix, is there a polynomial(in V and C)-time
algorithm to determine whether a non-boring mutual majority set (we
won't allow the full
or empty set) exists?  Or can we prove this problem is NP-complete?

REMARK: If there is such a polytime algorithm for the yes/no existence
problem, then I can use it fairly easily to construct another polytime
algorithm for finding and printing every MM-set.

ANSWER: yes, there is a polytime algorithm for finding and printing all MM-sets:
Use the algorithm above to find all OM-sets. use the MM==>OM theorem to
realize only these sets need to be checked, check them all in polynomial time
using basically JGA's technique (intersect all the voter subsets that
prefer X over Y
for X in and Y not in the set, see if result is a majority).

REMARK: This seems to obsolete JGA's exponential-time algorithm.

SPEED QUESTION: What is the fastest algorithm you can think of?
I have stopped with only the fact a polytime algorithm exists, without trying
to find the fastest possible polynomial.

Thinking a bit, it seems the algorithm I proposed will, if implemented
naively, run in time
O( V*C^3 ).   I think I can see how to speed it up to O(V*C^2).   If
you can speed it up further to O(V*C) then you are best possible since
it has to take that long just to read the input.

-- 
Warren D. Smith
http://RangeVoting.org  <-- add your endorsement (by clicking
"endorse" as 1st step)
and
math.temple.edu/~wds/homepage/works.html