> 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 ---- Election-Methods mailing list - see http://electorama.com/em for list info
