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

Steve Eppley seppley at alumni.caltech.edu
Sun Aug 29 11:46:25 PDT 2004

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

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

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

```