Jameson Quinn

2009-06-25 17:55:48 UTC

I believe that using Range ballots, renormalized on the Smith set as a

Condorcet tiebreaker, is a very good system by many criteria. I'm of course

not<http://lists.electorama.com/pipermail/election-methods-electorama.com/2005-January/014469.html>the

first one to propose this method, but I'd like to justify and analyze

it

further.

I call the

system Condorcet/Range DSV because it can be conceived as a kind of

Declared Strategy Voting

system, which rationally strategizes voters' ballots for them assuming that

they have correct but not-quite-complete information about all other voters.

Let me explain.

I have been looking into fully-rational DSV methods using Range ballots both

as input and as the underlying method in which strategies play out. It turns

out to be impossible, as far as I can tell, to get a stable, deterministic,

rational result from strategy when there is no Condorcet winner. (Assume

there's a stable result, A. Since A is not a cond. winner, there is some B

which beats A by a majority. If all B>A voters bullet vote for B then B is a

Condorcet winner, and so wins. Thus there exists an offensive strategy. This

proof is not fully general because it neglects defensive strategies, but in

practice trying to work out a coherent, stable DSV which includes defensive

strategies seems impossible to me.) Note that, on the other hand, there MUST

exist a stable probabilistic result, that is, a Nash equilibrium.

Let's take the case of a 3-candidate Smith set to start with. (This

simplifies things drastically and I've never seen a real-world example of a

larger set.) In the Nash equilibrium, all three candidates have a nonzero

probability of winning (or at least, are within one vote of having such a

probability). Voters are dissuaded from using offensive strategy by the real

probability that it would backfire and result in a worse candidate winning.

This Nash equilibrium is in some sense the "best" result, in that all voters

have equal power and no voter can strategically alter it. However, it is

both complicated-to-compute and unnecessarily probabilistic. Forest Simmons has

proposed an interesting

method<http://lists.electorama.com/pipermail/election-methods-electorama.com/2003-October/011028.html>for

artificially reducing the win probability of the less-likely

candidates,

but this method increases computational complexity without being able to

reach a single, fully stable result. (Simmons proposed simply selecting the

most-probable candidate, which is probably the best answer, but it does

invalidate the whole strategic motivation).

There's an easier way. Simply assume that any given voter has only

near-perfect information, not perfect information. That is, each voter knows

exactly which candidates are in the Smith set, but makes an ideosyncratic

(random) evaluation of the probability of each of those candidates winning.

That voter's ideal strategic ballot is an approval style ballot in which all

candidates above their expected value are rated at the top and all

candidates below at the bottom. However, averaging over the different

ballots they'd give for different subjective win probabilities, you get

something very much like a range ballot renormalized so that there is at

