[EM] Least Expected Umbrage, a new lottery method

[fsimmons at pcc.edu]

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.

[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?
>