[EM] Paper By Ron Rivest (fsimmons at pcc.edu)

fsimmons at pcc.edu fsimmons at pcc.edu
Mon Nov 22 13:00:05 PST 2010


As I mentioned in my last message, Designated Strategy Voting  (DSV) methods almost always fail 
monotonicity, even when the base method is monotone.  I promised that I would give a general technique for 
resolving this technique.

Before I try to keep that promise, let’s think about why DSV is such an attractive idea.  I think that there are 
two main reasons.  (1) The DSV “machine” is supposed to implement near optimal strategy for the voter 
based on the information it receives.  (2) The information the machine receives is directly from the voters on 
election day, so it should be more accurate than any politically manipulated polling (dis)information available 
to the voters as a basis for forming their own strategies, should they be so inclined.

With those points in mind, here is my general remedy:  each voter may submit two ballots, the first of which 
is understood to be a substitute for the polling information that would be used for strategizing in the base 
method if there were no DSV.   Then near optimal strategy (assuming the approximate validity of this 
substitute polling information) for the base method is applied to the second set of ballots to produce the 
output ballots, which are then counted as in the base method.

That’s the idea.  Let’s see how it might work for a DSV version of Approval, which is an ideal candidate for 
DSV because all of the near optimal strategies assume fairly accurate polling information, and voters averse 
to strategizing miss out on the full potential benefit of their vote:

Suppose that the designated strategy for all voters is to approve all alternatives with a score greater than the 
expected winning score on their score ballot.  The voters submit two score ballots, one to substitute for 
polling information, and therefore not necessarily sincere, and the other for conversion into an approval ballot 
by the designated strategy.  Then …

(I)	The winning probabilities are calculated from the first set of ballots by some machine that 
implements game theoretic and/or statistical ideas.  

(II)	Once these approximate winning probabilities have been determined, the approval cutoffs are 
calculated for each ballot in the second set.  The alternative with the greatest approval is elected.

Note that since the base method (Approval) is monotone, step (II) is monotone.  In other words, if some 
voters raise the score of the approval winner on the second set of ballots (leaving the first set of ballots 
unchanged), the winner will not change.  

Of course it is possible that by raising the score of the winning alternative on the first (polling) ballot, the 
winner could change.  But this possibility already exists (in hidden form) for ordinary Approval;  in that 
setting the voters can manipulate the polls just as much without destroying the reputation of Approval as a 
monotonic method.





More information about the Election-Methods mailing list