[EM] SODA

[fsimmons at pcc.edu]

----- Original Message -----
From: Andy Jennings 
> >
> > 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.

Building the tree and finding the order of play is tractable, but computing the optimal strategy is 
intractable.

Suppose there are twenty candidates, then each candidate has 19 choices of where to put her approval 
cutoff in her ranking of the candidates.  That makes 19^20 possibilities.  Precisely one of these will be 
optimal for the given order of play.   So Jameson is right; it is better to not compute the optimal strategy 
automatically; just let the candidates play the chess game the best they can.

However, when it gets down to the last five players, there will be only 19^5 possibilities left, and these 
could be done automatically in order to completely remove the temptation for a potential "kingmaker" to 
throw the election for some personal gain.