least one Smith set candidate at top and bottom. (It's not exactly that, the

math is more complex, especially when the Smith set is bigger than 3; but

it's a good enough approximation and much simpler than the exact answer).

Let's look at a few scenarios to see how this plays out.

First, the typical minimal Condorcet scenario. You have Va voters who say

A>B>C, and think on average that B is b% as good as A compared to C (that

is, if they rank them 70, 60, 20, then b=(60-20)/(70-20)=80%); Vb voters who

say B>C>A with C on average c% as good as B; and Vc voters who vote C>A>B

with A at a%. Without loss of generality, Va > Vb or Vc, but Va < Vb + Vc

(or A would be a Condorcet winner). The renormalized Range tiebreaking

scores are A=Va + a*Vc; B=Vb + b*Va; and C=Vc + c*Vb. What does that mean?

* If all of a, b, and c are 50%, then the candidate with the most

exceptionally strong win or weak loss, wins (that is, if the two strongest

wins are farther apart than the two weakest losses, then the strongest win,

otherwise the weakest loss).

* If one of a, b, and c is near 100% where the others are near 0%, then that

candidate wins. You could say that the XYZ voters' opinion of Y is acting as

the tiebreaker for Y.

* In general, for honest ballots, the winner is the candidate with the least

renormalized Bayesian regret. Assuming the effects of renormalization are

random, this will tend to be the candidate with the least Bayesian regret

overall.

Note that this could elect a Condorcet loser. For instance, if you had

ballots A>B>D>>>C, B>C>D>>>A, and C>A>D>>>B, (that is, each ballot rates

candidates at 100, 99, 98, and 0) then D is the Condorcet loser but has

higher utility than any other candidate, and wins. But this could only

happen if there is a Condorcet tie for winner. In general, I find the

scenario pretty implausible, and the result still optimal for that scenario.

(Because I think such results are optimal, I advocate using the Smith set

and not the Schwarz set for renormalizing).

How does this method do on other criteria? It fulfills Condorcet (by

definition) and is monotonic. For strategies which don't change the content

of the Smith set, it does very well on other criteria, fulfilling

Participation, Consistency, and "Local IIA". However, as the content of the

Smith set changes, it can fail all of those latter criteria - but only by

moving *towards* the renormalized utility winner, who is arguably the

correct winner anyway. I believe that, because of its construction, it will

have relatively low Bayesian Regret among Condorcet systems.

How resistant is it to strategy? When the Smith set is unchanged, all useful

strategies are at worst asymptotically on the honest side of semi-honest -

that is, they only require ranking equal (or, for nearly all of the

strategic benefit, nearly equal) candidates who are not honestly equal.

Moreover, I think that the DSV construction of this system gives it

excellent resistance to real-world strategies. Unless you have more

information than the agent which strategizes your ballot, you simply vote

honestly and allow the system to strategize for you. Thus, you wouldn't be

motivated to use strategy unless you felt you knew not only the exact

possibilities and chirality of the Smith set, both before and after your

strategizing, but also the probable winner from that Smith set. Under

realistic polling information, I think that such scenarios will be rare; if

you know of a possible Condorcet tie, then you will not generally know much

about the likely winners of this tie.

(It may even be provable that if you assume voters exist in some kind of

continuous, unimodal distribution in ideology space, and motivate Condorcet

ties by having non-euclidean but continuous distance measures, then there

will always naturally exist enough "honest defensive votes" to make any

strategy backfire).

Note that in regard to resisting simple strategies, this method is a serious

improvement over either Range or Approval. Because it is a kind of DSV, it

"does the strategy for you". So a candidate will gain no significant

advantage if their voters are more strategic (that is, more dichotomous and

better at evaluating the expected winners of the election) than other

candidates' voters. It allows for naive votes of many kinds, including

potentially "don't know" votes for certain candidates, simple approval-style

votes, simple ranking-style votes, and others, giving all approximately the

same power. And because it uses Range ballots as an input but encourages

more honest voting than Range, it enables the society to see (as an academic

question) who is the true Range winner, when that differs from the Condorcet

winner. I believe that, in successive elections, enough voters would

reevaluate such candidates to make one of them win in both senses.

Nonetheless, I will present one scenario where strategy might be employed.

Say the candidates are Nader, Gore, and Bush, and assume (contrafactually)

that this is simple a matter of 1-dimensional ideology and that all voters

agree that the candidates are, left to right,

nader..gore..........................bush (that is, Nader and Gore in this

scenario are considered much closer than Gore and Bush). Assume also that

there is some dearth of center-left voters who prefer Gore to Bush only

weakly. So the honest preferences are something like

Nader Gore Bush

11% 100 99 0

40% 99 100 0

49% 0 1 100

If all of the 11% of Nader voters dishonestly "bury" Gore under Bush, then

Nader wins with 50.6% (that is, 11% + (99%*40%)). However, if even 2 of the

40% Gore voters honestly vote Gore, Bush, Nader - or EVEN if those 2% simply

give Nader 1 point instead of 99 points - then the strategy backfires and

elects Bush. Given the honest utilities assumed, the Nader voters would not

use this strategy if they thought this was even 1% likely. In the real

election, of course, there was in fact a non-negligible minority of honest

Gore>Bush>Nader voters. (Gore voters were probably likelier to support Bush

second than Nader voters, and I've seen polls that say 1/4 of Nader voters

supported Bush second (!); 1/4 of Gore voters would be around 12%). So this

strategy would never have worked in real life, and in fact it requires an

artificial gap in the voter distribution right near the Gore>Bush>Nader zone

(extending on both sides of that zone, because for instance Gore>>Nader>Bush

votes hose the strategy too).

Condorcet tiebreaker, is a very good system by many criteria. I'm of course

not<http://lists.electorama.com/pipermail/election-methods-electorama.com/2005-January/014469.html>the

first one to propose this method, but I'd like to justify and analyze

it

further.

I call the

system Condorcet/Range DSV because it can be conceived as a kind of

Declared Strategy Voting

system, which rationally strategizes voters' ballots for them assuming that

they have correct but not-quite-complete information about all other voters.

Let me explain.

I have been looking into fully-rational DSV methods using Range ballots both

as input and as the underlying method in which strategies play out. It turns

out to be impossible, as far as I can tell, to get a stable, deterministic,

rational result from strategy when there is no Condorcet winner. (Assume

there's a stable result, A. Since A is not a cond. winner, there is some B

which beats A by a majority. If all B>A voters bullet vote for B then B is a

Condorcet winner, and so wins. Thus there exists an offensive strategy. This

proof is not fully general because it neglects defensive strategies, but in

practice trying to work out a coherent, stable DSV which includes defensive

strategies seems impossible to me.) Note that, on the other hand, there MUST

exist a stable probabilistic result, that is, a Nash equilibrium.

Let's take the case of a 3-candidate Smith set to start with. (This

simplifies things drastically and I've never seen a real-world example of a

larger set.) In the Nash equilibrium, all three candidates have a nonzero

