[EM] SODA

[fsimmons at pcc.edu]

----- Original Message -----
From: Jameson Quinn 
> 2011/7/7 Andy Jennings 
> 
> > On Wed, Jul 6, 2011 at 6:06 PM, wrote:
> >
> >>
> >> Of course, with too many factions, the optimal strategy 
> computation would
> >> be intractable.
> >>
> >
> > With twenty candidates, there are about a million different possible
> > subsets to consider. Seems like it could be tractable.
> >
> > I'm not exactly following how the tree is organized. If there 
> are N
> > candidates and every voter ranks all candidates, then the 
> biggest N-1 size
> > faction will be the one that omits the candidate who is ranked 
> last by the
> > most voters, right? Can't you apply that recursively to build 
> the tree?
> >
> 
> But wouldn't you prefer to find the biggest faction of a size 
> around N/2? I
> must admit, I'm also confused. It's easy with toy examples, but 
> I can't
> understand what Forest means for a broad set of candidates.
> 

Once we define precisely what we mean by "coalition," the coalition tree practically builds itself, and the traversal order is found in O(n) steps.

Let's say a faction is a (multi)set of identical ballots, so the atoms of coalitions are weighted factions, where the weight of a faction is the number of ballots in the faction.  [These atoms with their weights will be the leaves of the weighted coalition tree.]

Suppose that two or more factions share some initial segment of candidates in any order.  Then all of the factions that rank no candidate outside that set above any candidate in that set form a coalition.

In other words, the coalition C(S) based on a subset S of candidates is the set of all factions that do not rank any candidate outside of S ahead of any candidate inside S.  The weight of the W(S) of C(S) is the sum of the weights of the factions in C(S).

The set of all candidate coalitions is partially ordered by containment.  If C(S) contains C(S'), then C(S') is a subcoalition of C(S).

The Hasse diagram for a partially ordered set is a tree.  In our case the coalitions are the nodes of the tree, and the weights of the coalitions make it into a weighted tree.  The universal coalition consisting of all of the candidates is the root node.  Its weight is the total number of ballots.  The leaves of the tree are the atoms of the coalitionss, i.e. the factions themselves.

To find the sequence of play for the ideal version of SODA, starting at the root node recursively order the leaves of the daughter nodes and concatenate them together in descending order of weight of the daughter nodes.

There's probably a name for this order of traversal of a weighted tree.

Does anybody know it?  If so, you can look for an efficient cook book algorithm for computing the order of the leaves.

Does that help?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20110708/f6e2c793/attachment-0004.htm>