[EM] SODA

[Jameson Quinn]

2011/7/7 <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,


That may be so, but I still don't understand what algorithm you're
proposing.


> 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.
>

Actually, if you assume only the top five vote-getters are "viable" -
generally justified from the outset in real elections - then there are only
5^19 possibilities, and some good chess-playing algorithms could prune that
tree to tractability.

But the reason I said we should let the candidates do it rather than
computing wasn't computability; it was to prevent pre-election strategy
(principally burial) for candidates.

JQ
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20110707/f2ceff14/attachment-0004.htm>