probability of winning (or at least, are within one vote of having such a

probability). Voters are dissuaded from using offensive strategy by the real

probability that it would backfire and result in a worse candidate winning.

This Nash equilibrium is in some sense the "best" result, in that all voters

have equal power and no voter can strategically alter it. However, it is

both complicated-to-compute and unnecessarily probabilistic. Forest Simmons has

proposed an interesting

method<http://lists.electorama.com/pipermail/election-methods-electorama.com/2003-October/011028.html>for

artificially reducing the win probability of the less-likely

candidates,

but this method increases computational complexity without being able to

reach a single, fully stable result. (Simmons proposed simply selecting the

most-probable candidate, which is probably the best answer, but it does

invalidate the whole strategic motivation).

There's an easier way. Simply assume that any given voter has only

near-perfect information, not perfect information. That is, each voter knows

exactly which candidates are in the Smith set, but makes an ideosyncratic

(random) evaluation of the probability of each of those candidates winning.

That voter's ideal strategic ballot is an approval style ballot in which all

candidates above their expected value are rated at the top and all

candidates below at the bottom. However, averaging over the different

ballots they'd give for different subjective win probabilities, you get

something very much like a range ballot renormalized so that there is at

least one Smith set candidate at top and bottom. (It's not exactly that, the

math is more complex, especially when the Smith set is bigger than 3; but

it's a good enough approximation and much simpler than the exact answer).

Let's look at a few scenarios to see how this plays out.

First, the typical minimal Condorcet scenario. You have Va voters who say

A>B>C, and think on average that B is b% as good as A compared to C (that

is, if they rank them 70, 60, 20, then b=(60-20)/(70-20)=80%); Vb voters who

say B>C>A with C on average c% as good as B; and Vc voters who vote C>A>B

with A at a%. Without loss of generality, Va > Vb or Vc, but Va < Vb + Vc

(or A would be a Condorcet winner). The renormalized Range tiebreaking

scores are A=Va + a*Vc; B=Vb + b*Va; and C=Vc + c*Vb. What does that mean?

* If all of a, b, and c are 50%, then the candidate with the most

exceptionally strong win or weak loss, wins (that is, if the two strongest

wins are farther apart than the two weakest losses, then the strongest win,

otherwise the weakest loss).

* If one of a, b, and c is near 100% where the others are near 0%, then that

candidate wins. You could say that the XYZ voters' opinion of Y is acting as

the tiebreaker for Y.

* In general, for honest ballots, the winner is the candidate with the least

renormalized Bayesian regret. Assuming the effects of renormalization are

random, this will tend to be the candidate with the least Bayesian regret

overall.

Note that this could elect a Condorcet loser. For instance, if you had

ballots A>B>D>>>C, B>C>D>>>A, and C>A>D>>>B, (that is, each ballot rates

candidates at 100, 99, 98, and 0) then D is the Condorcet loser but has

higher utility than any other candidate, and wins. But this could only

happen if there is a Condorcet tie for winner. In general, I find the

scenario pretty implausible, and the result still optimal for that scenario.

(Because I think such results are optimal, I advocate using the Smith set

and not the Schwarz set for renormalizing).

How does this method do on other criteria? It fulfills Condorcet (by

definition) and is monotonic. For strategies which don't change the content

of the Smith set, it does very well on other criteria, fulfilling

Participation, Consistency, and "Local IIA". However, as the content of the

Smith set changes, it can fail all of those latter criteria - but only by

moving *towards* the renormalized utility winner, who is arguably the

correct winner anyway. I believe that, because of its construction, it will

have relatively low Bayesian Regret among Condorcet systems.

How resistant is it to strategy? When the Smith set is unchanged, all useful

strategies are at worst asymptotically on the honest side of semi-honest -

that is, they only require ranking equal (or, for nearly all of the

strategic benefit, nearly equal) candidates who are not honestly equal.

Moreover, I think that the DSV construction of this system gives it

excellent resistance to real-world strategies. Unless you have more

information than the agent which strategizes your ballot, you simply vote

honestly and allow the system to strategize for you. Thus, you wouldn't be

motivated to use strategy unless you felt you knew not only the exact

possibilities and chirality of the Smith set, both before and after your

strategizing, but also the probable winner from that Smith set. Under

realistic polling information, I think that such scenarios will be rare; if

you know of a possible Condorcet tie, then you will not generally know much

about the likely winners of this tie.

(It may even be provable that if you assume voters exist in some kind of

continuous, unimodal distribution in ideology space, and motivate Condorcet

ties by having non-euclidean but continuous distance measures, then there

will always naturally exist enough "honest defensive votes" to make any

strategy backfire).

Note that in regard to resisting simple strategies, this method is a serious

improvement over either Range or Approval. Because it is a kind of DSV, it

"does the strategy for you". So a candidate will gain no significant

advantage if their voters are more strategic (that is, more dichotomous and

better at evaluating the expected winners of the election) than other

candidates' voters. It allows for naive votes of many kinds, including

potentially "don't know" votes for certain candidates, simple approval-style

votes, simple ranking-style votes, and others, giving all approximately the

same power. And because it uses Range ballots as an input but encourages

more honest voting than Range, it enables the society to see (as an academic

question) who is the true Range winner, when that differs from the Condorcet

winner. I believe that, in successive elections, enough voters would

reevaluate such candidates to make one of them win in both senses.

Nonetheless, I will present one scenario where strategy might be employed.

Say the candidates are Nader, Gore, and Bush, and assume (contrafactually)

that this is simple a matter of 1-dimensional ideology and that all voters

agree that the candidates are, left to right,

nader..gore..........................bush (that is, Nader and Gore in this

scenario are considered much closer than Gore and Bush). Assume also that

there is some dearth of center-left voters who prefer Gore to Bush only

weakly. So the honest preferences are something like

Nader Gore Bush

11% 100 99 0

40% 99 100 0

49% 0 1 100

If all of the 11% of Nader voters dishonestly "bury" Gore under Bush, then

Nader wins with 50.6% (that is, 11% + (99%*40%)). However, if even 2 of the

40% Gore voters honestly vote Gore, Bush, Nader - or EVEN if those 2% simply

give Nader 1 point instead of 99 points - then the strategy backfires and

elects Bush. Given the honest utilities assumed, the Nader voters would not

use this strategy if they thought this was even 1% likely. In the real

election, of course, there was in fact a non-negligible minority of honest

Gore>Bush>Nader voters. (Gore voters were probably likelier to support Bush

second than Nader voters, and I've seen polls that say 1/4 of Nader voters

supported Bush second (!); 1/4 of Gore voters would be around 12%). So this

strategy would never have worked in real life, and in fact it requires an

artificial gap in the voter distribution right near the Gore>Bush>Nader zone

(extending on both sides of that zone, because for instance Gore>>Nader>Bush

votes hose the strategy too).