[EM] DSV, NES, & SMA

Tue Feb 17 00:15:01 PST 2004

James--

You wrote:

	I've just now finished going over your reply about anti-reversal
enhancements. I've made a couple of notes for a reply, but first things
first:
	You mentioned a few methods which I haven't heard of: NES, DSV, and SMA.
Would you mind telling me how those work? They sound interesting. I'm
assuming that they don't stand for Nintendo Entertainment System or Deep
Sea Voyager.

I reply:

DSV:

Yes, when Lorrie Cranor named her proposal DSV, that used the same initials 
from the "Seaquest" tv show. And what a disappointing show that was. 
Scheider was much better in _Jaws_. Well, I can't say that I know for sure 
which came first, Sequest or Cranor's DSV. I heard of Cranor's DSV much 
later than the time when Seaquest was on tv.

DSV, outside of Seaquest, stands for Declared Strategy Voting. Though the 
DSV versions discussed here use Approval as their base method, Cranor's used 
Plurality.

Each voter rates the candidates numerically. These ratings are used for 
making Plurality (or Approval, on EM) strategy for a series of simulated 
elections. For instance, the first Plurality count is 0-info, and 
Plurality's 0-info strategy is to vote for one's favorite. So each simulated 
voter votes for hir favorite in the 1st simulatedPluality election.

But then, DSV calculates optimum Plurality strategy for each voter in each 
subsequent simulated Plurality election, and that strategy makes use of 
information from previous voting in the previous simulated Pluralitly 
elections. Cranor, at her website that has her DSV paper, discusses a number 
of ways of calculating that Plurality strategy. One maximizes one's 
expectation in Plurality by voting for the candidate with the highest 
strategic value. That depends on a voter's utility ratings, and on the Pij 
estimates. Pij is the probability that if there are 2 candidates between 
whom my ballot can make or break a tie for 1st place, then i & j are those 2 
candidates.

The Pij are called, at that website, pivotal probabilities. There's a page 
of the website entitled "Calculation of Pivotal Probabilities", or something 
like that.

She describes a number of ways of calculatinlg those Pij.

On EM there's been interest in DSV. Here, Approval is the base method for 
DSV.

Several list members have suggested interesting and creative refinements for 
DSV(Approval), new ways to estimate best Approval strategy based on the 
voting results so far.

Cranor suggested 2 kinds of DSV: Batch and Ballot-By-Ballot. Both of those 
kinds of DSV(Approval) have been discussed on EM.

I'll get to NES later in this posting, but it seems that DSV & NES have 
properties very similar to wv. NES is a little easier to study than DSV, and 
seems to share wv's compliance with the majority defensive strategy 
criteria. More about NES after SMA.

SMA:

Because DSV & NES have properties so similar to wv, I was interested in 
other possible ways of designing methods that, while different from wv, 
would share wv's criterion compliances. SMA was what I devised. It stands 
for Smith Majority Approval:

Balloting: Rank balloting, with Approval cutoff. Truncation & equal ranking 
permitted.

Delete from the ballots every candidate who isn't in the Smith set.

If that leaves more than one candidate undeleted, then delete every 
candidate who has a majorityi defeat that isn't in a cycle of majority 
defeats, unless every candidate has such a majority defeat.

If that leaves more than one candidate undefeated, then elect the candidate 
who is above the Approval cutoff of the most voters.

Of course, as was suggested by others, Any ballot Approvaing all of the 
undeleted candidates would be adjusted so that it would un-approve one of 
them. And any ballot disapproving all the remaining candidates would be 
modified so that it would approve one of them. These changes are easily made 
based on that voter's ranking.

[end of SMA definition]

SMA doesn't really improve on wv significantly if at all. So I don't really 
propose SMA, except in the event that there turned out to be a significant 
improvement over wv.

NES:

Nash Equilibrium Selection.

Alex, some time ago, suggested a method that would elect the candidate(s) 
who, based on the voted rankings, could win at Nash equilibrium in Approval.

