Resolvability (was Re: [EM] Re: Election-methods Digest, Vol 2, Issue 42)

[Steve Eppley]

Alex S wrote:
>> Steve Eppley wrote:
>>> Aren't all the voting methods we've been promoting 
>>> both anonymous and neutral? Doesn't that mean
>>> none of them are entirely non-random?
>
> My understanding is that anonymous and neutral methods only 
> need a non-deterministic component to break ties. When I 
> analyze methods mathematically (e.g. my never-ending quest 
> to prove that Strong FBC is impossible) I simply leave aside 
> the issue of ties by specifying that the method yields a 
> definite winner determined uniquely and deterministically 
> from the ballots submitted except "in rare cases", 

It can be misleading to leave aside the issue of ties
and tiebreaking.  There may also be negative consequences
if, as a result, a poor tiebreaker is chosen.  In 
particular, suppose the tiebreaker is not independent
of clones.  Even though ties will be rare, it won't be 
known at nomination time whether the vote will be a tie, 
so it would be rational for every faction to nominate 
a slew of clones just in case there's a tie.

> where "rare cases" is made more precise depending
> upon the mathematical framework that I'm using. 
-snip-

There's a criterion in the social choice literature, 
resolvability, that's defined precisely and is useful for
distinguishing which methods rarely involve randomness. 
(For instance, Tideman provides a definition in his 
1987 paper on clone independence.)

   Resolvability
   -------------
   A voting method is resolvable if and only if, 
   for each possible collection of votes, 
   one of the following two cases holds:

   1. There exists a candidate that would be 
      elected with certainty given those votes.

   2. There exists a candidate x and an expression v
      such that v would be an admissible vote if 
      some voter voted v, and x would be elected
      with certainty given the votes with v added.

In other words, if the voting method is resolvable, 
then every election is at most one vote away from an
election that would be tallied entirely non-randomly.  
It follows that if the number of voters is large,
then the fraction of possible elections that would
require some randomness to elect a single winner 
is very small.

I slightly prefer a slightly different definition 
of resolvability, changing the wording of case 2:

   2. For each candidate x that has a non-zero chance
      of being elected given those votes, there exists 
      an expression v that would be an admissible vote 
      if some voter voted v, such that x would be elected
      with certainty given the votes with v added.

>>> Man, this stuff has got me really worried. It's just 
>>> scary how unconcerned the Republicans seem about 
>>> having a verifiable vote-counting process. 
-snip-

I didn't write that.  Alex must have quoted someone else.

--Steve