[EM] SODA

[fsimmons at pcc.edu]

A correction below at ***

----- Original Message -----
From: 
Date: Thursday, July 7, 2011 5:16 pm
Subject: Re: [EM] SODA
To: Jameson Quinn ,
Cc: Andy Jennings , election-methods at lists.electorama.com,

> 
> 
> ----- 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 coalitions, i.e. the factions themselves.

This paragraph should read ...

The universal coalition consisting of all of the factions is the root node.  Its weight is the sum of all of the 
faction weights, i.e. the total number of ballots.  The leaves of the tree are the atoms of the coalitions, 
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?
>