Now, Allex said that he wasn't proposing that as an actual method proposal, 
but was just mentioning it for some other purpose. But NES appears to fully 
share wv's advantages. I was interested in NES because it might 
automatically get rid of the incentive to rank all the better set candidates 
equal in 1st place, for the voter who considsers the candidates to be in 2 
sets such that the merit differences within the sets is negligible compared 
to the merit difference between the sets.

To avoid repeating that long wording (well maybe just once), let me define 
an "ideal" method.

A method is "ideal" if:

1. It meets the 4 majority defensive strategy criteria.

AND

2. A voter who considers the candidates to be divided into 2 sets such that 
the merit differences within each set are negligible compared to the merit 
diference between the sets won't have strategic reason to rank the 
better-set candidates equal in 1st place.

[end of definition of an ideal method]

I call that "ideal", because it surely is the best that any method can do. 
Though NES, and probably DSV too, share wv's criterion compliances, they 
also share its susceptibility to offensive order-reversal. Apparently 
susceptibility to offensive order-reversal is a property of every method 
that doesn't have worse strategy problems.

I was interestred in NES and DSV because they might be ideal.

As I was sayingl, DSV & NES can have any method as a base method, including 
Approval, wv, SMA, themselves, or eachother.

I'd considered that maybe NES(Approval), NES(wv), or NES(NES(wv)) might be 
ideal.

But the better wv methods, SSD, BeatpathWinner/CSSD, RP, & SD can be made 
ideal by adding the automatic equal ranking line option (AERLO):

If a voter chooses AERLO, s/he indicates a line in hir ranking such that if 
there's a circular tie with members above & below that line, and no 
above-line candidates win, then that voter wants to promote all the 
above-line candidates to 1st place and have the count repeated.

[end of AERLO definition]

Since wv can be made ideal in that way, that reduces the need for NES or 
DSV. Those methods, as interesting and appealing as they are, probably don't 
improve qualitatively on wv with AERLO.

But, just looking at one example, ballot-by-ballot DSV(Appreoval), with 
Approval strategy determined as suggested by Forest & Rob LG, seemed to make 
a more difficult requirement for successful offensive order-reversal than wv 
does. I tried my usual 40,25,35 example, and with ballot-by-ballot DSV the 
uncountered offensive order-reversal failed, though it would succeed in wv.

That certainly doesn't mean that successful offensive order reversal is 
impossible in ballot-by-ballot DSV--it just suggests that that method might 
have a somewhat more difficult numerical requirement for the conditions for 
successful offensive order-reversal. And anyway, that was just from looking 
at one example.

But whether or not DSV & NES are needed for practical reasons, and whether 
or not they're qualitilativelly better than wv, they're still valuable, 
because for those ideal-based methods to have the properties of wv is a 
further argument for wv.

Here's how I defined NES:

Nash equilibrium definition for voting:

An outcome is a Nash equilibrium if there isn't  a set of voters who can, by 
changing their ballots, improve the outcome for themselves if no one else 
changes their ballot.

Balloting: Rank balloting. Truncation & equal ranking permitted. Maybe have 
Approval cutoff.

The winner is the candidate who, based on the voted rankings, could win at 
Nash Equilibrium when a particular specified base method is used.

Outcome X keeps outcome Y from being a Nash equilibrium if some set of 
voters can improve on Y by making X.

If there are no Nash equilibria, then the tie consists of the candidates who 
win in outcomes that keep other outcomes from being Nash equilibria.

If there are 2 or more candidates who can win at Nash equilibria, then the 
tie consists of them.

If there's a tie, then the winner is the tie-member who is included in the 
most rankings.

If the balloting includes Approval cutoff, then the winner of the tie is the 
tie-member who is above the Approval cutoff of the most voters.

[end of NES definition]

I'd considered calling NES "Nash Equilibrium Winner" (NEW), but that sounded 
too promotional.
Well maybe...

I've sometimes asked how good a voting system can be. A voting system can be 
as good as wv with AERLO, and NES, & and  probably DSV.

As I've said, wv, NES, & DSV can benefit from all the anti-order-reversal 
enhancements that I've suggested, under conditions where offensive 
order-reversal is considered a problem.

Mike Ossipoff

_________________________________________________________________
Dream of owning a home? Find out how in the First-time Home Buying Guide. 
http://special.msn.com/home/firsthome.armx