[EM] The Unique Winning Alliance method

[Rob Speer]

On Sun, Aug 03, 2003 at 08:47:40AM -0400, John B. Hodges wrote:
> Alex's example above shows the possibility of a "spoiler effect", 
> i.e. in a two-person race between A and B, A wins, but adding C to 
> the race gives the victory to B. Those who vote for C give the 
> election to their last choice, so if they understood the situation in 
> advance, they would abstain from voting for their first choice. That 
> is significant; up to now I thought that Monotonicity implied the 
> absence of a spoiler effect. If avoiding the spoiler effect depends 
> on a voting method satisfying IIAC, there will be very, very few 
> methods that qualify.  (Does anybody KNOW of any?)

Random Dictator.

But seriously:

My advisor at MIT is currently studying a method that has been
discovered independently by a few people, called either Unique Winning
Alliance or Nash-Condorcet (after John Nash).

Since it is non-dictatorial and Pareto-optimal, it of course can't
actually satisfy IIAC in the winner it ultimately chooses. However, the
method is non-deterministic, and the percentage chances of a given
candidate winning _are_ independent from irrelevant alternatives.

There are a couple of ways to describe it: the complicated, detailed way
and the simple way. The complicated way first:

We know that there isn't always a candidate who beats every other
candidate pairwise (i.e. a Condorcet winner). However, there is always
a _combination_ of candidates that beats every other such combination.
Such a combination might be 100% candidate A (a Condorcet winner), or
maybe something like 60% A, 30% B, 10% C (a cycle). The way you can
determine whether one combination beats another is to take percentages
of the winning margins and add them. If X>Y is the number of votes by
which X beats Y, then the combination (80% A, 20% B) beats (80% C, 20%
D) by .64*(A>C) + .16*(B>C) + .16*(A>D) + .04*(B>D).

Though it may seem computationally daunting to find such a combination
(the Unique Winning Alliance), it is actually easily solved by linear
programming, which is something that, for example, Matlab can do. You
can just treat the pairwise victory matrix as a matrix of inequalities
to be solved.

Once you have found the UWA, you still of course need to pick a winner
from it. In a sense you get a "Nash Set" of candidates, which is always
a subset (possibly the same set) of the Smith Set, who are the people
with non-zero shares in the UWA, and you need to pick a winner from it.

The nondeterministic method that sort of satisfies IIAC is to choose the
winner randomly, weighted by their percentages of the win.

Now for the simple description, which justifies wanting to name it after
John Nash.

Treat the pairwise matrix of candidates as a zero-sum game (like Rock
Paper Scissors). Two players each choose a candidate, and if one
candidate beats the other pairwise, the player who chose the winner gets
a number of points equal to the margin of victory.  Determine the
winning strategy for the game (which will be a set of possible choices
and the probability that you will make them). Then make one move in this
game according to that winning strategy. The candidate chosen by that
move wins the election.

(If there is a Condorcet winner, then the winning strategy will be to
always pick that candidate, as it always wins. Consider the childhood
RPS variant, "Rock, Paper, Scissors, Nuclear Bomb".)

The properties of this method:
* It is non-dictatorial and Pareto-optimal.
* It is _not_ monotonic. The share that someone gets of the UWA might go
down if they get additional votes. It's a surprising flaw, but a
necessary outcome of the almost-IIAC-ness.
* It is cloneproof. Clones will simply end up dividing their share of the
UWA between them.
* It is almost IIAC. Certainly, if a member of the Nash Set drops out, it
will change the result, but that member would have had a chance to win,
so he isn't especially irrelevant.  The result stays the same if anyone
outside the Nash Set leaves.  This does not break Arrow's Theorem
because Arrow does not allow for non-deterministic methods.
* Determining whether a candidate is in the Nash Set _is_ monotonic -
you can't fall out of the Nash Set by getting more votes. Thus, UWA can
be completed by other methods besides Weighted Random. UWA Sequential
Dropping seems especially appealing.

Some properties of the Nash Set:
* It is unique as long as ties are prevented. This can be done by adding
a strict preference ordering that counts as half of a vote as a
tiebreaker.
* It always has an odd number of candidates in it.

I hope others find this method as cool as I do. Sure, it's impractical,
but I find the Nash Set to be an even nicer theoretical tool than the
Smith Set.
-- 
Rob Speer