[EM] mutual majority set

[Paul Kislanko]

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: election-methods-bounces at lists.electorama.com
[mailto:election-methods-bounces at lists.electorama.com] 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