[EM] mutual majority set

[Kristofer Munsterhjelm]

Warren Smith wrote:
> 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).

Is that the same as the CDTT set? The CDTT set is like the Schwartz set, 
but the relation is "beats by a majority" rather than just "beats". You 
could make a ranking of sets by first having the top set, then the top 
set with these excluded, then the top set with those excluded, and so on.

Maybe it's not the same, but it would seem that you'd have a MM=>CDTT 
theorem, too: if {A, B, C} is a mutual majority set, they by definition 
beat everybody else by a majority, and so it is not the case that 
someone not in the MM set appears higher in the ranking of subsets than 
someone who is.

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

Is there a summable method to finding the MM-sets, or the smallest MM 
set? There does seem to be many sets that have the X=>MM property you've 
mentioned. Perhaps it would be possible to show for two such sets (X and 
Y) that

- both these sets can be found in polytime from summable data structures
- it is never the case that there is both a false alarm for X and for Y, 
i.e. there are always values k and p so that the union of the top k 
subsets in X and the top p subsets in Y agree and form the MM set.

I'm not sure how one would go about finding X and Y, though, or proving 
that there is no such combination.

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

How would you speed it up to V*C^2?