[EM] Least Expected Umbrage, a new lottery method

[fsimmons at pcc.edu]

> From: Kristofer Munsterhjelm 
> To: fsimmons at pcc.edu
> Cc: election-methods at lists.electorama.com
> Subject: Re: [EM] Least Expected Umbrage, a new lottery method
> Message-ID: <4EEF6F55.40607 at lavabit.com>
> Content-Type: text/plain; charset=ISO-8859-1; format=flowed
> 
> On 12/19/2011 01:50 AM, fsimmons at pcc.edu wrote:
> > Let M be the matrix whose row i column j element M(i,j) is the 
> number> of ballots on which i is ranked strictly above j plus 
> half the number
> > of ballots on which neither i nor j is ranked.
> >
> > In particular, for each k the diagonal element M(k , k) is 
> half the
> > number of ballots on which candidate k is unranked.
> >
> > Now think of M as the payoff matrix for the row player in a 
> zero sum
> > game.
> >
> > Elect the candidate that would be chosen by the optimal 
> strategy of
> > the row player.
> >
> > [End of Method Definition]
> 
> Is that method strategy-proof? If not, is there any way to 
> determine 
> whether a given stochastic method is strategy-proof or not? I 
> know that 
> some are (such as Random Pair, for instance).

Random favorite is also strategy proof.  I do not know of any general technique for detecting strategy 
proofness.

> 

> From: Warren Smith 
> To: election-methods 
> Subject: [EM] Least Expected Umbrage
> Message-ID:
> 
> Content-Type: text/plain; charset=ISO-8859-1
> 
> can you compare this method with
> Rivest-Shen voting?
> 
> http://people.csail.mit.edu/rivest/gt/latest_full.pdf
> 

Rivest-Shen voting has the same relation to MinMax(margins) that LEU voting has to MMPO with 
Symmetric Completion Bottom.

Like MinMax(margins) Rivest Shen satisfies the Condorcet Criterion but fails the FBC.  LEU satisfies the 
FBC but fails the Condorcet Criterion.

Rivest Shen fails mono-raise-winner.  I hope that LEU is fully monotone.

The Rivest Shen probabilities form the optimal mixed strategy for a two person zero sum game based on 
the margins matrix.  In that game the row and column players have the same strategy.

The LEU probabilities form the optimal mixed strategy for the column player in the two person zero sum 
game based on the matrix M whose (i, j) entry M(i,j) is the number of ballots on which candidate i is 
rated strictly greater than candidate j plus half the number of ballots on which both i and j are rated at 
minRange.

Basically M(i,j) is the opposition to candidate i from the candidate j supporters.  Since for different values 
of i the opposition is different, we must give greater weight to the more credible values of i.  The row 
player's probabilities supply these weights.  The column player's probabilities give the optimal response 
to this threat.

This is easiest to see when there is a saddle point so that for some i and j, the value M(i,j) is the min 
element in row i and the max element in column j.

In this case the optimal row strategy is P(i)=100%.  the optimal column strategy is P(j)=100%.  This is 
the same result given by the deterministic method MMPO with Symmetric Completion Bottom.

Note that i is the biggest offensive threat to j, and j has the best defense against i.  So we are pitting the 
candidate with the best offense against the candidate with the best defense.

Electing the candidate with the best defense over-rides the preferences of the fewest voters.

When there is no saddle point there is no single best offensive or defensive candidate.  That's where the 
mixed strategies come in.

You might say that the MMPO winner is the best defensive candidate, but that is only true if the 
candidate that scores the most against him/her is an actual credible threat, i.e. a candidate that is 
strong against other candidates as well.  The mixed strategies automatically take this consideration into 
account.

There's probably a simpler way to explain this, but I hope my explanation is somewhat helpful.

Forest