I try to follow these discussions, but eventually every one of them turns into jargon thatI don't have time to research. I'm confused by the term "mutual" majority, which by it's nae ought to imply finding the subsets of VOTERS who all have the rankings. But all of the theorems are about alternatives, not voters.
http://sebaseball.rivals.com/content.asp?SID=1048&CID=1185716 describes an "election" with 5 voters and 300 alternatives. It is obvious from the "Count of votes by rank" and the "Pairwise rankings" for all alternatives on a majority of ballots that the Smith Set consists of three alternatives. My definition of "winner" amongst the three is the one with more votes for #1+#2 than the others, even though the other two have more votes for #1. My method is basically Bucklin. My question is, given the input on that page, what subset of the voters { BA BL BW CB CP } constitute a "mutual majority"? -----Original Message----- From: [email protected] [mailto:[email protected]] On Behalf Of Warren Smith Sent: Sunday, February 06, 2011 5:19 PM To: election-methods; electionscience Subject: [EM] mutual majority set >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 ---- Election-Methods mailing list - see http://electorama.com/em for list info ---- Election-Methods mailing list - see http://electorama.com/em for list info
