[EM] SODA

[fsimmons at pcc.edu]

 > > Therefore, we finally have a monotone, clone free, DSV that 
> takes rankings
> > as input, and puts out
> > rationally determined approval ballots.
> >
> 
> Well, you'd have to impute the most popular ranking among a 
> candidate'svoters to the candidate, and either use some direct 
> approval strategy or
> make fake candidates for all other rankings among a candidate's 
> voters...and that breaks the nice symmetry of the method 
> somewhat, but none of it
> should break the monotonicity or the clone-freeness.

Actually, the same coalition tree technique would work for as many factions as desired, outputing a 
(potentially) different approval ballot for each faction, even when several different factions have the same 
favorite.

Of course, with too many factions, the optimal strategy computation would be intractable.

Let's see how it would work on the simple example

45 B>C>A.
15 C>B>A
30 A>C>B
10 C>A>B

The coalition tree is  (45BCA /\15CBA)/root\(30ACB /\ 10CAB).

I have ordered the factions so that traversing the tree in its preorder gives the correct sequence.

At the root node the left branch accounts for 60 percent of the ballots, while the right branch accounts 
for 40 percent, so the left branch is rightfully traversed first (as in a preorder traversal), etc.

Since there are two approval cutoff possibilities for each faction, there are sixteen possible cutoff 
configurations.

I'm not going to list them all, but (if I am not grossly mistaken) the (essentially) unique optimal solution is

45B, 15C, 30 AC, 10 C, 

which gives approval totals for A, B, and C as
30, 45, and 55, respectively.

I say "essentially" because it makes no difference whether the BCA faction approves C or not.

In the long run any of Rob LeGrand's DSV (Designated Strategy Voting) methods (whether batch or 
sequential, whether strategy A or not) would yield approvals in the same proportion for this particular 
example..

Our coalition tree based method uses the same solid coalition structure as Woodall's Descending Solid 
Coalition (DSC) method, but soon parts company with DSC, although in this particular example it yields 
the same result, namely that C wins.