[EM] The Nash Equilibrium method for counting rankings. Other "player" definition.
MIKE OSSIPOFF
nkklrp at hotmail.com
Mon Jan 5 08:08:02 PST 2004
I believe it was probably Alex who once suggested a method that chooses the
candidate who wins at Nash equilibrium.
Alex, could you repeat that method definition again?
It sounds like a promising method. I was suggesting that, for Nash
equilbrium for voting, a "player" be a set of same-voting voters.
But when that definition of a player is used, the Nash equilibrium method
isn't truncation resistant.
40: A
25: BA
35: C
A has 65 votes, B has 25 votes, and C has 35 votes.
A wins. No one set of same-voting voters can improve on that outcome for
themselves.
.
If the B voters withdraw their vote for A, then A still wins, with 40 votes
to C's 35.
If the C voters vote for B, then A still wins, beating B 65 to 60.
So that outcome is a Nash equilibrium, by the "player" definition that I
quoted above. A wins by truncation at Nash equilibrium.
But I suggest a more natural definition of a "player" in voting: A set of
voters who can improve on the outcome for themselves.
Someone here once suggested a "player" definition different from the one I
suggested, and I didn't like it for some reason. I don't know if that other
definition is the one that I'm suggesting now.
So a Nash equilibrium then is an outcome that no set of voters can improve
on for themselves.
With that definition, and that example, that set is the B voters and the C
voters. The B voters withdraw their vote for A, and the C voters vote for B.
So now that A victory isn't a Nash equilibrium.
Using the Nash equilibrium definition in the paragraph before last, let me
define this method:
Nash Equilibrium Selection (NES):
Balloting: Rank balloting, allowing truncation and equal rankings.
Elect the candidate who can win at Nash equilibrium in an Approval election
between the candidates, based on the voters preferences expressed in their
ballot rankings.
Outcome A keeps outcome B from being a Nash equilibrium if some set of
voters can improve on B for themselves to get A.
If there's no Nash equilibrium, because every outcome is kept from being a
Nash equilibrium by some othe outcome, then the tie is the set of candidates
who win in outcomes that keep other outcomes from being Nash equilibrium.
If there's more than one Nash equilibrium, then the tie is the set of
candidates who win in those outcomes.
Ties are solved by having all the rankings give an Approval vote to each of
their ranked candidates.
That tie solution seems to get rid of some strategy incentive.
Someone suggested Approval Completed Condorcet. I don't remember exactly how
it went. Alex, if that was you, would you re-post it?
If one solves circular ties by having each ranking give an Approval vote to
each of its ranked candidates, that isn't truncation resistant.
The advantage of NES is that it only uses that tie solution when there isn't
a truncation cycle.
With 3 candidates, NES seems to have strategy properties similar to wv
Condorcet. I don't know if that remains so with more candidates.
All the new method proposals are more complicated to evaluate than
Condorcet, and so it's difficult to say how they do in terms of strategy.
But NES looks good at first glance, with 3 candidates.
So does Forest's and Rob LG's Ballot-By-Ballot (BBB?), and Lorie Cranor's
DSV, Declared Strategy Voting (when DSV uses Approval with the
best-frontrunner strategy).
But I only took a quick look at them. The new methods tend to be more
complicated and therefore more difficult to evaluate.
Those two are even more difficult to evaluate than NES, but with one
particular 3-candidate example that I checked, they both are truncation
resistant and, with both, offensive order-reversal can be thwarted by
defensive truncation.
Interestingly, with BBB, the defensive truncation elected the CW, unlike
with other methods that I know of. That could be considered a good thing,
because the defenders are improving the immediate outcome for themselves.
But it also means that, to the extent that that happens, defensive
truncation isn't a deterrent to offensive order-reversal. That could mean
that the defensive strategy could be needed more often. But, even without
defensive truncation, offensive order-reversal can backfire, and so it
always has some deterrent if the would be order-reversers aren't sure of the
faction numbers.
With BBB, the offensive order-reversal failed in my example. Apparently BBB
has more difficult faction-numbers requirements for successful offensive
order-reversal.
But all nonprobabilistic 1-balloting methods are vulnerable to offensive
order-reversal. The method has no way of determining if a circular tie is
strategic or natural. If it's strategic, the method has no way of
determining who the CW is and who is order-reversing, or which majorities
are sincere.
So how can it be expected to elect the CW when there's order-reversal? How
can it be expected to not reward the refersal if it can't determine who's
reversing?
So, even with fancier or more deluxe nonprobabilistic 1-balloting methods,
methods, we've still got offensive order-reversal and, when that strategy is
used, the need for defensive truncation.
Condorcet wv apparently is very difficult to improve on. Difficult but maybe
possible, in some minor way. But not in terms of the gross strategy problems
that 1-balloting methods all have.
Maybe there are other simpler ways of detecting truncation circular ties,
maybe in wv, so that only the other circular ties are solved by the
apparently strategy-reducing Approval tiebreaker.
I suggest that someone test the new methods with computer simulation in
which truncation takes place, and in which offensive order-reversal takes
place. And in which offensive order-reversal is countered by defensive
truncation. In that way they can be tested with more candidates.
It's worth doing if there's a chance of one or more of those methods
bringing a little improvement.
So the anti-order-reversal enhancements that I suggested in a previous
posting some time ago would be useful in any nonprobabilistic 1-balloting
method.
I suggested a few, but I'd like to add a few more:
Spectrum-order-estimate:
The method can't recognize order-reversal because it knows nothing about
anyone's preference ordering and nothing about the political spectrum
ordering. But the voter can often identify order-reversal if s/he knows
something about the political spectrum ordering. So the voter could have the
option of marking his spectrum order estimate on the ballot, authorizing the
method to drop from his ballot any candidate whose voters apparently
order-reverse and cause a strategic circular tie.
When any of these anti-order-refersal options are chosen, they'd be carried
out only if there's a circular tie whose each member has a majority defeat.
A previous suggestion was that the voter have the option to indicate a line
in his ranking, so that, if there's a circular tie all of whose defeats are
majority defeats, and with members above and below the line, that voter
wants to drop the below-line candidates from his ranking.
I also tentatively suggested an option for the voter to use a method of
detecting some order-reversals based on the pattern of unanimity and
nonunanimity of the lower choices of voters who share a 1st choice. It makes
some sense with 3 candidates, but I don't know if it work with more
candidates.
As before, it would automatically drop the apparent reversers' candidate
from the ranking of the voter who chose that option.
But, as I said, I don't believe that order-reversal will be a problem with
wv, for the reasons that I stated in that earlier posting. So these
anti-order-reversal enhancements wouldn't reallly be needed, though they
could be proposed at some time after wv enactment, if people became
concerned about strategy.
So far, all the new methods, NSE, BBB, & DSV and others aren't sufficiently
tested to be proposed. Some or all of them seem to complicated for a first
proposal. But if there are any other new method proposals that are expected
to bring improvement, could someone re-post them or tell the year and day on
which they can be found in the archives? And these methods should be more
thoroughly tested in computer simulations with more candidates, with
truncation and offensive order-reversal, and offensive order-reversal
countered by defensive truncation.
Mike Ossipoff
_________________________________________________________________
Tired of slow downloads? Compare online deals from your local high-speed
providers now. https://broadband.msn.com
More information about the Election-Methods
mailing list