[EM] How to fix the flawed "Nash equilibrium" concept for voting-theory purposes

[Jameson Quinn]

>
> Have each voter cast, not "one vote" but rather each voter casts "a
> standard gaussian random variable" number of votes of each possible
> type.  The voter does not get to control her vote, she only gets to
> control the mean of the Gaussians.   So for example, in the
> Gandhi-Hitler example, she can use the mean +1 or -1 (and fixed
> variance) and that is all.
>

This is a great idea at its heart, but I can see a couple of problems which
need fixing. For one thing, you didn't specify that the sum of the means for
all vote types must be 1. For another, as stated, this raises the
possibility of negative totals for certain vote types - something which many
voting systems couldn't handle. For a third, if you keep the variance for
each vote type constant, then total variance in "where my vote goes" depends
on the square root of the number of vote types - especially problematic for
Range voting, which has an unmanageably large number of vote types, even for
few candidates.

So, how about this: take all the honest votes. Then, take each vote type.
Say there are 8 A>B>C votes (in some ranked system). Instead, use a Poisson
distribution around 8. In other words, "There were an essentially infinite
number of possible voters who might have voted this way, and 8 of them made
it to the polls. If we ran the election again, without changing the
probability for each one of them, how many people might make it?"

To be clear: in the Gandhi/Hitler case, the situation where 100% vote Hitler
somehow against their will, is not a Nash equilibrium, because each voter
sees that there is some finite (though smaller than the number of atoms in
the visible universe) probability that a poisson distribution around 1 will
be greater than a poisson distribution around the 99,999 other voters still
voting Hitler.

Note that in a two-way race like that, honest voting IS a "Poisson/Nash
Equilibrium" in this sense.

Such incredibly tiny probabilities make the presence or absence of this sort
of equilibrium very, very dependent on the distributions used. I proposed
the Poisson distribution, rather than the Gaussian, because it is
well-behaved - two poissons sum to another one, and it is never negative -
and justifiable in a hand-waving-story sense.

However, I actually think that this distribution is not realistic. If you
rerun an election, things don't just change one voter at a time. Maybe it's
raining in the area where most of the A voters live. Maybe candidate B has a
minor stroke and starts swearing on national TV. If we allow voters to not
make it to the polls and phantom "possible" voters to make it to the polls,
why don't we allow the same for powerful endorsers? Etc. The probabilities
involved would be small - but essentially everything is bigger than the tiny
probabilities needed to sway the equilibrium. So we need some distribution
where different vote types are (weakly) correlated by some "distance
matrix", but which is still summable between any two random slices of the
electorate as the Poisson distribution was. Such a distribution would have
"fatter tails" than the Poisson, because of the autocorrelation within each
vote type. I'm sure such a distribution exists, but I don't have the math fu
to know if it's known, and even less so to derive it if unknown.

But the very existence of alternative distributions throws this whole thing
into some doubt. If situation X were shown to be a "Poisson Nash
equilibrium" but not (say) a "Lognormal Nash equilibrium", what would that
mean?

Anyway, good job, Warren.

I would like to compare your idea with the idea which may have prompted it,
my "bloc Nash equilibrium" which I mentioned in our recent private exchange.
The "bloc Nash equilibrium" regards each bloc of voters with a given honest
vote type as a single player, able to determine (through some kind of secret
collusion) as many ballots as it has members. You criticized this idea
because it allows collusion, the precise thing the Nash equilibrium was
invented to avoid. Still, the idea has content; unlike the plain Nash
equilibrium, there are some interesting cases which are not bloc Nash
equilibria and some which are, and I still find this interesting. My
criticism of this idea would be the opposite of yours: by segregating each
specific vote type, it doesn't allow ENOUGH collaboration. Something which
is not a bloc Nash equilibrium can easily be made into one by a sprinkling
of clones; as the blocs randomly break into pieces over their random
opinions of which clone is slightly better, we return to the plain Nash
equilibrium problem: there's so many players that essentially nobody is ever
pivotal and so everything's a bloc Nash equilibrium.

So, to compare: using the scenario from the range voting DH3/Condorcet page:

 A simple DH3 scenario (honest votes). The notation "X,Y" means a
*mixture*of X>Y and Y>X votes whose composition is not immediately
known.  #voters
 Their Vote   37  C>A,B>D   32 A>B,C>D   31 B>A,C>D
Of course, the Nash equilibrium does not consider probabilistic outcomes or
unknowns. So, let's make the "A,B" splits exactly 50/50, and fix it so that
there's a perfect tie between the A and B voters - that is, add one B>A,C>D
voter. Now, if the A and B blocs both bury, they will exactly tie for the
win in most Condorcet tiebreakers, and so split the utility with a coin
flip.

So, with the "Gaussian Nash equilibrium", an A voter considering burial will
see three infinitesimal probabilities, each vastly smaller than the
preceding ones: my burial causes A or B to win; A or B wins without my
burial; and my burial causes D to win. Thus, burial increases utility, and
so honest voting is not an equilibrium. (With a "poisson Nash equilibrium",
it is, unless there is at least one honest B>D>C or A>D>C voter; but you
could fix that with some tiny poisson for unvoted ballot types).

Note that a "correlated/fat tailed" Nash equilibrium could easily exist. If
the number of B>D>CA votes is correlated to the number of C>D>AB votes, then
an extra A>D>CB vote could easily cause a greater chance of a D win than of
an A or B win. Personally, I find this scenario more plausible than the pure
Poisson one, but my arguments are complicated not at all bulletproof.

Is there a "bloc Nash equilibrium"? Yes, because if only the A bloc, or only
the B bloc, buries, it does not affect the result.

I am not sure what the Nash equilibrium (or equilibria?) are, but I am sure
> that
> honest voting is not it, because each individual voter finds burial to
> be an "improvement."   Presumably the Nash strategy in that scenario
> will be a probability-mixture of honest and strategic votes.
>

This is interesting. My "poisson" fix to your scheme does not allow
probability-mixture votes. And yet Nash's proof still holds: there must be
some equilibrium. And your argument holds in some cases: all honest voting
is sometimes NOT that equilibrium. I guess that you can replace
probability-mixture for individual voters by splitting up the votes of the
honest blocs so that some pair two identical voters are assumed to vote
differently, but neither of them could improve their mutual expected result
by switching their own vote. My brain hurts.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20100413/d6ffaf05/attachment-0004.htm>