[EM] Least Expected Umbrage, a new lottery method

[fsimmons at pcc.edu]

Jobst,

I completed the computation, and (surprise!) the row player expectation turned out the same with both 
strategies: 3000/91 .

Do the two methods (Rivest Shen and LEU) always give equivalent results, or does this depend on the 
fact that we are dealing with complete rankings so that symmetric completiion of the bottom level 
doesn't change anything?

Given 3x=51 and 3y=49, it seems to me that LEU would give positive probability to D in the scenario

x A B C D
x B C A D
x C A B D
y D A B C
y D B C A
y D C A B

while Rivest Shen would give all of the support to the Smith set {A, B, C} .

There is still some sorting out to do here.

And now I'm not so sure that MinMax(margins) and MMPO with full symmetric completion are 
equivalent.  They both elect the CW when there is one, but in the above example (where there is no CW) 
they seem to give different results.

Let's try to make sense out of this..

Forest

----- Original Message -----
To: Jobst Heitzig ,
> Jobst, 
> 
> Yes, your Condorcet Lottery was the first of this kind, as I 
> pointed out on the EM list when the Rivest 
> paper first came to our attention.
> 
> Suppose that we replace each entry in the margins matrix with 
> its sign (-1, 0, or 1 depending on whether 
> it is negative zero or positive). we could call this matrix the 
> Copeland matrix.
> 
> Then the Condorcet Lottery is determined from the Copeland 
> Matrix in the same way that the Rivest 
> Shen Lottery is determined from the margins matrix.
> 
> Since these matrices are anti-symmetric and the game is zero 
> sum, the row and column players have 
> identical optimum (mixed) strategies, i.e. the games are symmetrical.
> 
> In the case of the Least Expected Umbrage lottery it turns out 
> that the row and column player lotteries 
> are not usually the same.
> 
> Take the very ballot set used as an example in the Rivest Paper:
> 
> (40) A B C D
> (30) B C A D
> (20) C A B D
> (10) C B A D
> 
> 
> The respective rows of the pairwise matrix are given by
> 
> A: 0 60 40 100
> B: 40 0 70 100
> C: 60 30 0 100
> D: 0 0 0 0
> 
> while the respective rows of the margins matrix are
> 
> A 0 20 -20 100
> B -20 0 40 100
> C 20 -40 0 100
> D -100 -100 -100 0
> 
> The common strategy of both row and column players for this game 
> is the lottery
> 
> A/4+B/2+C/4,
> 
> meaning that the respective probabilities for A, B, C and D are 
> 25%, 50%, 25%, and zero.
> 
> 
> For LEU we go back to the basic pairwise matrix and put 50 in 
> the lower right hand corner to represent 
> half of the number of ballots on which C was ranked bottom with 
> itself:
> 0 60 40 100
> 40 0 70 100
> 60 30 0 100
> 0 0 0 50
> 
> The bottom row of this matrix is dominated by each of the other 
> rows, so it can be removed from the row 
> player's strategy, and the (opposite of) the last column is 
> dominated by the (opposite of) each of the 
> other columns, so it can be removed from the column player's 
> strategy. 
> 
> We are left with the matrix
> 
> 0 60 40 
> 40 0 70 
> 60 30 0
> 
> For the zero sum game represented by this matrix the optimal 
> strategy of the row player turns out to be
> 
> (33*A+24*B+34*C)/91,
> 
> and the optimal strategy for the column player is
> 
> (33*A+34*B+24*C)/91 .
> 
> The row player's expected payoff is 3000/91.
> 
> If the row player adopts the Rivest strategy of (A+2*B+C)/4 
> instead of the optimal row player strategy
> (33*A+24*B+34*C)/91, and the column player sticks to the optimal 
> strategy(33*A+34*B+24*C)/91, then the expected payoff for the 
> row player will be less.

So this turns out to false:  the optimal strategy is not unique.

> 
> [Exercise: calculate this expectd payoff; I'm out of time.]
> 
> My Best,
> 
> Forest
> 
> 
> 
> 
> 
> 
> From: Jobst Heitzig 
> Date: Wednesday, December 21, 2011 4:25 am
> Subject: Re: [EM] Least Expected Umbrage, a new lottery method
> To: fsimmons at pcc.edu
> 
> > I just realized that this is quite similar to "Condorcet Lottery"
> > (http://lists.electorama.com/htdig.cgi/election-methods-
> > electorama.com/2005-January/014449.html)
> > where I even mention in the end that the payoff matrix could 
> be chosen
> > to reflect defeat strengths rather than just defeats (i.e., 
> > having entry
> > 1 where i beats j).
> > 
> > So maybe we should compare Rivest-Shen and LEU to Condorcet Lottery?
> >