[EM] mutual majority set

[Warren Smith]

> OM-set... Is that the same as the CDTT set?

--oh, maybe+probably.  I did not pay attention to whatever everybody
else's precise definitions were,  but probably my OM-set corresponds
to their's or if not I daresay one can modify whatever I said to work
with their definition.


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

--Interesting question.  Well clearly the OM-sets are findable in
"summable" fashion, since
all you need to know are the pairwise totals.   I do not see how to
find MM-sets in summable fashion but that might just mean I'm too
stupid.

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

--first it takes V*C^2 time to find all the pairwise totals in naive manner.
Then C^2 time to find the OM-sets.
Second, the naive way I outlined to find the MM-sets takes V*C^3 time.

How can this be sped up to V*C^2?    For a putative MM-set S, you can
go thru the V
voters, for each voter X asking "does X prefer all members of S over
everybody else?"
and answering that in O(C) time.  (Hint: first build an array saying
for each candidate what rank they are and another array saying what
rank-range is permitted...) So the check done in this fashion takes
O(V*C) time, not O(V*C*C).   Since only C-1 putative sets to check,
the whole process now runs in only O(V*C*C) time.

--But wait, there is more.

I will now try to construct an optimal-speed, O(V*C)-time
algorithm under the assumption V>C.
   This is optimal speed since it takes that long just to read the input.
I will sketch such an algorithm with details suppressed and some steps
left vague.
Assuming you can successfully fill in the gaps in what I now say, then
we have succeeded in reaching optimality.

Given a combined description of all OM-sets as an ordering of the C candidates
where the OM-sets all are prefixes of that ordering, I think we can in
O(C) time
actually find for a given voter X EVERY point in that ordering such
that X prefers all candidates above that point to all below.  I leave
it to you to write down the sub-algorithm for that more precisely.
(I'm a bit confused or lazy.   You may need to do
a C*C-time or even V*C-time preprocessing step before starting, which is ok.)
So by recording the counts in a C-2 entry array we then can for all
C-1 putative MM-sets, determine which ones really are MM-sets, in
total time O(V*C).

We still have to speed up the initial step of finding all MM-sets, to
O(V*C) time,
which means that our initial step of finding all pairwise totals in
O(V*C^2) time, has to be abolished somehow.   Create in O(V*C + C*C)
time, which assuming V>C is O(V*C)
time, a CxC matrix saying for each candidate how many voters rank him
Kth for all
K.   Now using O(C)-time algorithm find for each candidate all
rank-ranges [L,U] such
that a majority of voters agree he is ranked r with L<=r<=U.   This
info is stored
as an array saying for each L the maximum allowable U.
Now if we can combine all these different ranges into constructing
the magic ordering giving all the OM-sets... all in O(C^2) time, then
we have succeeded.

End of vague optimal-algorithm sketch.  (At this point I am not sure
it can actually be made to work, you'd have to fill in the details
carefully and at some point it might be revealed that
I made an unrepairable mistake.)

This algorithm (if correct) does not seem at all trivial.

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