[EM] Possible advantage of NES (& maybe DSV) over wv with AERLO

[Jobst Heitzig]

Dear Mike,

I wonder whether I understand the NES stuff right. Let me consider a
very simple example: 3 options A,B,C, 3 voters, sincere preferences are
complete and strict rankings, base method is plurality.

First of all, it seems that the only situations where anyone has an
incentive to vote strategically are when each of A,B,C is favourite for
some voter. This is because when one of A,B,C is favourite for two or
three voters, that option wins with sincere votes and the at most one
voter who has a different favourite cannot do anything about it.

Hence the only interesting preference situations are, up to a renaming
of voters and/or options:

(a) the famous cycle      1:A>B>C, 2:B>C>A, 3:C>A>B
(b) the near-by situation 1:A>B>C, 2:B>C>A, 3:C>B>A

Now what equilibria exist with plurality in these situations?

(a) With sincere votes (ABC), plurality would elect either of A,B,C with
probability 1/3 here. When any one of the voters votes 2nd best instead,
she can improve upon this result in the sense that she keeps her bottom
option from being elected by accepting her middle option. When we count
this as an improvement, every voter has an incentive to vote
strategically here, and the resulting votes would be either BBC, ACC, or
ABA, resulting in a winner B, C, or A, resp.
In each of these three voting situations, it seems that no-one can
improve the result any further, hence these are three equilibria. I did
not find any other equilibria for (a). Anyway, by the symmetry the
situation (a) it is clear that also NES(plurality) would elect either of
A,B,C with probability 1/3 here.

(b) This is a bit more interesting. Again, each of the voters can
improve the result by voting 2nd best, and again the resulting voting
situations BBC, ACC, and ABB seem to be the only equilibria for
situation (b), whose winners are B, C, and again B, resp.
What would NES(plurality) elect here? It seems to me that a natural
solution would be to elect B or C at random, for example with
probabilities 2/3 and 1/3.

Now I understood from your postings that we might hope that the result
of NES would be in some sense optimal for each voter. But let us look
more closely at this method in the above example: NES(plurality) is a
ranked-ballots method electing B or C at random when the voters utter
the preferences (b) 1:A>B>C, 2:B>C>A, 3:C>B>A, am I right? But
NES(plurality) still elects B deterministically when the voters utter
the preferences (c) 1:B>A>C, 2:B>C>A, 3:C>B>A. Hence when (b) are the
sincere preferences, voter 1 has an incentive to vote (c) instead when
NES(plurality) is used. In other words, when (b) are the sincere
preferences, voting (b) is still not an equilibrium in NES(plurality),
but voting (c) is the equilibrium instead!

So, when the whole thing should make sense, we would have to consider
NES^2(base method) := NES(NES(base method)) and so on...
Fortunately, for any combination of finitely many options and voters
there is only a finite number of possible voting methods we must take
into account. Hence the sequence NES^k must become stable or periodic
for large k. If it becomes stable, that is, if NES^(k+1)=NES^k for some
k, then it seems that NES^k would be a method in which the equilibrium
result always equals the sincere result. Proof: NES^k(equilibrium
votes)=NES^(k+1)(sincere prefs)=NES^k(sincere prefs)? That doesn't mean
that NES^k leaves no incentives to vote strategically at all, but that
at least the situations attained by voting strategically are unstable
and will in the end lead to an equilibrium which gives the same result
as the sincere one. But what if the sequence NES^k does not become
stable but periodic? Is there a similar argument then?

Another question is: When can we be sure that equilibria exist? With
plurality, it seems that the equilibria are exactly those voting
situations where a majority votes for the Condorcet winner. In all other
situations, some majority would have an incentive to vote for the
Condorcet winner instead. Without a Condorcet winner, there would be no
equilibria. Are there base methods of which we know that equilibria must
exist? Does that follow from some well-known criterion for example?

Jobst