[EM] The Ultimate Lottery Method!

[fsimmons at pcc.edu]

Once one has an estimate of the lottery probability vector p, one can either
directly elect alternative k with probability p[k] or (more dramatically) one
can draw a random ballot vector b and elect alternative k with probability

p[k]*b[k]/(dot product of p and b) .

Either process yields the same ultimate winning probabilities.

If everything checks out (and if this method has not already been discovered
elsewhere) what should we call it?        

The HSULM (Heitzig/Simmons Ultimate Lottery Method)?  Or something more
descriptive like "The Maximum Peace on Earth and Good Will Voting Method."

It was Jobst's steadfast insistence on properties (1) through (6) (especially
property (3)) along with his many tentative approaches (from the Condorcet
Lottery, D2MAC, etc.) that led inexorably to this method.

>I wonder if the solution to the maximization problem could be done iteratively
> analogous to the iterative computation of  an eigenvector:

> Initialize a column matrix V with 1/n in all n rows, where n is the number of
> alternatives.

> For each ballot vector b, form another column matrix W(b) whose k_th component is

  >  (1/N)*V[k]*b[k]/(the dot product of b and V)

> Update V as the sum of all the W(b) over b.

>  Repeat until V stabilizes.

> Ballots are ratings with a minimum possible rating of zero.

> Ballots with all zero ratings are thrown out as not valid.

> The lottery probabilities are chosen so as to maximize the product of the
> expected ratings over the ballots.

> This method is (1) monotone, (2) clone free, and (3) gives proportional
> probability to stubborn voters.  (4) Each ballot has equal weight in determining
> the winning probabilities. (5) Good opportunities for cooperation are not wasted
> by this method. (6) There is little if any incentive for insincere ratings.

> Let's use the Lagrange multiplier method to find the lottery that maximizes the
> product of the expected ballot ratings:

> Let ProdE represent the product of the expected ratings, and let SumP represent
> the sum of the lottery probabilities.  Then a necessary condition for maximality
> of ProdE is the stationarity of the expression

> L = log(ProdE) - Lambda*SumP

> as the lottery probabilities are varied subject to the constraint SumP = 1.

> Setting to zero the partial derivative of  L  with respect to the lottery
> probability p(k) of the k_th alternative (i.e. candidate number k) verifies
> claim (4) in that each ballot b contributes to p(k) precisely the quantity

> (1/N)*p(k)*b(k)/E(b)

> where N = Lambda is the number of ballots, b(k) is ballot b's rating of
> alternative k, and E(b) is ballot b's expected rating

> E(b) = p(1)*b(1) + p(2)*b(2) + ...